Hashing, load balancing and multiple choice

著者

• Wieder, Udi

書誌事項

Hashing, load balancing and multiple choice

Udi Wieder

（Foundations and trends in theoretical computer science, 12:3-4）

now, c2017

• : pbk

注記

Includes bibliographical references (p. 99-109)

内容説明・目次

内容説明

Many tasks in computer systems could be abstracted as distributing items into buckets, so that the allocation of items across buckets is as balanced as possible, and, furthermore, given an item's identifier it is possible to determine quickly to which bucket it was assigned. A canonical example is a dictionary data structure, where `items' stands for key-value pairs and `buckets' for memory locations. Another example is a distributed key-value store, where the buckets represent locations in disk or even whole servers. A third example may be a distributed execution engine where items represent processes and buckets compute devices, and so on. A common technique in this domain is the use of a hash-function that maps an item into a relatively short fixed length string. The hash function is then used in some way to associate the item to its bucket. The use of a hash function is typically the first step in the solution and additional algorithmic ideas are required to deal with collisions and the imbalance of hash values. Hashing, Load Balancing and Multiple Choice presents some of the basic algorithmic ideas that underpin many of the practical and theoretically interesting approaches for this problem. It focuses on multiple choice schemes where items are placed into buckets via the use of several independent hash functions, and typically an item is placed at the least loaded bucket at the time of placement. It analyses the distributions obtained, and shows how these ideas could be used to design basic data structures. With respect to data structures it focuses on dictionaries, presenting linear probing, cuckoo hashing and many of their variants.

目次

• 1: Introduction
• 2: Simple Hashing - the One Choice Scheme
• 3: Multiple Choice Schemes
• 4: The Heavily Loaded Case
• 5: Dictionaries
• References.

「Nielsen BookData」 より

詳細情報

• NII書誌ID(NCID): BC12179645
• ISBN:
  • 9781680832822
• 出版国コード: us
• タイトル言語コード: eng
• 本文言語コード: eng
• 出版地: Hanover
• ページ数/冊数: 10, 109 p.
• 大きさ: 24 cm
• 親書誌ID:
  • BA81053856