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) BibTeX

[3]

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

[4]

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

[5]

...

[6]

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

[7]

...

[8]

...

[9]

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

Referenced by

1. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
2. Ye-In Chang: Alternating Hashing for Expansible Files. IEEE Trans. Knowl. Data Eng. 9(1): 179-185(1997)
3. Witold Litwin, Marie-Anne Neimat, Donovan A. Schneider: LH* - A Scalable, Distributed Data Structure. ACM Trans. Database Syst. 21(4): 480-525(1996)
4. Hiroshi Ishikawa, Yasuo Yamane, Yoshio Izumida, Nobuaki Kawato: An Object-Oriented Database System Jasmine: Implementation, Application, and Extension. IEEE Trans. Knowl. Data Eng. 8(2): 285-304(1996)
5. Jukka Teuhola: Effective Clustering of Objects Stored by Linear Hashing. CIKM 1995: 274-280
6. Hiroshi Ishikawa, Fumio Suzuki, Fumihiko Kozakura, Akifumi Makinouchi, Mika Miyagishima, Yoshio Izumida, Masaaki Aoshima, Yasuo Yamane: The Model, Language, and Implementation of an Object-Oriented Multimedia Knowledge Base Management System. ACM Trans. Database Syst. 18(1): 1-50(1993)
7. Witold Litwin, Marie-Anne Neimat, Donovan A. Schneider: LH* - Linear Hashing for Distributed Files. SIGMOD Conference 1993: 327-336
8. Anastasia Analyti, Sakti Pramanik: Fast Search in Main Memory Databases. SIGMOD Conference 1992: 215-224
9. Francesca Cesarini, Giovanni Soda: A Dynamic Hash Method with Signature. ACM Trans. Database Syst. 16(2): 309-337(1991)
10. 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)
11. Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459
12. Charles Severance, Sakti Pramanik, P. Wolberg: Distributed Linear Hashing and Parallel Projection in Main Memory Databases. VLDB 1990: 674-682
13. Frank Olken, Doron Rotem: Random Sampling from Database Files: A Survey. SSDBM 1990: 92-111
14. David Hung-Chang Du, Subbarao Ghanta, Kurt Maly, Suzanne M. Sharrock: An Efficient File Structure for Document Retrieval in the Automated Office Environment. IEEE Trans. Knowl. Data Eng. 1(2): 258-273(1989)
15. Ricardo A. Baeza-Yates, Per-Åke Larson: Performance of B+-Trees with Partial Expansions. IEEE Trans. Knowl. Data Eng. 1(2): 248-257(1989)
16. Yasuo Yamane, Mika Narita, Fumihiko Kozakura, Akifumi Makinouchi: Design and Evaluation of a High-Speed Extended Relational Database Engine, XRDB. DASFAA 1989: 52-60
17. David B. Lomet: A Simple Bounded Disorder File Organization with Good Performance. ACM Trans. Database Syst. 13(4): 525-551(1988)
18. Per-Åke Larson: Linear Hashing with Separators - A Dynamic Hashing Scheme Achieving One-Access Retrieval. ACM Trans. Database Syst. 13(3): 366-388(1988)
19. Richard J. Enbody, H. C. Du: Dynamic Hashing Schemes. ACM Comput. Surv. 20(2): 85-113(1988)
20. Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371
21. Ratko Orlandic, John L. Pfaltz: Compact 0-Complete Trees. VLDB 1988: 372-381
22. Myoung-Ho Kim, Sakti Pramanik: Optimal File Distribution For Partial Match Retrieval. SIGMOD Conference 1988: 173-182
23. M. V. Ramakrishna, P. Mukhopadhyay: Analysis of Bounded Disorder File Organization. PODS 1988: 117-125
24. Edward Omiecinski: Concurrent Storage Structure Conversion: from B+ Tree to Linear Hash File. ICDE 1988: 589-596
25. Hans-Peter Kriegel, Bernhard Seeger: PLOP-Hashing: A Grid File without Directory. ICDE 1988: 369-376
26. C. Thomas Wu, Walter A. Burkhard: Associative Searching in Multiple Storage Units. ACM Trans. Database Syst. 12(1): 38-64(1987)
27. David B. Lomet: Partial Expansions for File Organizations with an Index. ACM Trans. Database Syst. 12(1): 65-84(1987)
28. 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
29. Hans-Peter Kriegel, Bernhard Seeger: Multidimensional Dynamic Quantile Hashing is Very Efficient for Non-Uniform Record Distributions. ICDE 1987: 10-17
30. David Hung-Chang Du, Subbarao Ghanta, Kurt Maly, Suzanne M. Sharrock: An Efficient File Structure for Document Retrieval in the Automated Office Environment. ICDE 1987: 165-172
31. Tobin J. Lehman, Michael J. Carey: A Study of Index Structures for Main Memory Database Management Systems. VLDB 1986: 294-303
32. John T. Robinson: Order Preserving Linear Hashing Using Dynamic Key Statistics. PODS 1986: 91-99
33. Hans-Peter Kriegel, Bernhard Seeger: Multidimensional Order Preserving Linear Hashing with Partial Expansions. ICDT 1986: 203-220
34. T. S. Yuen, H. C. Du: Dynamic File Organizations For Partial Match Retrieval Based on Linear Hashing. ICDE 1986: 116-123
35. Witold Litwin, David B. Lomet: The Bounded Disorder Access Method. ICDE 1986: 38-48
36. Per-Åke Larson: Linear Hashing with Overflow-Handling by Linear Probing. ACM Trans. Database Syst. 10(1): 75-89(1985)
37. Ekow J. Otoo: A Multidimensional Digital Hashing Scheme for Files With Composite Keys. SIGMOD Conference 1985: 214-229
38. Kyoji Kawagoe: Modified Dynamic Hashing. SIGMOD Conference 1985: 201-213
39. Kotagiri Ramamohanarao, Ron Sacks-Davis: Recursive Linear Hashing. ACM Trans. Database Syst. 9(3): 369-391(1984)
40. Wei-Pang Yang, M. W. Du: A Dynamic Perfect Hash Function Defined by an Extended Hash Indicator Table. VLDB 1984: 245-254
41. Ekow J. Otoo: A Mapping Function for the Directory of a Multidimensional Extendible Hashing. VLDB 1984: 493-506
42. James K. Mullin: Unified Dynamic Hashing. VLDB 1984: 473-480
43. Peter Kjellberg, Torben U. Zahle: Cascade Hashing. VLDB 1984: 481-492
44. Georges Gardarin, Patrick Valduriez, Yann Viémont: Predicate Trees: An Approach to Optimize Relational Query Operations. ICDE 1984: 439-444
45. Kotagiri Ramamohanarao, John W. Lloyd: Partial-Match Retrieval Using Hashing and Descriptors. ACM Trans. Database Syst. 8(4): 552-576(1983)
46. Aris M. Ouksel, Peter Scheuermann: Storage Mappings for Multidimensional Linear Dynamic Hashing. PODS 1983: 90-105
47. Walter A. Burkhard: Interpolation-Based Index Maintenance. PODS 1983: 76-89
48. Per-Åke Larson: Performance Analysis of Linear Hashing with Partial Expansions. ACM Trans. Database Syst. 7(4): 566-587(1982)
49. Per-Åke Larson: A Single-File Version of Linear Hashing with Partial Expansions. VLDB 1982: 300-309
50. Arvola Chan, Sy Danberg, Stephen Fox, Wen-Te K. Lin, Anil Nori, Daniel R. Ries: Storage and Access Structures to Support a Semantic Data Model. VLDB 1982: 122-130
51. Witold Litwin: Trie Hashing. SIGMOD Conference 1981: 19-29
52. Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223