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

Full Text:


DOI: http://dx.doi.org/10.7146/brics.v7i4.20132
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.

ISSN: 0909-0878 

Hosted by the Royal Danish Library and Aarhus University Library