ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Order Preserving Linear Hashing Using Dynamic Key Statistics.

John T. Robinson: Order Preserving Linear Hashing Using Dynamic Key Statistics. PODS 1986: 91-99
@inproceedings{DBLP:conf/pods/Robinson86,
  author    = {John T. Robinson},
  title     = {Order Preserving Linear Hashing Using Dynamic Key Statistics},
  booktitle = {Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 24-26, 1986, Cambridge, Massachusetts},
  publisher = {ACM},
  year      = {1986},
  isbn      = {0-89791-179-2},
  pages     = {91-99},
  ee        = {http://doi.acm.org/10.1145/6012.6014, db/conf/pods/Robinson86.html},
  crossref  = {DBLP:conf/pods/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A class of order preserving key associative access methods based on linear hashing is presented. The overwhelming advantage of these methods for many applications is that sequential access is supported. In these methods, dynamically maintained key statistics are used at the beginning of each expansion to construct new order preserving hash functions that should be approximately uniform. An example of such a function using positional digram frequency statistics is given, and the results of an experiment using these methods is reported.

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.


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Printed Edition

Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 24-26, 1986, Cambridge, Massachusetts. ACM 1986, ISBN 0-89791-179-2
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library


References

[Burkhard 83]
Walter A. Burkhard: Interpolation-Based Index Maintenance. BIT 23(3): 274-294(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Carter&Wegman 79]
Larry Carter, Mark N. Wegman: Universal Classes of Hash Functions. J. Comput. Syst. Sci. 18(2): 143-154(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Litwin 80]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Larson 80]
Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Larson 82]
Per-Åke Larson: Performance Analysis of Linear Hashing with Partial Expansions. ACM Trans. Database Syst. 7(4): 566-587(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Referenced by

  1. Kyu-Young Whang, Sang-Wook Kim, Gio Wiederhold: Dynamic Maintenance of Data Distribution for Selectivity Estimation. VLDB J. 3(1): 29-51(1994)
  2. 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)
  3. Nabil I. Hachem, P. Bruce Berra: Key-Sequential Access Methods for Very Large Files Derived from Linear Hashing. ICDE 1989: 305-312
  4. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents

Copyright © Mon Nov 2 21:03:54 2009 by Michael Ley (ley@uni-trier.de)