Static dictionaries on AC/sup 0/ RAMs: query time θ(√log n/log log n) is necessary and sufficient
Authors:
- P.B. MiltersenPMP.B. Miltersen
- S. RiisSRS. Riis
- M. ThorupMTM. Thorup
- 24 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 441-450
Abstract
In this paper we consider solutions to the static dictionary problem on AC/sup 0/ RAMs, i.e. random access machines where the only restriction on the finite instruction set is that all computational instructions are in AC/sup 0/. Our main result is a tight upper and lower bound of /spl theta/(/spl radic/log n/log log n) 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 2/sup polylog n/. Several variations of this result are also obtained. Among others, we show a tradeoff between time and circuit depth under the unit-cost assumption: any RAM instruction set which permits a linear space, constant query time solution to the static dictionary problem must have an instruction of depth /spl Omega/(log w/log log to), where w is the word size of the machine (and log the size of the universe). This matches the depth of multiplication and integer division, used in the perfect hashing scheme by M.L. Fredman, J. Komlos and E. Szemeredi (1984).Keywords
This publication has 14 references indexed in Scilit:
- Sublogarithmic searching without multiplications2002
- Lower bounds for static dictionaries on RAMs with bit operations but no multiplication1996
- Sorting in linear time?1995
- Surpassing the information theoretic bound with fusion treesJournal of Computer and System Sciences, 1993
- Constant depth circuits, Fourier transform, and learnabilityJournal of the ACM, 1993
- The computational complexity of universal hashingTheoretical Computer Science, 1993
- Log Depth Circuits for Division and Related ProblemsSIAM Journal on Computing, 1986
- Storing a Sparse Table with 0 (1) Worst Case Access TimeJournal of the ACM, 1984
- Constant Depth ReducibilitySIAM Journal on Computing, 1984
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979