ACM SIGMOD Anthology TODS dblp.uni-trier.de

Performance Analysis of Linear Hashing with Partial Expansions.

Per-Åke Larson: Performance Analysis of Linear Hashing with Partial Expansions. ACM Trans. Database Syst. 7(4): 566-587(1982)
@article{DBLP:journals/tods/Larson82,
  author    = {Per-{\AA}ke Larson},
  title     = {Performance Analysis of Linear Hashing with Partial Expansions},
  journal   = {ACM Trans. Database Syst.},
  volume    = {7},
  number    = {4},
  year      = {1982},
  pages     = {566-587},
  ee        = {http://doi.acm.org/10.1145/319758.319763, db/journals/tods/Larson82.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Linear hashing with partial expansions is a new file organization primarily intended for files which grow and shrink dynamically. This paper presents a mathematical analysis of the expected performance of the new scheme. The following performance measures are considered: length of successful and unsuccessful searches, accesses required to insert or delete a record, and the size of the overflow area. The performance is cyclical. For all performance measures, the necessary formulas are derived for computing the expected performance at any point of a cycle and the average over a cycle. Furthermore, the expected worst case in connection with searching is analyzed. The overall performance depends on several file parameters. The numerical results show that for many realistic parameter combinations the performance is expected to be extremely good. Even the longest search is expected to be of quite reasonable length.

Copyright © 1982 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]
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: Expected Length of the Longest Probe Sequence in Hash Code Searching. J. ACM 28(2): 289-304(1981) BibTeX
[3]
Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978) BibTeX
[4]
Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232 BibTeX
[5]
Witold Litwin: Virtual Hashing: A Dynamically Changing Hashing. VLDB 1978: 517-523 BibTeX
[6]
...
[7]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
[8]
...

Referenced by

  1. Ye-In Chang: Alternating Hashing for Expansible Files. IEEE Trans. Knowl. Data Eng. 9(1): 179-185(1997)
  2. 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)
  3. Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459
  4. Frank Olken, Doron Rotem, Ping Xu: Random Sampling from Hash Files. SIGMOD Conference 1990: 375-386
  5. Nabil I. Hachem, P. Bruce Berra: Key-Sequential Access Methods for Very Large Files Derived from Linear Hashing. ICDE 1989: 305-312
  6. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  7. Per-Åke Larson: Linear Hashing with Separators - A Dynamic Hashing Scheme Achieving One-Access Retrieval. ACM Trans. Database Syst. 13(3): 366-388(1988)
  8. Richard J. Enbody, H. C. Du: Dynamic Hashing Schemes. ACM Comput. Surv. 20(2): 85-113(1988)
  9. Soon Myoung Chung, P. Bruce Berra: A Comparison of Concatenated and Superimposed Code Word Surrogate Files for Very Large Data/Knowledge Bases. EDBT 1988: 364-387
  10. C. Thomas Wu, Walter A. Burkhard: Associative Searching in Multiple Storage Units. ACM Trans. Database Syst. 12(1): 38-64(1987)
  11. Stavros Christodoulakis: Analysis of Retrieval Performance for Records and Objects Using Optical Disk Technology. ACM Trans. Database Syst. 12(2): 137-169(1987)
  12. Christos Faloutsos: Multiattribute Hashing Using Gray Codes. SIGMOD Conference 1986: 227-238
  13. John T. Robinson: Order Preserving Linear Hashing Using Dynamic Key Statistics. PODS 1986: 91-99
  14. Per-Åke Larson: Linear Hashing with Overflow-Handling by Linear Probing. ACM Trans. Database Syst. 10(1): 75-89(1985)
  15. Kotagiri Ramamohanarao, Ron Sacks-Davis: Recursive Linear Hashing. ACM Trans. Database Syst. 9(3): 369-391(1984)
  16. Wei-Pang Yang, M. W. Du: A Dynamic Perfect Hash Function Defined by an Extended Hash Indicator Table. VLDB 1984: 245-254
  17. Walter A. Burkhard: Index Maintenance for Non-Uniform Record Distributions. PODS 1984: 173-179
  18. Per-Åke Larson: A Single-File Version of Linear Hashing with Partial Expansions. VLDB 1982: 300-309
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:50 2008