Backyard Cuckoo Hashing:
Constant Worst-Case Operations with a Succinct Representations
Yuriy Arbitman Moni Naor
The performance of a dynamic dictionary is measured mainly by its update time,
lookup time, and memory 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
Don Knuth analyzed linear probing, the trade-off between these aspects of
performance is still not completely understood.
This work provides the construction of the first dynamic dictionary that
enjoys the best of both worlds: it stores n elements using only (1 +
o(1))B bits, 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. This problem
was open even in the amortized setting. One of the main ingredients of our
construction is a permutation-based variant of cuckoo hashing.
An application of the above result is an approximate set membership data
structure (AKA Bloom Filter) that is within 1+o(1) of optimal size and
works in worst case O(1) time for updates and lookups.
Slides in Hebrew (Shimon Even Memorial talk)
Related On-Line Papers:
- Yuriy Arbitman, Moni Naor and Gil Segev,
De-amortized Cuckoo Hashing: Provable Worst-Case Performance and
- Moni Naor, Gil Segev and Udi Wieder,
History-Independent Cuckoo Hashing, ICALP 2008.
Back to: On-Line Publications, Recent Papers