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

       Yuriy Arbitman      Moni Naor      Gil Segev     

Abstract:

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. In this paper we settle two fundamental open problems:

• We construct the first dynamic dictionary that enjoys the best of both worlds: we present a two-level variant of cuckoo hashing that stores n elements using (1+o(1))n memory words, and
  guarantees constant-time operations in the worst case with high probability. The construction is based on augmenting cuckoo hashing with a “backyard” that handles a large fraction of the elements, together with a de-amortized perfect hashing scheme.
  
  
• We present a variant of our construction that uses only (1+o(1))B bits of memory, where B is the information-theoretic lower bound for representing a set of size n taken from a
  universe of size u, and guarantees constant-time operations in the worst case with high  probability, as before. This problem was open even in the amortized setting. Our approach
  is based on k-wise almost independent permutations with a succinct representation and a constant evaluation time.

  Paper: PDF. Slides: ppt.

  Related On-Line Papers:

  • Yuriy Arbitman, Moni Naor and Gil Segev, De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results, ICALP 2009. Abstract, PDF.

  • Moni Naor, Gil Segev, and Udi Wieder, History-Independent Cuckoo Hashing,  ICALP 2008. Abstract, Postscript, gzipped Postscript, PDF. Slides: ppt.

  Back to: On-Line Publications,  Recent Papers
  

  Back Home