Dictionaries on

RAMs: Query Time

is Necessary and Sufficient

Arne Andersson
Peter Bro Miltersen
Sřren Riis
Mikkel Thorup

June 1997

Abstract:

In this paper we consider solutions to the dictionary problem on RAMs, i.e. random access machines where the only restriction on the finite instruction set is that all computational instructions are in . Our main result is a tight upper and lower bound of on the time for answering membership queries in a set of size n when reasonable space is used for the data structure storing the set; the upper bound can be obtained using O(n) space, and the lower bound holds even if we allow space . Furthermore, the lower bound holds even for static dictionaries, while the upper bound holds also for dynamic dictionaries; insertion and deletions can be accommodated in expected amortized time .

Several variations of this bound is also obtained, including tight upper and lower bounds on the storage space if the query time must be constant and bounds valid for non- RAMs if the execution time of an instruction computing a function is measured as the minimal depth of a polynomially sized unbounded fan-in circuit computing the function. We refer to this model as the Circuit RAM. As an example of the latter, we show that any RAM instruction set which permits a linear space, constant query time solution to the static dictionary problem must have an instruction of depth , where w is the word size of the machine (and the size of the universe). This matches the depth of multiplication and integer division, used in the two level hashing scheme of Fredman, Komlós and Szemerédi

Available as PostScript, PDF, DVI.

Last modified: 2003-06-08 by webmaster.