Order-preserving key transformations

ABSTRACT

File organizations based on conventional hash functions provide faster access to the stored records in comparison with tree-like file structures. Tree structures such as B+-trees and ISAM do provide for sequential processing, but require considerable storage for the indices. When sequential processing is needed a table that performs an order-preserving transformation on keys can be used. H is an order-preserving key transform if H(K1) ⩾ H(K2), for all keys K1> K2. We present methodologies for constructing such key transforms, and illustrate them for some real-life key sets. Storage requirements for the table needed to carry out the transformation are less than those needed for the indices.

REFERENCES

• 1: BAYER, R., AND MCCREIGHT, E. Organization and maintenance of large ordered indexes. Acta Inf. 1, 3 (1972), 173-189.
• 2: Rudolf Bayer , Karl Unterauer, Prefix B-trees, ACM Transactions on Database Systems (TODS), v.2 n.1, p.11-26, March 1977 [doi>10.1145/320521.320530]
• 3: Walter A. Burkhard, Interpolation-based index maintenance, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588070]
• 4: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 5: R. F. Deutscher , P. G. Sorenson , J. P. Tremblay, Distribution-dependent hashing functions and their characteristics, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500111]
• 6: Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
• 7: Anil Kumar Garg, Order-preserving dynamic file organizations for non-uniform access patterns, 1984
• 8: GONNEqVr, G. H., ROGERS, L. D., AND GEORGE, J.A. An algorithmic and complexity analysis of interpolation search. Acta Inf. 13 (1980)~ 39-52.
• 9: Leo R. Gotlieb, Data Types and Structures, Prentice Hall PTR, Upper Saddle River, NJ, 1978
• 10: HOROWITZ, E., ^~D SAHNI, S, Fundamentals of Data Structures. Computer Science Press, Rockville, Md., 1982.
• 11: KNOTT, G.D. Hashing functions. Comput. J. 18 (Aug. 1975), 265-278.
• 12: 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
• 13: LARSON, P.-A. Dynamic hashing. BIT 18, 2 {1978), 184-201.
• 14: LITWIN, W. Linear hashing=. A new tool for file and table addressing. In Proceedings 6th International Conference on Very Large Data Bases (Montreal, 1980), 212-223.
• 15: Witold Litwin, Trie hashing, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582322]
• 16: James Martin, Computer Database Organization, 2nd Ed, Prentice Hall PTR, Upper Saddle River, NJ, 1977
• 17: G. N.N. Martin, Spiral Storage: Incrementally Augmentable Hash Addressed Storage, University of Warwick, Coventry, UK, 1979
• 18: W. D. Maurer , T. G. Lewis, Hash Table Methods, ACM Computing Surveys (CSUR), v.7 n.1, p.5-19, March 1975 [doi>10.1145/356643.356645]
• 19: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 20: Jack A. Orenstein, A Dynamic Hash File for Random and Sequential Accessing, Proceedings of the 9th International Conference on Very Large Data Bases, p.132-141, October 31-November 02, 1983
• 21: SORENSON, P. G., TREMBLAY, J. P., AND DEUTSCHER, R.F. Key-to-address transformation techniques. INFOR J~ 16, 1 (Feb. 1978), 1-34.
• 22: TAMMINEN, M. Some aspects of order-preserving hashing. Rep. HTKK-TKO-A19, Laboratory of Information Processing, Helsinki Univ. of Technology, Espoo, Finland, 1980.
• 23: TAMMINEN, M. A note on order-preserving extendible hashing and bucket tries. Rep. HTKK- TKO-B29, Laboratory of Information Processing, Helsinki Univ. of Technology, Espoo, Finland, 1981.
• 24: Leen Torenvliet , Peter van Emde Boas, The Reconstruction and Optimization of Trie Hashing Functions, Proceedings of the 9th International Conference on Very Large Data Bases, p.142-156, October 31-November 02, 1983
• 25: VELAZQUEZ, H. University of Toronto library automation systems. On-Line Rev. 3, 3 (1979), 253-264.
• 26: YAO, A.C. Random 2-3 trees. Acta Inf. 9 (1978), 159-170.
• 27: The Illustrated Science and Invention Encyclopedia. International Edition, H. S. Stuttman, New York, 1980.

INDEX TERMS

Classification:
  E. Data
  E.5 FILES
      Subjects: Organization/structure

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

General Terms:
Algorithms, Design, Management, Measurement, Performance, Theory