Linear Hashing with Separators - A Dynamic Hashing Scheme Achieving One-Access Retrieval.

Per-Åke Larson: Linear Hashing with Separators - A Dynamic Hashing Scheme Achieving One-Access Retrieval. ACM Trans. Database Syst. 13(3): 366-388(1988)

@article{DBLP:journals/tods/Larson88,
  author    = {Per-{\AA}ke Larson},
  title     = {Linear Hashing with Separators - A Dynamic Hashing Scheme Achieving
               One-Access Retrieval},
  journal   = {ACM Trans. Database Syst.},
  volume    = {13},
  number    = {3},
  year      = {1988},
  pages     = {366-388},
  ee        = {http://doi.acm.org/10.1145/44498.44500, db/journals/tods/Larson88.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

A new dynamic hashing scheme is presented. Its most outstanding feature is that any record can be retrieved in exactly one disk access. This is achieved by using a small amount of supplemental internal storage that stores enough information to uniquely determine the current location of any record. The amount of internal storage required is small: typically one byte for each page of the file. The necessary address computation, insertion, and expansion algorithms are presented and the performance is studied by means of simulation. The new method is the first practical method offering one-access retrieval for large dynamic files.

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.

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]: 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
[2]: Gaston H. Gonnet, Per-Åke Larson: External hashing with limited internal storage. J. ACM 35(1): 161-184(1988) BibTeX
[3]: Kyoji Kawagoe: Modified Dynamic Hashing. SIGMOD Conference 1985: 201-213 BibTeX
[4]: Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[5]: Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978) BibTeX
[6]: Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232 BibTeX
[7]: Per-Åke Larson: Performance Analysis of Linear Hashing with Partial Expansions. ACM Trans. Database Syst. 7(4): 566-587(1982) BibTeX
[8]: Per-Åke Larson: Linear Hashing with Overflow-Handling by Linear Probing. ACM Trans. Database Syst. 10(1): 75-89(1985) BibTeX
[9]: Per-Åke Larson, Ajay Kajla: File Organization: Implementation of a Method Guaranteeing Retrieval in One Access. Commun. ACM 27(7): 670-677(1984) BibTeX
[10]: Witold Litwin: Virtual Hashing: A Dynamically Changing Hashing. VLDB 1978: 517-523 BibTeX
[11]: Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
[12]: ...
[13]: Kotagiri Ramamohanarao, John W. Lloyd: Dynamic Hashing Schemes. Comput. J. 25(4): 478-485(1982) BibTeX

Referenced by

C. Mohan: Repeating History Beyond ARIES. VLDB 1999: 1-17
Ye-In Chang: Alternating Hashing for Expansible Files. IEEE Trans. Knowl. Data Eng. 9(1): 179-185(1997)
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
C. Mohan: ARIES/LHS: A Concurrency Control and Recovery Method Using Write-Ahead Logging for Linear Hashing with Separators. ICDE 1993: 243-252
Anastasia Analyti, Sakti Pramanik: Fast Search in Main Memory Databases. SIGMOD Conference 1992: 215-224
Seng Fuat Ou, Alan L. Tharp: Improved Overflow Handling with Linear Hashing. DASFAA 1991: 165-173

BibTeX

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