A New Trade-off for Deterministic Dictionaries

Rasmus Pagh

February 2000


We consider dictionaries over the universe $U=\{0,1\}^w$ on a unit-cost RAM with word size $w$ and a standard instruction set. We present a linear space deterministic dictionary with membership queries in time $(\log\log n)^{O(1)}$ and updates in time $(\log n)^{O(1)}$, where $n$ is the size of the set stored. This is the first such data structure to simultaneously achieve query time $(\log n)^{o(1)}$ and update time $O(2^{\sqrt{\log n}})$

Available as PostScript, PDF.


Last modified: 2003-06-08 by webmaster.