Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation
Speaker: Moni Naor , Weizmann Institute
Date: December 15 2009
Time: 4:15PM to 5:15PM
Location: 32-G155
Host: Scott Aaronson, TOC, CSAIL
Contact: Be, 3-6098, imbe@mit.edu
Relevant URL: The performance of a dynamic dictionary is measured mainly by its update
time, lookup time, and space consumption. 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 talk I will focus on a recent line of work with the goal of
achieving the best possible performance guarantees simultaneously.
In particular, the following constructions will be described:
-- A de-amortization of cuckoo hashing that stores n elements using
roughly 2n memory words, and guarantees constant-time time operations
in the worst case with high probability, for any sequence of polynomially many operations.
-- The first dynamic dictionary that enjoys the best of both worlds: 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 as above. 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 for
eliminating the dependency on bin sizes.
--- A variant of the previous construction that stores n elements using
only (1+o(1))B bits, where B is the information-theoretic lower bound
for representing a (static) 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.
Joint work with Yuriy Arbitman and Gil Segev.
See other events that are part of Theory Colloquium 2009/2010
See other events happening in December 2009
