Order-preserving key transformations

@article{citeulike:3399266, 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(K 1 ) \⩾ H(K 2 ), for all keys K 1 > K 2 . 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.}, address = {New York, NY, USA}, author = {Garg, Anil K. and Gotlieb, C. C.}, citeulike-article-id = {3399266}, doi = {10.1145/5922.5923}, issn = {0362-5915}, journal = {ACM Trans. Database Syst.}, keywords = {hash, order-preserving}, number = {2}, pages = {213--234}, posted-at = {2008-10-13 04:55:35}, priority = {2}, publisher = {ACM}, title = {Order-preserving key transformations}, url = {http://dx.doi.org/10.1145/5922.5923}, volume = {11}, year = {1986} }

TY - JOUR ID - citeulike:3399266 L3 - citeulike-article-id:3399266 N2 - 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(K 1 ) ⩾ H(K 2 ), for all keys K 1 > K 2 . 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. IS - 2 JF - ACM Trans. Database Syst. SN - 0362-5915 AD - New York, NY, USA EP - 234 TI - Order-preserving key transformations PB - ACM VL - 11 SP - 213 KW - hash KW - order-preserving AU - Garg, Anil AU - Gotlieb, CC PY - 1986/// UR - http://dx.doi.org/10.1145/5922.5923 ER -