Faster Deterministic Dictionaries

Rasmus Pagh

Abstract


We consider static dictionaries over the universe U = {0, 1}^w on a
unit-cost RAM with word size w. Construction of a static dictionary with
linear space consumption and constant lookup time can be done in linear
expected time by a randomized algorithm. In contrast, the best previous
deterministic algorithm for constructing such a dictionary with n elements
runs in time O(n^(1+epsilon)) for epsilon > 0. This paper narrows the gap between
deterministic and randomized algorithms exponentially, from the factor of
n^epsilon to an O(log n) factor. The algorithm is weakly non-uniform, i.e. requires
certain precomputed constants dependent on w. A by-product of the result
is a lookup time vs insertion time trade-off for dynamic dictionaries, which
is optimal for a certain class of deterministic hashing schemes.

Full Text:

PDF


DOI: http://dx.doi.org/10.7146/brics.v6i48.20118
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.
OK


ISSN: 0909-0878 

Hosted by the Royal Danish Library and Aarhus University Library