ACM SIGMOD Anthology TODS dblp.uni-trier.de

Extendible Hashing - A Fast Access Method for Dynamic Files.

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)
@article{DBLP:journals/tods/FaginNPS79,
  author    = {Ronald Fagin and
               J{\"u}rg Nievergelt and
               Nicholas Pippenger and
               H. Raymond Strong},
  title     = {Extendible Hashing - A Fast Access Method for Dynamic Files},
  journal   = {ACM Trans. Database Syst.},
  volume    = {4},
  number    = {3},
  year      = {1979},
  pages     = {315-344},
  ee        = {http://doi.acm.org/10.1145/320083.320092, db/journals/tods/FaginNPS79.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Extendible hashing is a new access technique, in which the user is guaranteed no more than two page faults to locate the data associated with a given unique identifier, or key. Unlike conventional hashing, extendible hashing has a dynamic structure that grows and shrinks gracefully as the database grows and shrinks. This approach simultaneously solves the problem of making hash tables that are extendible and of making radix search trees that are balanced. We study, by analysis and simulation, the performance of extendible hashing. The results indicate that extendible hashing provides an attractive alternative to other access methods, such as balanced trees.

Copyright © 1979 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]
...
[2]
...
[3]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[4]
Larry Carter, Mark N. Wegman: Universal Classes of Hash Functions. J. Comput. Syst. Sci. 18(2): 143-154(1979) BibTeX
[5]
...
[6]
...
[7]
...
[8]
Gary D. Knott: Expandable Open Addressing Hash Table Storage and Retrieval. SIGFIDET Workshop 1971: 187-206 BibTeX
[9]
...
[10]
Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978) BibTeX
[11]
Witold Litwin: Virtual Hashing: A Dynamically Changing Hashing. VLDB 1978: 517-523 BibTeX
[12]
George Markowsky, Larry Carter, Mark N. Wegman: Analysis of a Universal Class of Hash Functions. MFCS 1978: 345-354 BibTeX
[13]
...
[14]
...
[15]
...
[16]
Jürg Nievergelt, Edward M. Reingold: Binary Search Trees of Bounded Balance. SIAM J. Comput. 2(1): 33-43(1973) BibTeX
[17]
...
[18]
...
[19]
Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978) BibTeX

