A New Trade-off for Deterministic Dictionaries

Abstract

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) ).