Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation

By Yuriy Arbitman, Moni Naor, Gil Segev. 2009

121 citations recorded by the source corpus.

The performance of a dynamic dictionary is measured mainly by its update time, lookup time, and space consumption. In terms of update time and lookup time there are known constructions that guarantee constant-time operations in the worst case with high probability, and in terms of space consumption there are known constructions that use essentially optimal space. However, although the first analysis of a dynamic dictionary dates back more than 45 years ago (when Knuth analyzed linear probing in 1963), the trade-off between these aspects of performance is still not completely understood. In this paper we settle two fundamental open problems: \begin{itemize} \item We construct the first dynamic dictionary that enjoys the best of both worlds: it stores $\boldsymbol{n}$ elements using $\boldsymbol{(1 + \epsilon) n}$ memory words, and guarantees constant-time operations in the worst case with high probability. Specifically, for any \boldsymbol{\epsilon = \Omega ( (\log \log n / \log n)^{1/2} )}$ and for any sequence of polynomially many operations, with high probability over the randomness of the initialization phase, all operations are performed in constant time which is independent of $\boldsymbol{\epsilon}$. The construction is a two-level variant of cuckoo hashing, augmented with a ``backyard'' that handles a large fraction of the elements, together with a de-amortized perfect hashing scheme for eliminating the dependency on $\boldsymbol{\epsilon}$. \item We present a variant of the above construction that uses only $\boldsymbol{(1 + o(1))\B}$ bits, where $\boldsymbol{\B}$ is the information-theoretic lower bound for representing a set of size $\boldsymbol{n}$ taken from a universe of size $\boldsymbol{u}$, and guarantees constant-time operations in the worst case with high probability, as before. This problem was open even in the {\em amortized} setting. One of the main ingredients of our construction is a permutation-based variant of cuckoo hashing, which significantly improves the space consumption of cuckoo hashing when dealing with a rather small universe. \end{itemize}

Subfields: Artificial Intelligence, Computer Networks and Communications

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

In Computer Networks and Communications

Citations in the corpus

PIR with Compressed Queries and Amortized Query Processing (2018, background): “Relatedly, many data structures, systems, and networking applications use different variants of hashing—consistent [49], asymmetric [73], weighted [72], multi-choice [9, 61], cuckoo [8, 63], and others [18, 34]—to achieve the same goal.”
Pseudorandom Functions: Three Decades Later (2017, methodology): “In the realm of data structures, permutation-based hashing, which is inspired by the Feistel construction of PRPs, has been applied to improve the performance of dynamic dictionaries [12].”
Fast Private Set Intersection from Homomorphic Encryption (2017, methodology): “Independent of the exact hashing scheme, permutation-based hashing [3] is an optimization to reduce the length of the items stored in the hash tables by encoding a part of an item into the bin index.”
Oblivious RAM Revisited (2010, background): “, [11,12,13,3,4]) present variants of Cuckoo hashing with guaranteed constant worst-case performance for insertion (this is also referred to as de-amortizing the insertion time of Cuckoo hashing).”
Scalable Private Set Intersection Based on OT Extension (2018, methodology): “The bit-length of the stored items can be reduced based on a permutation-based hashing technique that was suggested in [Arbitman et al. 2010] for reducing the memory usage of Cuckoo hashing.”