Abstract:
We consider dictionaries that perform lookups by probing a single word of memory, knowing only the size of the data structure. We
describe a randomized dictionary where a lookup returns the correct answer
with probability 
, and otherwise returns ``don't
know''. The lookup
procedure uses an expander graph to select the memory location to probe.
Recent explicit expander constructions are shown to yield space usage much
smaller than what would be required using a deterministic lookup procedure.
Our data structure supports efficient deterministic updates,
exhibiting new probabilistic guarantees on dictionary running
time
, and otherwise returns ``don't
know''. The lookup
procedure uses an expander graph to select the memory location to probe.
Recent explicit expander constructions are shown to yield space usage much
smaller than what would be required using a deterministic lookup procedure.
Our data structure supports efficient deterministic updates,
exhibiting new probabilistic guarantees on dictionary running
timeAvailable as PostScript, PDF, DVI.