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
- 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 allocation and dictionaries with tightly packed constant size bins
- Balanced Allocations
- 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
- scientific article; zbMATH DE number 5764819 (Why is no real title available?)
- 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
(20)- A faster algorithm for cuckoo insertion and bipartite matching in large graphs
- Parallel d-Pipeline: A Cuckoo Hashing Implementation for Increased Throughput
- Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables
- Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)
- Some Open Questions Related to Cuckoo Hashing
- Matchings on infinite graphs
- Load Thresholds for Cuckoo Hashing with Overlapping Blocks
- Dense peelable random uniform hypergraphs
- Greedy matching in bipartite random graphs
- Constant-time retrieval with O( m) extra bits
- Load thresholds for cuckoo hashing with double hashing
- Orientability Thresholds for Random Hypergraphs
- The Multiple-Orientability Thresholds for Random Hypergraphs
- Load Thresholds for Cuckoo Hashing with Overlapping Blocks
- What if we tried less power? Lessons from studying the power of choices in hashing-based data structures
- Peeling close to the orientability threshold. Spatial coupling in hashing-based data structures
- ShockHash: near optimal-space minimal perfect hashing beyond brute-force
- Insertion time of random walk cuckoo hashing below the peeling threshold
- Ribbon: fast succinct static retrieval and approximate membership
- Fast scalable construction of ([compressed] static | minimal perfect hash) functions
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)
