A New Trade-off for Deterministic Dictionaries
Rasmus Pagh · BRICS Report Series · 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) ).