ACM SIGMOD Anthology TODS dblp.uni-trier.de

Linear Hashing with Overflow-Handling by Linear Probing.

Per-Åke Larson: Linear Hashing with Overflow-Handling by Linear Probing. ACM Trans. Database Syst. 10(1): 75-89(1985)
@article{DBLP:journals/tods/Larson85,
  author    = {Per-{\AA}ke Larson},
  title     = {Linear Hashing with Overflow-Handling by Linear Probing},
  journal   = {ACM Trans. Database Syst.},
  volume    = {10},
  number    = {1},
  year      = {1985},
  pages     = {75-89},
  ee        = {http://doi.acm.org/10.1145/3148.3324, db/journals/tods/Larson85.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Linear hashing is a file structure for dynamic files. In this paper, a new, simple method for handling overflow records in connection with linear hashing is proposed. The method is based on linear probing and does not rely on chaining. No dedicated overflow area is required. The expansion sequence of liner hashing is modified to improve the performance, which requires changes in the address computation. A new address computation algorithm and an expansion algorithm are given. The performance of the method is studied by simulation. The algorithms for the basic file operations are very simple, and the overall performance is competitive with that of other variants of linear hashing.

Copyright © 1985 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]
Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232 BibTeX
[2]
Per-Åke Larson: Performance Analysis of Linear Hashing with Partial Expansions. ACM Trans. Database Syst. 7(4): 566-587(1982) 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 a Single-File Version of Linear Hashing. Comput. J. 28(3): 319-329(1985) 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
[8]
Kotagiri Ramamohanarao, Ron Sacks-Davis: Recursive Linear Hashing. ACM Trans. Database Syst. 9(3): 369-391(1984) BibTeX

Referenced by

  1. Ye-In Chang: Alternating Hashing for Expansible Files. IEEE Trans. Knowl. Data Eng. 9(1): 179-185(1997)
  2. Jukka Teuhola: Effective Clustering of Objects Stored by Linear Hashing. CIKM 1995: 274-280
  3. Anastasia Analyti, Sakti Pramanik: Fast Search in Main Memory Databases. SIGMOD Conference 1992: 215-224
  4. Francesca Cesarini, Giovanni Soda: A Dynamic Hash Method with Signature. ACM Trans. Database Syst. 16(2): 309-337(1991)
  5. Per-Åke Larson: Linear Hashing with Separators - A Dynamic Hashing Scheme Achieving One-Access Retrieval. ACM Trans. Database Syst. 13(3): 366-388(1988)
  6. Richard J. Enbody, H. C. Du: Dynamic Hashing Schemes. ACM Comput. Surv. 20(2): 85-113(1988)
  7. Hans-Peter Kriegel, Bernhard Seeger: PLOP-Hashing: A Grid File without Directory. ICDE 1988: 369-376
  8. 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
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:56 2008