An Analysis of Random-Walk Cuckoo Hashing
By Alan M. Frieze, Páll Melsted, Michael M. Mitzenmacher. 2009
68 citations recorded by the source corpus.
In this paper, we provide a polylogarithmic bound that holds with high probability on the insertion time for cuckoo hashing under the random-walk insertion method. Cuckoo hashing provides a useful methodology for building practical, high-performance hash tables. The essential idea of cuckoo hashing is to combine the power of schemes that allow multiple hash locations for an item with the power to dynamically change the location of an item among its possible locations. Previous work on the case where the number of choices is larger than two has analyzed breadth-first search, which is both inefficient in practice and currently has only a polynomial upper bound on the insertion time that holds with high probability. On the other hand, it does have expected constant amortized insertion time. Here we significantly advance the state of the art by proving a polylogarithmic bound that holds with high probability on the more efficient random-walk method, where items repeatedly kick out random blocking items until a free location for an item is found.
Subfields: Artificial Intelligence, Hardware and Architecture, Signal Processing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Kim Laine
- Hao Chen
- Srinath T. V. Setty
- Sebastian Angel
- Gil Segev
- Moni Naor
- Yuriy Arbitman
- Megha Khosla
In Hardware and Architecture
In Signal Processing
Citations in the corpus
- PIR with Compressed Queries and Amortized Query Processing (2018, background): “Analyzing the exact failure probability of Cuckoo hashing, and determining the constant factors, remains an open problem (see [42] for recent progress).”
- Balls into Bins Made Faster (2013, background): “In [7, 9] the authors analyzed the random walk insertion method and gave a polylogarithmic bound (with high probability) on the maximum allocation time, i.”
- Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation (2009, background): “For further and improved analysis see also [CSW07, DM09, DGM + 10, FR07, FP09, FM09, FMM09, LP09].”