A New Trade-off for Deterministic Dictionaries

  • Rasmus Pagh


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) ).
How to Cite
Pagh, R. (2000). A New Trade-off for Deterministic Dictionaries. BRICS Report Series, 7(4). https://doi.org/10.7146/brics.v7i4.20132