Tight Thresholds for Cuckoo Hashing via XORSAT

By Martin Dietzfelbinger, A. Goerdt, Michael M. Mitzenmacher, Andrea Montanari, Rasmus Pagh, Michael Rink. 2009

164 citations recorded by the source corpus.

We settle the question of tight thresholds for offline cuckoo hashing. The problem can be stated as follows: we have n keys to be hashed into m buckets each capable of holding a single key. Each key has k ≥ 3 (distinct) associated buckets chosen uniformly at random and independently of the choices of other keys. A hash table can be constructed successfully if each key can be placed into one of its buckets. We seek thresholds ck such that, as n goes to infinity, if n/m ≤ c for some c ck a hash table cannot be constructed successfully with high probability. Here we are considering the offline version of the problem, where all keys and hash values are given, so the problem is equivalent to previous models of multiple-choice hashing. We find the thresholds for all values of k > 2 by showing that they are in fact the same as the previously known thresholds for the random k-XORSAT problem.We then extend these results to the setting where keys can have differing number of choices, and make a conjecture (based on experimental observations) that extends our result to cuckoo hash tables storing multiple keys in a bucket.

Subfields: Computer Vision and Pattern Recognition, Genetics, Molecular Biology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Molecular Biology

Michael M. Mitzenmacher

Citations in the corpus

PIR with Compressed Queries and Amortized Query Processing (2018, background): “Analyzing the exact failure probability of Cuckoo hashing remains an open problem (see [33] for the most recent progress).”
Invertible bloom lookup tables (2011, background): “As can be found in for example [8], [15], these values are given by”
Scalable Private Set Intersection Based on OT Extension (2018, methodology): “It was later shown in [Dietzfelbinger et al. 2010] that increasing the number of hash functions k > 2 achieves much better utilization of bins in the hash table.”
Fast Private Set Intersection from Homomorphic Encryption (2017, background): “While some asymptotic results exist for estimating the failure probability of cuckoo hashing [17, 24], the hidden constants are difficult to determine precisely.”
On the phase transition in random simplicial complexes (2014, background): “We can similarly deﬁne h T j,r ( s ) = is ˜ R v rj ,v rj , and by the same argument, h T j,r ( s ) The proof is concluded by letting s → 0.”