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