Order-Preserving Key Transformations.

Anil K. Garg, C. C. Gotlieb: Order-Preserving Key Transformations. ACM Trans. Database Syst. 11(2): 213-234(1986)
  author    = {Anil K. Garg and
               C. C. Gotlieb},
  title     = {Order-Preserving Key Transformations},
  journal   = {ACM Trans. Database Syst.},
  volume    = {11},
  number    = {2},
  year      = {1986},
  pages     = {213-234},
  ee        = {, db/journals/tods/GargG86.html},
  bibsource = {DBLP,}


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.

Copyright © 1986 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
Rudolf Bayer, Karl Unterauer: Prefix B-Trees. ACM Trans. Database Syst. 2(1): 11-26(1977) BibTeX
Walter A. Burkhard: Interpolation-Based Index Maintenance. PODS 1983: 76-89 BibTeX
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
R. F. Deutscher, Paul G. Sorenson, J. Paul Tremblay: Distribution-Dependent Hashing Functions and Their Characteristics. SIGMOD Conference 1975: 224-236 BibTeX
Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979) BibTeX
Gaston H. Gonnet, Lawrence D. Rogers, J. Alan George: An Algorithmic and Complexity Analysis of Interpolation Search. Acta Inf. 13: 39-52(1980) BibTeX
Gary D. Knott: Hashing Functions. Comput. J. 18(3): 265-278(1975) BibTeX
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978) BibTeX
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
Witold Litwin: Trie Hashing. SIGMOD Conference 1981: 19-29 BibTeX
W. D. Maurer, T. G. Lewis: Hash Table Methods. ACM Comput. Surv. 7(1): 5-19(1975) BibTeX
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX
Jack A. Orenstein: A Dynamic Hash File for Random and Sequential Accessing. VLDB 1983: 132-141 BibTeX
Leen Torenvliet, Peter van Emde Boas: The Reconstruction and Optimization of Trie Hashing Functions. VLDB 1983: 142-156 BibTeX
Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978) BibTeX

Referenced by

  1. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  2. Soon Myoung Chung, Jaerheen Yang: Distributive Join Algorithm for Cube-Connected Multiprocessors. DASFAA 1993: 253-260
  3. Nabil I. Hachem, P. Bruce Berra: New Order Preserving Access Methods for Very Large Files Derived From Linear Hashing. IEEE Trans. Knowl. Data Eng. 4(1): 68-82(1992)
  4. Nabil I. Hachem, P. Bruce Berra: Key-Sequential Access Methods for Very Large Files Derived from Linear Hashing. ICDE 1989: 305-312
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:38:59 2008