Table Lookup Techniques

ABSTRACT

Consideration is given to the basic methodology for table searching in computer programming. Only static tables are treated, but references are made to techniques for handling dynamic tables. Methods described are: sequential search, merge search, binary search, estimated entry, and direct entry. The rationale of key transformation is discussed, with some consideration of methods of “hash addressing.” A general guide to technique selection is given in conclusion.

REFERENCES

• 1: R. L. Glass, An Elementary Discussion of Compiler/Interpreter Writing, ACM Computing Surveys (CSUR), v.1 n.1, p.55-77, March 1969 [doi>10.1145/356540.356545]
• 2: USA standard vocabulary for information processing. USAS X3.12-1966, USASI, New York. 1966. Yet another attempt to define and name computer-related words and concepts.
• 3: Edward H. Sussenguth, Jr., Use of tree structures for processing files, Communications of the ACM, v.6 n.5, p.272-279, May 1963 [doi>10.1145/366552.366600]
• 4: Harry A. Clampett, Jr., Randomized binary searching with tree structures, Communications of the ACM, v.7 n.3, p.163-165, March 1964 [doi>10.1145/363958.363987]
• 5: A. K. Scidmore , B. L. Weinberg, Storage and search properties of a tree-organized memory system, Communications of the ACM, v.6 n.1, p.28-31, Jan. 1963 [doi>10.1145/366193.366215]
• 6: Robert Morris, Scatter storage techniques, Communications of the ACM, v.11 n.1, p.38-44, Jan. 1968 [doi>10.1145/362851.362882]
• 7: PRICE, C. E. "Representing characters to computers." American Documentation 20, 1 (Jan. 1969), 50-60. A meandering discussion of alphanumeric data processing, including problems of making "keys" on page 56.
• 8: SPIEGEL, MURRAY R. Curve fitting and the method of least squares in theory of problems of statistics. Sehaum's Outline Series, New York, 1961, Chapter 13.
• 9: Disc storage concepts--student text. Form F20-8161, IBM, White Plains, New York, 1963. Key transforming and randomizing are discussed in relation to disc storage.
• 10: Introduction to IBM System/360 direct access storage devices and organization methods. C20- 1649-2, IBM, White Plains, New York, 1966. Chapter 8, Direct Organization, offers a discussion of various key transforming (and randomizing) techniques.
• 11: 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization