Sharp load thresholds for cuckoo hashing
From MaRDI portal
Abstract: The paradigm of many choices has influenced significantly the design of efficient data structures and, most notably, hash tables. Cuckoo hashing is a technique that extends this concept. There,we are given a table with locations, and we assume that each location can hold one item. Each item to be inserted chooses randomly k>1 locations and has to be placed in any one of them. How much load can cuckoo hashing handle before collisions prevent the successful assignment of the available items to the chosen locations? Practical evaluations of this method have shown that one can allocate a number of elements that is a large proportion of the size of the table, being very close to 1 even for small values of k such as 4 or 5. In this paper we show that there is a critical value for this proportion: with high probability, when the amount of available items is below this value, then these can be allocated successfully, but when it exceeds this value, the allocation becomes impossible. We give explicitly for each k>1 this critical value. This answers an open question posed by Mitzenmacher (ESA '09) and underpins theoretically the experimental results. Our proofs are based on the translation of the question into a hypergraph setting, and the study of the related typical properties of random k-uniform hypergraphs.
Recommendations
Cites work
- scientific article; zbMATH DE number 5764819 (Why is no real title available?)
- A phase transition for avoiding a giant component
- A precise analysis of cuckoo hashing
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- An analysis of random-walk cuckoo hashing
- Balanced Allocations
- Balanced allocation and dictionaries with tightly packed constant size bins
- Cores in random hypergraphs and Boolean formulas
- Cuckoo hashing
- Cuckoo hashing: Further analysis
- De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results
- How asymmetry helps load balancing
- Orientability of random hypergraphs and the power of multiple choices
- Some Open Questions Related to Cuckoo Hashing
- Space efficient hash tables with worst case constant access time
- Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)
- The \(k\)-orientability thresholds for \(G_{n,p}\)
- The asymptotic number of labeled graphs with given degree sequences
- The random graph threshold for \(k\)-orientiability and a fast algorithm for optimal multiple-choice allocation
- Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)
Cited in
(16)- A faster algorithm for cuckoo insertion and bipartite matching in large graphs
- Matchings on infinite graphs
- Load Thresholds for Cuckoo Hashing with Overlapping Blocks
- Load thresholds for cuckoo hashing with double hashing
- Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables
- Some Open Questions Related to Cuckoo Hashing
- Fast scalable construction of ([compressed] static | minimal perfect hash) functions
- What if we tried less power? Lessons from studying the power of choices in hashing-based data structures
- Load Thresholds for Cuckoo Hashing with Overlapping Blocks
- Greedy matching in bipartite random graphs
- Orientability Thresholds for Random Hypergraphs
- Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)
- scientific article; zbMATH DE number 7525475 (Why is no real title available?)
- scientific article; zbMATH DE number 7559133 (Why is no real title available?)
- The Multiple-Orientability Thresholds for Random Hypergraphs
- Parallel d-Pipeline: A Cuckoo Hashing Implementation for Increased Throughput
This page was built for publication: Sharp load thresholds for cuckoo hashing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3168497)
