ACM SIGMOD Anthology TODS dblp.uni-trier.de

Bounded Index Exponential Hashing.

David B. Lomet: Bounded Index Exponential Hashing. ACM Trans. Database Syst. 8(1): 136-165(1983)
@article{DBLP:journals/tods/Lomet83,
  author    = {David B. Lomet},
  title     = {Bounded Index Exponential Hashing},
  journal   = {ACM Trans. Database Syst.},
  volume    = {8},
  number    = {1},
  year      = {1983},
  pages     = {136-165},
  ee        = {http://doi.acm.org/10.1145/319830.319837, db/journals/tods/Lomet83.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Bounded index exponential hashing, a new form of extendible hashing, is described. It has the important advantages over most of the other extendible hashing variants of both (i) providing random access to any record of a file in close to one disk access and (ii) having performance which does not vary with file size. It is straightforward to implement and demands only a fixed and specifiable amount of main storage to achieve this performance. Its underlying physical disk storage is readily managed and record overflow is handled so as to insure that unsuccessful searches never take more than two accesses. The method's ability to access data in close to a single disk access makes it possible to organize a database, in which files have a primary key and multiple secondary keys, such that the result is a significant performance advantage over existing organizations.

Copyright © 1983 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

References

[1]
Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
[2]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[3]
Larry Carter, Mark N. Wegman: Universal Classes of Hash Functions. J. Comput. Syst. Sci. 18(2): 143-154(1979) BibTeX
[4]
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
[5]
...
[6]
Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
BibTeX
[7]
Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978) BibTeX
[8]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
[9]
David B. Lomet: Digital B-Trees. VLDB 1981: 333-344 BibTeX
[10]
...
[11]
Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978) BibTeX

Referenced by

  1. Gunter Saake, Andreas Heuer: Datenbanken: Implementierungstechniken. MITP-Verlag 1999, ISBN 3-8266-0513-6
    Contents
  2. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  3. Georgios Evangelidis, David B. Lomet, Betty Salzberg: The hB-Pi-Tree: A Multi-Attribute Index Supporting Concurrency, Recovery and Node Consolidation. VLDB J. 6(1): 1-25(1997)
  4. Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988)
  5. David B. Lomet: A Simple Bounded Disorder File Organization with Good Performance. ACM Trans. Database Syst. 13(4): 525-551(1988)
  6. Richard J. Enbody, H. C. Du: Dynamic Hashing Schemes. ACM Comput. Surv. 20(2): 85-113(1988)
  7. Witold Litwin, Djamel Eddine Zegour, Gérard Lévy: Multilevel Trie Hashing. EDBT 1988: 309-335
  8. David B. Lomet: Partial Expansions for File Organizations with an Index. ACM Trans. Database Syst. 12(1): 65-84(1987)
  9. Carla Schlatter Ellis: Concurrency in Linear Hashing. ACM Trans. Database Syst. 12(2): 195-217(1987)
  10. Witold Litwin, David B. Lomet: The Bounded Disorder Access Method. ICDE 1986: 38-48
  11. Eugene Veklerov: Analysis of Dynamic Hashing with Deferred Splitting. ACM Trans. Database Syst. 10(1): 90-96(1985)
  12. Kyoji Kawagoe: Modified Dynamic Hashing. SIGMOD Conference 1985: 201-213
  13. Nathan Goodman, Dennis Shasha: Semantically-based Concurrency Control for Search Structures. PODS 1985: 8-19
  14. Carla Schlatter Ellis: Concurrency and Linear Hashing. PODS 1985: 1-7
  15. Ekow J. Otoo: A Mapping Function for the Directory of a Multidimensional Extendible Hashing. VLDB 1984: 493-506
  16. Peter Kjellberg, Torben U. Zahle: Cascade Hashing. VLDB 1984: 481-492
  17. David B. Lomet: A High Performance, Universal, Key Associative Access Method. SIGMOD Conference 1983: 120-133
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:38:51 2008