Recursive Linear Hashing.

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

@article{DBLP:journals/tods/RamamohanaraoS84,
  author    = {Kotagiri Ramamohanarao and
               Ron Sacks-Davis},
  title     = {Recursive Linear Hashing},
  journal   = {ACM Trans. Database Syst.},
  volume    = {9},
  number    = {3},
  year      = {1984},
  pages     = {369-391},
  ee        = {http://doi.acm.org/10.1145/1270.1285, db/journals/tods/RamamohanaraoS84.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

A modification of linear hashing is proposed for which the conventional use of overflow records is avoided. Furthermore, an implementation of linear hashing is presented for which the amount of physical storage claimed is only fractionally more than the minimum required. This implementation uses a fixed amount of in-core space. Simulation results are given which indicate that even for storage utilizations approaching 95 percent, the average successful search cost for this method is close to one disk access.

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

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/An3-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

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

BibTeX

References

[1]: Per-Åke Larson: Analysis of Repeated Hashing. BIT 20(1): 25-32(1980) BibTeX
[2]: Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232 BibTeX
[3]: Per-Åke Larson: A Single-File Version of Linear Hashing with Partial Expansions. VLDB 1982: 300-309 BibTeX
[4]: Per-Åke Larson: Performance Analysis of Linear Hashing with Partial Expansions. ACM Trans. Database Syst. 7(4): 566-587(1982) BibTeX
[5]: Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
[6]: James K. Mullin: Tightly Controlled Linear Hashing without Separate Overflow Storage. BIT 21(4): 390-400(1981) BibTeX
[7]: Kotagiri Ramamohanarao, John W. Lloyd: Dynamic Hashing Schemes. Comput. J. 25(4): 478-485(1982) BibTeX

Referenced by

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)
Ron Sacks-Davis, Alan J. Kent, Kotagiri Ramamohanarao, James A. Thom, Justin Zobel: Atlas: A Nested Relational Database System for Text Applications. IEEE Trans. Knowl. Data Eng. 7(3): 454-470(1995)
Radek Vingralek, Yuri Breitbart, Gerhard Weikum: Distributed File Organization with Scalable Cost/Performance. SIGMOD Conference 1994: 253-264
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)
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)
Nabil I. Hachem, P. Bruce Berra: Key-Sequential Access Methods for Very Large Files Derived from Linear Hashing. ICDE 1989: 305-312
Kotagiri Ramamohanarao, John Shepherd, Ron Sacks-Davis: Partial-match Retrieval using Multiple-Key Hashing with Multiple File Copies. DASFAA 1989: 225-232
Richard J. Enbody, H. C. Du: Dynamic Hashing Schemes. ACM Comput. Surv. 20(2): 85-113(1988)
Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Twin Grid Files: Space Optimizing Access Schemes. SIGMOD Conference 1988: 183-190
Hans-Werner Six, Peter Widmayer: Spatial Searching in Geometric Databases. ICDE 1988: 496-503
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
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
T. S. Yuen, H. C. Du: Dynamic File Organizations For Partial Match Retrieval Based on Linear Hashing. ICDE 1986: 116-123
Per-Åke Larson: Linear Hashing with Overflow-Handling by Linear Probing. ACM Trans. Database Syst. 10(1): 75-89(1985)

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]