Referenced by

  1. Volker Markl, Martin Zirkel, Rudolf Bayer: Processing Operations with Restrictions in RDBMS without External Sorting: The Tetris Algorithm. ICDE 1999: 562-571
  2. Gunter Saake, Andreas Heuer: Datenbanken: Implementierungstechniken. MITP-Verlag 1999, ISBN 3-8266-0513-6
    Contents
  3. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  4. Guido Moerkotte: Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing. VLDB 1998: 476-487
  5. Ye-In Chang: Alternating Hashing for Expansible Files. IEEE Trans. Knowl. Data Eng. 9(1): 179-185(1997)
  6. Witold Litwin, Marie-Anne Neimat, Donovan A. Schneider: LH* - A Scalable, Distributed Data Structure. ACM Trans. Database Syst. 21(4): 480-525(1996)
  7. Jun-Ichi Aoe, Katsushi Morimoto, Masami Shishibori, Ki-Hong Park: A Trie Compaction Algorithm for a Large Set of Keys. IEEE Trans. Knowl. Data Eng. 8(3): 476-491(1996)
  8. Betty Salzberg: Access Methods. ACM Comput. Surv. 28(1): 117-120(1996)
  9. Alfons Kemper, Donald Kossmann: Adaptable Pointer Swizzling Strategies in Object Bases: Design, Realization, and Quantitative Analysis. VLDB J. 4(3): 519-566(1995)
  10. André Eickler, Carsten Andreas Gerlhof, Donald Kossmann: A Performance Evaluation of OID Mapping Techniques. VLDB 1995: 18-29
  11. Peter Buneman, Susan B. Davidson, Kyle Hart, G. Christian Overton, Limsoon Wong: A Data Transformation System for Biological Data Sources. VLDB 1995: 158-169
  12. Sang-Wook Kim, Wan-Sup Cho, Min-Jae Lee, Kyu-Young Whang: A New Algorithm for Processing Joins Using the Multilevel Grid File. DASFAA 1995: 115-123
  13. Jukka Teuhola: Effective Clustering of Objects Stored by Linear Hashing. CIKM 1995: 274-280
  14. Kyu-Young Whang, Sang-Wook Kim, Gio Wiederhold: Dynamic Maintenance of Data Distribution for Selectivity Estimation. VLDB J. 3(1): 29-51(1994)
  15. M. V. Ramakrishna: Bounded Disorder File Organization. IEEE Trans. Knowl. Data Eng. 6(1): 79-85(1994)
  16. Goetz Graefe, Ann Linville, Leonard D. Shapiro: Sort versus Hash Revisited. IEEE Trans. Knowl. Data Eng. 6(6): 934-944(1994)
  17. Radek Vingralek, Yuri Breitbart, Gerhard Weikum: Distributed File Organization with Scalable Cost/Performance. SIGMOD Conference 1994: 253-264
  18. Gabriel Matsliach: Performance Analysis of File Organizations that Use Multibucket Data Leaves with Partial Expansions. ACM Trans. Database Syst. 18(1): 157-180(1993)
  19. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  20. 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)
  21. Anastasia Analyti, Sakti Pramanik: Fast Search in Main Memory Databases. SIGMOD Conference 1992: 215-224
  22. Mark Sullivan, Michael A. Olson: An Index Implementation Supporting Fast Recovery for the POSTGRES Storage System. ICDE 1992: 293-300
  23. Francesca Cesarini, Giovanni Soda: A Dynamic Hash Method with Signature. ACM Trans. Database Syst. 16(2): 309-337(1991)
  24. David Hung-Chang Du, Sheau-Ru Tong: Multilevel Extendible Hashing: A File Structure for Very Large Databases. IEEE Trans. Knowl. Data Eng. 3(3): 357-370(1991)
  25. Gabriel Matsliach: Performance Analysis of File Organizations that Use Multi-Bucket Data Leaves with Partial Expansions. PODS 1991: 164-180
  26. Aris M. Ouksel, Otto Mayer: The Nested Interpolation Based Grid File. MFDBS 1991: 173-187
  27. Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459
  28. Seng Fuat Ou, Alan L. Tharp: Improved Overflow Handling with Linear Hashing. DASFAA 1991: 165-173
  29. Pyung-Chul Kim, Hwan-Ik Choi, Yoon-Joon Lee, Myung-Joon Kim: Design and Implementation of the Multiuser Index-based Data Access System. DASFAA 1991: 156-164
  30. Won Kim, Jorge F. Garza, Nat Ballou, Darrell Woelk: Architecture of the ORION Next-Generation Database System. IEEE Trans. Knowl. Data Eng. 2(1): 109-124(1990)
  31. Charles Severance, Sakti Pramanik, P. Wolberg: Distributed Linear Hashing and Parallel Projection in Main Memory Databases. VLDB 1990: 674-682
  32. John L. Pfaltz, James C. French: Implementing Subscripted Identifiers in Scientific Databases. SSDBM 1990: 80-91
  33. Frank Olken, Doron Rotem, Ping Xu: Random Sampling from Hash Files. SIGMOD Conference 1990: 375-386
  34. H. V. Jagadish: Linear Clustering of Objects with Multiple Atributes. SIGMOD Conference 1990: 332-342
  35. Gabriel Matsliach, Oded Shmueli: Maintaining Bounded Disorder Files in Multiprocessor Multi-Disk Environments. ICDT 1990: 109-125
  36. Dik Lun Lee, Chun-Wu Leng: A Partitioned Signature File Structure for Multiattribute and Text Retrieval. ICDE 1990: 389-397
  37. Henk M. Blanken, Alle IJbema, Paul Meek, Bert van den Akker: The Generalized Grid File: Description and Performance Aspects. ICDE 1990: 380-388
  38. M. V. Ramakrishna, Per-Åke Larson: File Organization Using Composite Perfect Hashing. ACM Trans. Database Syst. 14(2): 231-263(1989)
  39. David Hung-Chang Du, Subbarao Ghanta, Kurt Maly, Suzanne M. Sharrock: An Efficient File Structure for Document Retrieval in the Automated Office Environment. IEEE Trans. Knowl. Data Eng. 1(2): 258-273(1989)
  40. Doron Rotem: Clustered Multiattribute Hash Files. PODS 1989: 225-234
  41. Nabil I. Hachem, P. Bruce Berra: Key-Sequential Access Methods for Very Large Files Derived from Linear Hashing. ICDE 1989: 305-312
  42. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  43. Per-Åke Larson: Linear Hashing with Separators - A Dynamic Hashing Scheme Achieving One-Access Retrieval. ACM Trans. Database Syst. 13(3): 366-388(1988)
  44. Richard J. Enbody, H. C. Du: Dynamic Hashing Schemes. ACM Comput. Surv. 20(2): 85-113(1988)
  45. Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371
  46. Ratko Orlandic, John L. Pfaltz: Compact 0-Complete Trees. VLDB 1988: 372-381
  47. M. V. Ramakrishna: Hashing in Practive, Analysis of Hashing and Universal Hashing. SIGMOD Conference 1988: 191-199
  48. Myoung-Ho Kim, Sakti Pramanik: Optimal File Distribution For Partial Match Retrieval. SIGMOD Conference 1988: 173-182
  49. Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Twin Grid Files: Space Optimizing Access Schemes. SIGMOD Conference 1988: 183-190
  50. Mireille Régnier: Trie Hashing Analysis. ICDE 1988: 377-381
  51. Ekow J. Otoo: Linearizing the Directory Growth in Order Preserving Extendible Hashing. ICDE 1988: 580-588
  52. Hans-Peter Kriegel, Bernhard Seeger: PLOP-Hashing: A Grid File without Directory. ICDE 1988: 369-376
  53. Witold Litwin, Djamel Eddine Zegour, Gérard Lévy: Multilevel Trie Hashing. EDBT 1988: 309-335
  54. Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: The Twin Grid File: A Nearly Space Optimal Index Structure. EDBT 1988: 352-363
  55. C. Thomas Wu, Walter A. Burkhard: Associative Searching in Multiple Storage Units. ACM Trans. Database Syst. 12(1): 38-64(1987)
  56. Michael Stonebraker, Jeff Anton, Eric N. Hanson: Extending a Database System with Procedures. ACM Trans. Database Syst. 12(3): 350-376(1987)
  57. David B. Lomet: Partial Expansions for File Organizations with an Index. ACM Trans. Database Syst. 12(1): 65-84(1987)
  58. Carla Schlatter Ellis: Concurrency in Linear Hashing. ACM Trans. Database Syst. 12(2): 195-217(1987)
  59. Randal C. Nelson, Hanan Samet: A Population Analysis for Hierarchical Data Structures. SIGMOD Conference 1987: 270-277
  60. Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269
  61. William D. Ruchte, Alan L. Tharp: Linear Hashing with Priority Splitting: A Method for Improving the Retrieval Performance of Linear Hashing. ICDE 1987: 2-9
  62. David Hung-Chang Du, Subbarao Ghanta, Kurt Maly, Suzanne M. Sharrock: An Efficient File Structure for Document Retrieval in the Automated Office Environment. ICDE 1987: 165-172
  63. Anil K. Garg, C. C. Gotlieb: Order-Preserving Key Transformations. ACM Trans. Database Syst. 11(2): 213-234(1986)
  64. Brad T. Vander Zanden, Howard M. Taylor, Dina Bitton: Estimating Block Accessses when Attributes are Correlated. VLDB 1986: 119-127
  65. Tobin J. Lehman, Michael J. Carey: A Study of Index Structures for Main Memory Database Management Systems. VLDB 1986: 294-303
  66. Meichun Hsu, Wei-Pang Yang: Concurrent Operations in Extendible Hashing. VLDB 1986: 241-247
  67. Tobin J. Lehman, Michael J. Carey: Query Processing in Main Memory Database Management Systems. SIGMOD Conference 1986: 239-250
  68. Christos Faloutsos: Multiattribute Hashing Using Gray Codes. SIGMOD Conference 1986: 227-238
  69. Ekow J. Otoo: Balanced Multidimensional Extendible Hash Tree. PODS 1986: 100-113
  70. T. S. Yuen, H. C. Du: Dynamic File Organizations For Partial Match Retrieval Based on Linear Hashing. ICDE 1986: 116-123
  71. Michael Stonebraker: Inclusion of New Types in Relational Data Base Systems. ICDE 1986: 262-269
  72. Keith L. Kelley, Marek Rusinkiewicz: Implementation of Multi-Key Extendible Hashing as an Access Method for a Relational DBMS. ICDE 1986: 124-131
  73. Jean-Pierre Cheiney, Pascal Faudemay, Rodolphe Michel: An Extension of Access Paths to Improve Joins and Selections. ICDE 1986: 270-280
  74. Ilsoo Ahn: Towards An Implementation of Database Management Systems with Temporal Support. ICDE 1986: 374-381
  75. Eugene Veklerov: Analysis of Dynamic Hashing with Deferred Splitting. ACM Trans. Database Syst. 10(1): 90-96(1985)
  76. Don S. Batory: Modeling the Storage Architectures of Commercial Database Systems. ACM Trans. Database Syst. 10(4): 463-528(1985)
  77. Christos Faloutsos: Access Methods for Text. ACM Comput. Surv. 17(1): 49-74(1985)
  78. Ekow J. Otoo: A Multidimensional Digital Hashing Scheme for Files With Composite Keys. SIGMOD Conference 1985: 214-229
  79. Kyoji Kawagoe: Modified Dynamic Hashing. SIGMOD Conference 1985: 201-213
  80. Aris M. Ouksel: The Interpolation-Based Grid File. PODS 1985: 20-27
  81. Carla Schlatter Ellis: Concurrency and Linear Hashing. PODS 1985: 1-7
  82. 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)
  83. Hanan Samet: The Quadtree and Related Hierarchical Data Structures. ACM Comput. Surv. 16(2): 187-260(1984)
  84. Wei-Pang Yang, M. W. Du: A Dynamic Perfect Hash Function Defined by an Extended Hash Indicator Table. VLDB 1984: 245-254
  85. Ekow J. Otoo: A Mapping Function for the Directory of a Multidimensional Extendible Hashing. VLDB 1984: 493-506
  86. Peter Kjellberg, Torben U. Zahle: Cascade Hashing. VLDB 1984: 481-492
  87. Patrick Valduriez, Yann Viémont: A Multikey Hashing Scheme Using Predicate Trees. SIGMOD Conference 1984: 107-114
  88. Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190
  89. Walter A. Burkhard: Index Maintenance for Non-Uniform Record Distributions. PODS 1984: 173-179
  90. Georges Gardarin, Patrick Valduriez, Yann Viémont: Predicate Trees: An Approach to Optimize Relational Query Operations. ICDE 1984: 439-444
  91. Kotagiri Ramamohanarao, John W. Lloyd: Partial-Match Retrieval Using Hashing and Descriptors. ACM Trans. Database Syst. 8(4): 552-576(1983)
  92. David B. Lomet: Bounded Index Exponential Hashing. ACM Trans. Database Syst. 8(1): 136-165(1983)
  93. Jack A. Orenstein: A Dynamic Hash File for Random and Sequential Accessing. VLDB 1983: 132-141
  94. Don S. Batory: Index Coding: A Compression Technique for Large Statistical Databases. SSDBM 1983: 306-314
  95. David B. Lomet: A High Performance, Universal, Key Associative Access Method. SIGMOD Conference 1983: 120-133
  96. Aris M. Ouksel, Peter Scheuermann: Storage Mappings for Multidimensional Linear Dynamic Hashing. PODS 1983: 90-105
  97. Carla Schlatter Ellis: Extendible Hashing for Concurrent Operations and Distributed Data. PODS 1983: 106-116
  98. Walter A. Burkhard: Interpolation-Based Index Maintenance. PODS 1983: 76-89
  99. Per-Åke Larson: Performance Analysis of Linear Hashing with Partial Expansions. ACM Trans. Database Syst. 7(4): 566-587(1982)
  100. Don S. Batory, C. C. Gotlieb: A Unifying Model of Physical Databases. ACM Trans. Database Syst. 7(4): 509-539(1982)
  101. Per-Åke Larson: A Single-File Version of Linear Hashing with Partial Expansions. VLDB 1982: 300-309
  102. Sten Andler, I. Ding, Kapali P. Eswaran, Carl Hauser, Won Kim, James W. Mehl, R. Williams: System D: A Distributed System for Availability. VLDB 1982: 33-44
  103. Markku Tamminen: Efficient Spatial Access to a Data Base. SIGMOD Conference 1982: 200-206
  104. Gaston H. Gonnet, Per-Åke Larson: External Hashing with Limited Internal Storage. PODS 1982: 256-261
  105. Michel Scholl: New File Organizations Based on Dynamic Hashing. ACM Trans. Database Syst. 6(1): 194-211(1981)
  106. David B. Lomet: Digital B-Trees. VLDB 1981: 333-344
  107. Witold Litwin: Trie Hashing. SIGMOD Conference 1981: 19-29
  108. Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223
  109. Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232
  110. Mary E. S. Loomis: The 78 CODASYL Database Model: A Comparison with Preceding Specifications. SIGMOD Conference 1980: 30-44
  111. Douglas Comer: Surveyor's Forum: The Tree Branches. ACM Comput. Surv. 11(4): 412(1979)
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:41 2008