Linear Hashing: A New Tool for File and Table Addressing.

@inproceedings{DBLP:conf/vldb/Litwin80,
  author    = {Witold Litwin},
  title     = {Linear Hashing: A New Tool for File and Table Addressing},
  booktitle = {Sixth International Conference on Very Large Data Bases, October
               1-3, 1980, Montreal, Quebec, Canada, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1980},
  pages     = {212-223},
  ee        = {db/conf/vldb/Litwin80.html},
  crossref  = {DBLP:conf/vldb/80},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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

[AHO75]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX

[BLA77]

Ian F. Blake, Alan G. Konheim: Big Buckets Are (Are Not) Better! J. ACM 24(4): 591-606(1977) BibTeX

[CAR73]

Carter Bays: The Reallocation of Hash-Coded Tables. Commun. ACM 16(1): 11-14(1973) BibTeX

[COM79]

Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX

[FAG78]

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

[GHO75]

Sakti P. Ghosh, Vincent Y. Lum: Analysis of Collisions when Hashing by Division. Inf. Syst. 1(1): 15-22(1975) BibTeX

[GUI72]

...

[GUI73]

...

[KAR79]

...

[KNO71]

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

[KNU74]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX

[LAR78]

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

[LAR80]

Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232 BibTeX

[LIT77]

...

[LIT77a]

...

[LIT78]

...

[LIT78a]

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

[LIT79]

...

[LIT79a]

...

[LIT80]

Witold Litwin: Linear Hashing: A new Algorithm for Files and Tables Addressing. ICOD 1980: 260-276 BibTeX

[LUM73]

Vincent Y. Lum: General Performance Analysis of Key-to-Address Transformation Methods Using an Abstract File Concept. Commun. ACM 16(10): 603-612(1973) BibTeX

[MAR77]

...

[ROS77]

Arnold L. Rosenberg, Larry J. Stockmeyer: Hashing Schemes for Extendible Arrays. J. ACM 24(2): 199-221(1977) BibTeX

[SCH73]

Ben Shneiderman: Optimum Data Base Reorganization Points. Commun. ACM 16(6): 362-365(1973) BibTeX

[SHO79]

...

[SPR77]

Renzo Sprugnoli: Perfect Hashing Functions: A Single Probe Retrieving Method for Static Sets. Commun. ACM 20(11): 841-850(1977) BibTeX

Referenced by

1. Reinhard Braumandl, Jens Claußen, Alfons Kemper, Donald Kossmann: Functional-Join Processing. VLDB J. 8(3-4): 156-177(2000)
2. Witold Litwin, Thomas J. E. Schwarz: LH*_RS: A High-Availability Scalable Distributed Data Structure using Reed Solomon Codes. SIGMOD Conference 2000: 237-248
3. H. V. Jagadish, Laks V. S. Lakshmanan, Divesh Srivastava: What can Hierarchies do for Data Warehouses? VLDB 1999: 530-541
4. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
5. Ye-In Chang: Alternating Hashing for Expansible Files. IEEE Trans. Knowl. Data Eng. 9(1): 179-185(1997)
6. Witold Litwin, Marie-Anne Neimat, Donovan A. Schneider: LH* - A Scalable, Distributed Data Structure. ACM Trans. Database Syst. 21(4): 480-525(1996)
7. Betty Salzberg: Access Methods. ACM Comput. Surv. 28(1): 117-120(1996)
8. Jonas S. Karlsson, Witold Litwin, Tore Risch: LH*LH: A scalable High Performance Data Structure for Switched Multicomputers. EDBT 1996: 573-591
9. Paolo Ciaccia: Optimal Multi-Block Read Schedule for Partitioned Signature Files. EDBT 1996: 241-255
10. André Eickler, Carsten Andreas Gerlhof, Donald Kossmann: A Performance Evaluation of OID Mapping Techniques. VLDB 1995: 18-29
11. Jukka Teuhola: Effective Clustering of Objects Stored by Linear Hashing. CIKM 1995: 274-280
12. M. V. Ramakrishna: Bounded Disorder File Organization. IEEE Trans. Knowl. Data Eng. 6(1): 79-85(1994)
13. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
14. Pavel Zezula, Paolo Ciaccia, Paolo Tiberio: Hamming Filters: A Dynamic Signature File Organization for Parallel Stores. VLDB 1993: 314-327
15. Witold Litwin, Marie-Anne Neimat, Donovan A. Schneider: LH* - Linear Hashing for Distributed Files. SIGMOD Conference 1993: 327-336
16. 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)
17. Vibby Gottemukkala, Tobin J. Lehman: Locking and Latching in a Memory-Resident Database System. VLDB 1992: 533-544
18. Anastasia Analyti, Sakti Pramanik: Fast Search in Main Memory Databases. SIGMOD Conference 1992: 215-224
19. Francesca Cesarini, Giovanni Soda: A Dynamic Hash Method with Signature. ACM Trans. Database Syst. 16(2): 309-337(1991)
20. 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)
21. Aris M. Ouksel, Otto Mayer: The Nested Interpolation Based Grid File. MFDBS 1991: 173-187
22. Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459
23. Seng Fuat Ou, Alan L. Tharp: Improved Overflow Handling with Linear Hashing. DASFAA 1991: 165-173
24. Charles Severance, Sakti Pramanik, P. Wolberg: Distributed Linear Hashing and Parallel Projection in Main Memory Databases. VLDB 1990: 674-682
25. Frank Olken, Doron Rotem: Random Sampling from Database Files: A Survey. SSDBM 1990: 92-111
26. Frank Olken, Doron Rotem, Ping Xu: Random Sampling from Hash Files. SIGMOD Conference 1990: 375-386
27. H. V. Jagadish: Linear Clustering of Objects with Multiple Atributes. SIGMOD Conference 1990: 332-342
28. Gabriel Matsliach, Oded Shmueli: Maintaining Bounded Disorder Files in Multiprocessor Multi-Disk Environments. ICDT 1990: 109-125
29. M. V. Ramakrishna, Per-Åke Larson: File Organization Using Composite Perfect Hashing. ACM Trans. Database Syst. 14(2): 231-263(1989)
30. Jaideep Srivastava, Jack S. Eddy Tan, Vincent Y. Lum: TBSAM: An Access Method for Efficient Processing of Statistical Queries. IEEE Trans. Knowl. Data Eng. 1(4): 414-423(1989)
31. 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)
32. Stavros Christodoulakis, Daniel Alexander Ford: Retrieval Performance Versus Disc Space Utilization on WORM Optical Discs. SIGMOD Conference 1989: 306-314
33. Nabil I. Hachem, P. Bruce Berra: Key-Sequential Access Methods for Very Large Files Derived from Linear Hashing. ICDE 1989: 305-312
34. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
35. David B. Lomet: A Simple Bounded Disorder File Organization with Good Performance. ACM Trans. Database Syst. 13(4): 525-551(1988)
36. Per-Åke Larson: Linear Hashing with Separators - A Dynamic Hashing Scheme Achieving One-Access Retrieval. ACM Trans. Database Syst. 13(3): 366-388(1988)
37. Richard J. Enbody, H. C. Du: Dynamic Hashing Schemes. ACM Comput. Surv. 20(2): 85-113(1988)
38. Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371
39. Ratko Orlandic, John L. Pfaltz: Compact 0-Complete Trees. VLDB 1988: 372-381
40. M. V. Ramakrishna: Hashing in Practive, Analysis of Hashing and Universal Hashing. SIGMOD Conference 1988: 191-199
41. Myoung-Ho Kim, Sakti Pramanik: Optimal File Distribution For Partial Match Retrieval. SIGMOD Conference 1988: 173-182
42. M. V. Ramakrishna, P. Mukhopadhyay: Analysis of Bounded Disorder File Organization. PODS 1988: 117-125
43. Ekow J. Otoo: Linearizing the Directory Growth in Order Preserving Extendible Hashing. ICDE 1988: 580-588
44. Edward Omiecinski: Concurrent Storage Structure Conversion: from B+ Tree to Linear Hash File. ICDE 1988: 589-596
45. Hans-Peter Kriegel, Bernhard Seeger: PLOP-Hashing: A Grid File without Directory. ICDE 1988: 369-376
46. Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Globally Order Preserving Multidimensional Linear Hashing. ICDE 1988: 572-579
47. Witold Litwin, Djamel Eddine Zegour, Gérard Lévy: Multilevel Trie Hashing. EDBT 1988: 309-335
48. C. Thomas Wu, Walter A. Burkhard: Associative Searching in Multiple Storage Units. ACM Trans. Database Syst. 12(1): 38-64(1987)
49. David B. Lomet: Partial Expansions for File Organizations with an Index. ACM Trans. Database Syst. 12(1): 65-84(1987)
50. Carla Schlatter Ellis: Concurrency in Linear Hashing. ACM Trans. Database Syst. 12(2): 195-217(1987)
51. 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
52. Hans-Peter Kriegel, Bernhard Seeger: Multidimensional Dynamic Quantile Hashing is Very Efficient for Non-Uniform Record Distributions. ICDE 1987: 10-17
53. 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
54. Anil K. Garg, C. C. Gotlieb: Order-Preserving Key Transformations. ACM Trans. Database Syst. 11(2): 213-234(1986)
55. Tobin J. Lehman, Michael J. Carey: A Study of Index Structures for Main Memory Database Management Systems. VLDB 1986: 294-303
56. Tobin J. Lehman, Michael J. Carey: Query Processing in Main Memory Database Management Systems. SIGMOD Conference 1986: 239-250
57. Christos Faloutsos: Multiattribute Hashing Using Gray Codes. SIGMOD Conference 1986: 227-238
58. John T. Robinson: Order Preserving Linear Hashing Using Dynamic Key Statistics. PODS 1986: 91-99
59. Ekow J. Otoo: Balanced Multidimensional Extendible Hash Tree. PODS 1986: 100-113
60. Hans-Peter Kriegel, Bernhard Seeger: Multidimensional Order Preserving Linear Hashing with Partial Expansions. ICDT 1986: 203-220
61. T. S. Yuen, H. C. Du: Dynamic File Organizations For Partial Match Retrieval Based on Linear Hashing. ICDE 1986: 116-123
62. Michael Stonebraker: Inclusion of New Types in Relational Data Base Systems. ICDE 1986: 262-269
63. Witold Litwin, David B. Lomet: The Bounded Disorder Access Method. ICDE 1986: 38-48
64. Keith L. Kelley, Marek Rusinkiewicz: Implementation of Multi-Key Extendible Hashing as an Access Method for a Relational DBMS. ICDE 1986: 124-131
65. Jean-Pierre Cheiney, Pascal Faudemay, Rodolphe Michel: An Extension of Access Paths to Improve Joins and Selections. ICDE 1986: 270-280
66. Ilsoo Ahn: Towards An Implementation of Database Management Systems with Temporal Support. ICDE 1986: 374-381
67. Per-Åke Larson: Linear Hashing with Overflow-Handling by Linear Probing. ACM Trans. Database Syst. 10(1): 75-89(1985)
68. Ekow J. Otoo: A Multidimensional Digital Hashing Scheme for Files With Composite Keys. SIGMOD Conference 1985: 214-229
69. Kyoji Kawagoe: Modified Dynamic Hashing. SIGMOD Conference 1985: 201-213
70. Aris M. Ouksel: The Interpolation-Based Grid File. PODS 1985: 20-27
71. Carla Schlatter Ellis: Concurrency and Linear Hashing. PODS 1985: 1-7
72. Kotagiri Ramamohanarao, Ron Sacks-Davis: Recursive Linear Hashing. ACM Trans. Database Syst. 9(3): 369-391(1984)
73. Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984)
74. Hanan Samet: The Quadtree and Related Hierarchical Data Structures. ACM Comput. Surv. 16(2): 187-260(1984)
75. Wei-Pang Yang, M. W. Du: A Dynamic Perfect Hash Function Defined by an Extended Hash Indicator Table. VLDB 1984: 245-254
76. Ekow J. Otoo: A Mapping Function for the Directory of a Multidimensional Extendible Hashing. VLDB 1984: 493-506
77. James K. Mullin: Unified Dynamic Hashing. VLDB 1984: 473-480
78. Peter Kjellberg, Torben U. Zahle: Cascade Hashing. VLDB 1984: 481-492
79. Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190
80. Kee S. Ong: Synapse Approach to Database Recovery. PODS 1984: 79-85
81. Walter A. Burkhard: Index Maintenance for Non-Uniform Record Distributions. PODS 1984: 173-179
82. Georges Gardarin, Patrick Valduriez, Yann Viémont: Predicate Trees: An Approach to Optimize Relational Query Operations. ICDE 1984: 439-444
83. Kotagiri Ramamohanarao, John W. Lloyd: Partial-Match Retrieval Using Hashing and Descriptors. ACM Trans. Database Syst. 8(4): 552-576(1983)
84. David B. Lomet: Bounded Index Exponential Hashing. ACM Trans. Database Syst. 8(1): 136-165(1983)
85. Jack A. Orenstein: A Dynamic Hash File for Random and Sequential Accessing. VLDB 1983: 132-141
86. David B. Lomet: A High Performance, Universal, Key Associative Access Method. SIGMOD Conference 1983: 120-133
87. Aris M. Ouksel, Peter Scheuermann: Storage Mappings for Multidimensional Linear Dynamic Hashing. PODS 1983: 90-105
88. Walter A. Burkhard: Interpolation-Based Index Maintenance. PODS 1983: 76-89
89. Per-Åke Larson: Performance Analysis of Linear Hashing with Partial Expansions. ACM Trans. Database Syst. 7(4): 566-587(1982)
90. Per-Åke Larson: A Single-File Version of Linear Hashing with Partial Expansions. VLDB 1982: 300-309
91. 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
92. Witold Litwin: Trie Hashing. SIGMOD Conference 1981: 19-29
93. J. R. Jordan, J. Banerjee, R. B. Batman: Precision Locks. SIGMOD Conference 1981: 143-147
94. Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232