ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Virtual Hashing: A Dynamically Changing Hashing.

Witold Litwin: Virtual Hashing: A Dynamically Changing Hashing. VLDB 1978: 517-523
@inproceedings{DBLP:conf/vldb/Litwin78,
  author    = {Witold Litwin},
  editor    = {S. Bing Yao},
  title     = {Virtual Hashing: A Dynamically Changing Hashing},
  booktitle = {Fourth International Conference on Very Large Data Bases, September
               13-15, 1978, West Berlin, Germany},
  publisher = {IEEE Computer Society},
  year      = {1978},
  pages     = {517-523},
  ee        = {db/conf/vldb/Litwin78.html},
  crossref  = {DBLP:conf/vldb/78},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We propose a new type of hashing which we call virtual hashing. In contrast to any known hashing, a virtual hashing may modify its hashing function. Such changes may be performed when collisions arise. A virtual hashing may then find in one disk access, a record such that several accesses would be needed if the function initially chosen for the file was used. We define virtual hashings which practically independently of the number of such records find in one disk access almost each record of the file.

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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

S. Bing Yao (Ed.): Fourth International Conference on Very Large Data Bases, September 13-15, 1978, West Berlin, Germany. IEEE Computer Society 1978
Contents BibTeX

References

[1]
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
[2]
Ian F. Blake, Alan G. Konheim: Big Buckets Are (Are Not) Better! J. ACM 24(4): 591-606(1977) BibTeX
[3]
Carter Bays: The Reallocation of Hash-Coded Tables. Commun. ACM 16(1): 11-14(1973) BibTeX
[4]
Sakti P. Ghosh, Vincent Y. Lum: Analysis of Collisions when Hashing by Division. Inf. Syst. 1(1): 15-22(1975) BibTeX
[5]
...
[6]
...
[7]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[8]
...
[9]
...
[10]
...
[11]
...
[12]
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
[13]
...
[14]
...
[15]
Arnold L. Rosenberg, Larry J. Stockmeyer: Hashing Schemes for Extendible Arrays. J. ACM 24(2): 199-221(1977) BibTeX
[16]
Ben Shneiderman: Optimum Data Base Reorganization Points. Commun. ACM 16(6): 362-365(1973) BibTeX
[17]
Renzo Sprugnoli: Perfect Hashing Functions: A Single Probe Retrieving Method for Static Sets. Commun. ACM 20(11): 841-850(1977) BibTeX

Referenced by

  1. Gunter Saake, Andreas Heuer: Datenbanken: Implementierungstechniken. MITP-Verlag 1999, ISBN 3-8266-0513-6
    Contents
  2. Francesca Cesarini, Giovanni Soda: A Dynamic Hash Method with Signature. ACM Trans. Database Syst. 16(2): 309-337(1991)
  3. 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)
  4. Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459
  5. 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)
  6. Per-Åke Larson: Linear Hashing with Separators - A Dynamic Hashing Scheme Achieving One-Access Retrieval. ACM Trans. Database Syst. 13(3): 366-388(1988)
  7. M. V. Ramakrishna, P. Mukhopadhyay: Analysis of Bounded Disorder File Organization. PODS 1988: 117-125
  8. Witold Litwin, Djamel Eddine Zegour, Gérard Lévy: Multilevel Trie Hashing. EDBT 1988: 309-335
  9. C. Thomas Wu, Walter A. Burkhard: Associative Searching in Multiple Storage Units. ACM Trans. Database Syst. 12(1): 38-64(1987)
  10. David B. Lomet: Partial Expansions for File Organizations with an Index. ACM Trans. Database Syst. 12(1): 65-84(1987)
  11. 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
  12. T. S. Yuen, H. C. Du: Dynamic File Organizations For Partial Match Retrieval Based on Linear Hashing. ICDE 1986: 116-123
  13. Witold Litwin, David B. Lomet: The Bounded Disorder Access Method. ICDE 1986: 38-48
  14. Keith L. Kelley, Marek Rusinkiewicz: Implementation of Multi-Key Extendible Hashing as an Access Method for a Relational DBMS. ICDE 1986: 124-131
  15. Jean-Pierre Cheiney, Pascal Faudemay, Rodolphe Michel: An Extension of Access Paths to Improve Joins and Selections. ICDE 1986: 270-280
  16. Eugene Veklerov: Analysis of Dynamic Hashing with Deferred Splitting. ACM Trans. Database Syst. 10(1): 90-96(1985)
  17. Kyoji Kawagoe: Modified Dynamic Hashing. SIGMOD Conference 1985: 201-213
  18. Wei-Pang Yang, M. W. Du: A Dynamic Perfect Hash Function Defined by an Extended Hash Indicator Table. VLDB 1984: 245-254
  19. Peter Kjellberg, Torben U. Zahle: Cascade Hashing. VLDB 1984: 481-492
  20. Patrick Valduriez, Yann Viémont: A Multikey Hashing Scheme Using Predicate Trees. SIGMOD Conference 1984: 107-114
  21. Don S. Batory: Index Coding: A Compression Technique for Large Statistical Databases. SSDBM 1983: 306-314
  22. Walter A. Burkhard: Interpolation-Based Index Maintenance. PODS 1983: 76-89
  23. Per-Åke Larson: Performance Analysis of Linear Hashing with Partial Expansions. ACM Trans. Database Syst. 7(4): 566-587(1982)
  24. Don S. Batory, C. C. Gotlieb: A Unifying Model of Physical Databases. ACM Trans. Database Syst. 7(4): 509-539(1982)
  25. Per-Åke Larson: A Single-File Version of Linear Hashing with Partial Expansions. VLDB 1982: 300-309
  26. Gaston H. Gonnet, Per-Åke Larson: External Hashing with Limited Internal Storage. PODS 1982: 256-261
  27. Michel Scholl: New File Organizations Based on Dynamic Hashing. ACM Trans. Database Syst. 6(1): 194-211(1981)
  28. David B. Lomet: Digital B-Trees. VLDB 1981: 333-344
  29. Witold Litwin: Trie Hashing. SIGMOD Conference 1981: 19-29
  30. Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223
  31. Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232
  32. 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)
  33. Douglas Comer: Surveyor's Forum: The Tree Branches. ACM Comput. Surv. 11(4): 412(1979)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings (1977-1981): Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:04 2009