Linear Hashing with Partial Expansions.

@inproceedings{DBLP:conf/vldb/Larson80,
  author    = {Per-{\AA}ke Larson},
  title     = {Linear Hashing with Partial Expansions},
  booktitle = {Sixth International Conference on Very Large Data Bases, October
               1-3, 1980, Montreal, Quebec, Canada, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1980},
  pages     = {224-232},
  ee        = {db/conf/vldb/Larson80.html},
  crossref  = {DBLP:conf/vldb/80},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A new method for organising dynamic files is presented and its performance is analysed. The scheme is a generalization of W. Litwin's linear (virtual) hashing. The amount of storage space allocated to the file grows and shrinks in a simple fashion according to the number of records actually stored in the file. The storage utilisation is controlled and constantly kept equal to a threshold selected by the user. Because no index or other form of access table is used, retrieval of a record requires only one access in most cases. The analysis reveals that an average search length in the range 1.1 - 1.2 accesses can easily be achieved, even for storage utilisations as high as 85 - 90 per cent.

Key words: file organisation, access methods, hashing, searching, dynamic storage allocation, dynamic hashing schemes, virtual hashing, linear hashing, analysis of algorithms. gracefully.

Copyright © 1980 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

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/vldb7588 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/aDVD1 or /dvd

Printed Edition

References

[1]

...

[2]

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)

[3]

Gary D. Knott: Expandable Open Addressing Hash Table Storage and Retrieval. SIGFIDET Workshop 1971: 187-206

[4]

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

[5]

...

[6]

Witold Litwin: Virtual Hashing: A Dynamically Changing Hashing. VLDB 1978: 517-523

[7]

...

[8]

...

[9]

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

Last update Mon Sep 17 22:00:35 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page