ACM SIGMOD Anthology VLDB dblp.uni-trier.de

The Reconstruction and Optimization of Trie Hashing Functions.

Leen Torenvliet, Peter van Emde Boas: The Reconstruction and Optimization of Trie Hashing Functions. VLDB 1983: 142-156
@inproceedings{DBLP:conf/vldb/TorenvlietB83,
  author    = {Leen Torenvliet and
               Peter van Emde Boas},
  editor    = {Mario Schkolnick and
               Costantino Thanos},
  title     = {The Reconstruction and Optimization of Trie Hashing Functions},
  booktitle = {9th International Conference on Very Large Data Bases, October
               31 - November 2, 1983, Florence, Italy, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1983},
  isbn      = {0-934613-15-X},
  pages     = {142-156},
  ee        = {db/conf/vldb/TorenvlietB83.html},
  crossref  = {DBLP:conf/vldb/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We propose an adaptation to the trie hashing algorithm published by W. Litwin in 1980. This adaptation extends the algorithm so that it will save necessary information on secondary storage to reconstruct the hashing function after loss of information (E.G., system crash or termination of a find/insert program). An algorithm is given to reconstruct the trie from the information saved, and another for optimizing the reconstructed trie. A mathematical analysis of the trie data structure is given, making visible the essential structural properties of these tries; based on this analysis correctness of the algorithms presented can be established.

Copyright © 1983 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Mario Schkolnick, Costantino Thanos (Eds.): 9th International Conference on Very Large Data Bases, October 31 - November 2, 1983, Florence, Italy, Proceedings. Morgan Kaufmann 1983, ISBN 0-934613-15-X
Contents BibTeX

References

[1]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX
[2]
...
[3]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[4]
...
[5]
...

Referenced by

  1. Witold Litwin, Djamel Eddine Zegour, Gérard Lévy: Multilevel Trie Hashing. EDBT 1988: 309-335
  2. Anil K. Garg, C. C. Gotlieb: Order-Preserving Key Transformations. ACM Trans. Database Syst. 11(2): 213-234(1986)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
 ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:18 2009