The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.5 / (1996))
The Tree Model for Hashing: Lower and Upper Bounds
Joseph Gil, Friedhelm Meyer Auf Der Heide, Avi Wigderson,
Pages. 936-955
Abstract We define a new simple and general model for hashing. The basic model together with several variants capture many natural (sequential and parallel) hashing algorithms and represent common hashing practice. Our main results exhibit tight tradeoffs between hash-table size and the number of applications of a hash function on a single key.
Contents 1. Introduction
2. The tree model for hashing
2.1. The basic model
2.2. Comments
2.3. Resources
2.4. Variants of the basic model
3. Results
4. Proofs of lower bounds
4.1. Root-node hashing
4.2. The basic model and the chaining variant
4.3. The parallel variant
4.4. The retries variant
5. Proofs of upper bounds
5.1. Foundaton: Algorithm FKS
5.2. The retries variant: Algorithm RestyShallow
5.3. The basic model: Algorithm BasicShallow
5.4. The parallel variant: Algorithm ParShallow
5.5. The chaining variant: Algorithm Chain Shallow
6. Concluding remarks
Key words parallel algorithms, randomization data structures.
Mathmatical Subject Classification 68P10, 68P05, 68Q10, 68Q22