AbstractIn this paper we characterize several expansion techniques used for linear hashing and we present how to analyze any linear hashing technique that expands based on local events or that mixes local events and global conditions. As an example we give a very simple randomized expansion technique, which is easy to analyze and implement. Furthermore, we obtain the analysis of the original hashing technique devised by Litwin, which was unsolved until now, comparing it to the later and more widely used version of Larson's. We also analyze one hybrid technique. Among other results, it is shown that the control function used by Litwin does not produce a good storage utilization, matching known experimental data.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; E.5 [Files]; E.2 [Data Storage Representations]
Additional Key Words and Phrases: external hashing, linear hashing, analysis of algorithms, optimal bucketing
Selected references
- Richard J. Enbody and H. C. Du. Dynamic hashing schemes. ACM Computing Surveys, 20(2):85-113, June 1988.
- Per-Åke Larson. Linear hashing with partial expansions. In Sixth International Conference on Very Large Data Bases, pages 224-232, Montreal, Quebec, Canada, 1-3 October 1980. IEEE-CS.
- Per-Åke Larson. Performance analysis of linear hashing with partial expansions. ACM Transactions on Database Systems, 7(4):566-587, December 1982.
- Witold Litwin. Linear hashing: A new tool for file and table addressing. In Sixth International Conference on Very Large Data Bases, pages 212-223, Montreal, Quebec, Canada, 1-3 October 1980. IEEE-CS.