Open AccessOne-Probe Search
Author(s) -
Anna Östlin,
Rasmus Pagh
Publication year - 2002
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v9i9.21727
Subject(s) - computer science , probabilistic logic , expander graph , algorithm , word (group theory) , graph , lookup table , theoretical computer science , arithmetic , mathematics , artificial intelligence , programming language , geometry
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 1 - epsilon, 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.