Dynamic Hashing Schemes.

@article{DBLP:journals/csur/EnbodyD88,
  author    = {Richard J. Enbody and
               H. C. Du},
  title     = {Dynamic Hashing Schemes},
  journal   = {ACM Comput. Surv.},
  volume    = {20},
  number    = {2},
  year      = {1988},
  pages     = {85-113},
  ee        = {db/journals/csur/EnbodyD88.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1988 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.

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An4-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

Online Edition: ACM Digital Library

References

[Carter and Wegman 1979]

Larry Carter, Mark N. Wegman: Universal Classes of Hash Functions. J. Comput. Syst. Sci. 18(2): 143-154(1979) BibTeX

[Comer and Sethi 1977]

Douglas Comer, Ravi Sethi: The Complexity of Trie Index Construction. J. ACM 24(3): 428-440(1977) BibTeX

[Fagin et al. 1979]

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

[Flajolet 1983]

Philippe Flajolet: On the Performance Evaluation of Extendible Hashing and Trie Searching. Acta Inf. 20: 345-369(1983) BibTeX

[Larson 1978]

Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978) BibTeX

[Larson 1980]

Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232 BibTeX

[Larson 1982]

Per-Åke Larson: Performance Analysis of Linear Hashing with Partial Expansions. ACM Trans. Database Syst. 7(4): 566-587(1982) BibTeX

[Larson 1985]

Per-Åke Larson: Linear Hashing with Overflow-Handling by Linear Probing. ACM Trans. Database Syst. 10(1): 75-89(1985) BibTeX

[Litwin 1980]

Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX

[Lomet 1983]

David B. Lomet: Bounded Index Exponential Hashing. ACM Trans. Database Syst. 8(1): 136-165(1983) BibTeX

[Lum et al. 1971]

Vincent Y. Lum, P. S. T. Yuen, M. Dodd: Key-to-Address Transform Techniques: A Fundamental Performance Study on Large Existing Formatted Files. Commun. ACM 14(4): 228-239(1971) BibTeX

[Martin 1979]

...

[Mendelson 1982]

Haim Mendelson: Analysis of Extendible Hashing. IEEE Trans. Software Eng. 8(6): 611-619(1982) BibTeX

[Mullin 1981]

James K. Mullin: Tightly Controlled Linear Hashing without Separate Overflow Storage. BIT 21(4): 390-400(1981) BibTeX

[Mullin 1984]

James K. Mullin: Unified Dynamic Hashing. VLDB 1984: 473-480 BibTeX

[Mullin 1985]

James K. Mullin: Spiral Storage: Efficient Dynamic Hashing with Constant Performance. Comput. J. 28(3): 330-334(1985) BibTeX

[Otto 1988]

Ekow J. Otoo: Linearizing the Directory Growth in Order Preserving Extendible Hashing. ICDE 1988: 580-588 BibTeX

[Ramakrishna and Larson 1988]

M. V. Ramakrishna, Per-Åke Larson: File Organization Using Composite Perfect Hashing. ACM Trans. Database Syst. 14(2): 231-263(1989) BibTeX

[Ramamohanarao and Lloyd 1982]

Kotagiri Ramamohanarao, John W. Lloyd: Dynamic Hashing Schemes. Comput. J. 25(4): 478-485(1982) BibTeX

[Ramamohanarao and Sacks-Davies 1984]

Kotagiri Ramamohanarao, Ron Sacks-Davis: Recursive Linear Hashing. ACM Trans. Database Syst. 9(3): 369-391(1984) BibTeX

[Scholl 1981]

Michel Scholl: New File Organizations Based on Dynamic Hashing. ACM Trans. Database Syst. 6(1): 194-211(1981) BibTeX

[Severance and Duhne 1976]

Dennis G. Severance, Richardo Duhne: A Practitioner's Guide To Addressing Algorithms. Commun. ACM 19(6): 314-326(1976) BibTeX

[Veklerov 1985]

Eugene Veklerov: Analysis of Dynamic Hashing with Deferred Splitting. ACM Trans. Database Syst. 10(1): 90-96(1985) BibTeX

[Vitter 1982]

Jeffrey Scott Vitter: Implementations for Coalesced Hashing. Commun. ACM 25(12): 911-926(1982) BibTeX

Referenced by

1. Reinhard Braumandl, Jens Claußen, Alfons Kemper, Donald Kossmann: Functional-Join Processing. VLDB J. 8(3-4): 156-177(2000)
2. Ye-In Chang: Alternating Hashing for Expansible Files. IEEE Trans. Knowl. Data Eng. 9(1): 179-185(1997)
3. Witold Litwin, Marie-Anne Neimat, Donovan A. Schneider: LH* - A Scalable, Distributed Data Structure. ACM Trans. Database Syst. 21(4): 480-525(1996)
4. 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)
5. André Eickler, Carsten Andreas Gerlhof, Donald Kossmann: A Performance Evaluation of OID Mapping Techniques. VLDB 1995: 18-29
6. Jukka Teuhola: Effective Clustering of Objects Stored by Linear Hashing. CIKM 1995: 274-280
7. Radek Vingralek, Yuri Breitbart, Gerhard Weikum: Distributed File Organization with Scalable Cost/Performance. SIGMOD Conference 1994: 253-264
8. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
9. Witold Litwin, Marie-Anne Neimat, Donovan A. Schneider: LH* - Linear Hashing for Distributed Files. SIGMOD Conference 1993: 327-336
10. C. Mohan: ARIES/LHS: A Concurrency Control and Recovery Method Using Write-Ahead Logging for Linear Hashing with Separators. ICDE 1993: 243-252
11. Keh-Chang Guh, Clement T. Yu: Efficient Management of Materialized Generalized Transitive Closure in Centralized and Parallel Environments. IEEE Trans. Knowl. Data Eng. 4(4): 371-381(1992)
12. 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)
13. Alexandra Poulovassilis, Carol Small: A Functional Programming Approach to Deductive Databases. VLDB 1991: 491-500
14. Keh-Chang Guh, Chengyu Sun, Clement T. Yu: Real Time Retrieval and Update of Materialized Transitive Closure. ICDE 1991: 690-697
15. Carol Small, Alexandra Poulovassilis: An Overview of PFL. DBPL 1991: 96-110