A practitioner's guide to addressing algorithms

ABSTRACT

This paper consolidates a number of popular rules of thumb which have been suggested for the design of record addressing algorithms, and discusses the applicability of these rules to large commercial databases. Guidelines for selecting identifier transformations, overflow techniques, loading factors, bucket sizes, and loading order are considered. Particular attention is focused on the reasonableness of common heuristics for determining primary or secondary bucket sizes. A mathematical model which explicitly considers storage device characteristics and time/space cost tradeoffs is used to analyze the effect of design parameters on overall system costs. A specific design example is presented and solved.

REFERENCES

• 1: Buchholz, W. File organization and addressing. IBM Syst. J. (June 1963), 86-111.
• 2: Canning, R.G. Structures for future systems. EDP Analyzer 12, 8 (Aug. 1974).
• 3: Heising, W.P. Note on random addressing techniques. IBM Syst. J. (June 1963), 112-116.
• 4: Introduction to IBM Direct-Access Storage Devices and Organization Methods GD 20-1649. IBM Corp., White Plains, N.Y., 1973.
• 5: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 6: V. Y. Lum , P. S. T. Yuen , M. Dodd, Key-to-address transform techniques: a fundamental performance study on large existing formatted files, Communications of the ACM, v.14 n.4, p.228-239, April 1971 [doi>10.1145/362575.362578]
• 7: Robert Morris, Scatter storage techniques, Communications of the ACM, v.11 n.1, p.38-44, Jan. 1968 [doi>10.1145/362851.362882]
• 8: Charles A. Olson, Random access file organization for indirectly addressed records, Proceedings of the 1969 24th national conference, p.539-549, August 26-28, 1969 [doi>10.1145/800195.805959]
• 9: Peterson, W.W. Addressing for random access storage. IBM J. Res. Dev. (April 1957), 130-146.
• 10: G. Schay, Jr. , W. G. Spruth, Analysis of a file addressing method, Communications of the ACM, v.5 n.8, p.459-462, Aug. 1962 [doi>10.1145/368637.368827]
• 11: Senko, M.E., et al. File Design Handbook (Final Report, Contract AF 30602-60-C-0100), IBM Research, San Jose, Calif., Nov. 1969.
• 12: Dennis G. Severance, Identifier Search Mechanisms: A Survey and Generalized Model, ACM Computing Surveys (CSUR), v.6 n.3, p.175-194, Sept. 1974 [doi>10.1145/356631.356633]
• 13: Van der Pool, J.A. Optimum Load Factors for Files. IBM Nederland N.V., 1973.

INDEX TERMS

Keywords:
addressing techniques, bucket size, data management, file retrieval, hashing functions, heuristic design, loading factor, rules of thumb, searching, synonym resolution