ACM SIGMOD Anthology TODS dblp.uni-trier.de

File Organization Using Composite Perfect Hashing.

M. V. Ramakrishna, Per-Åke Larson: File Organization Using Composite Perfect Hashing. ACM Trans. Database Syst. 14(2): 231-263(1989)
@article{DBLP:journals/tods/RamakrishnaL89,
  author    = {M. V. Ramakrishna and
               Per-{\AA}ke Larson},
  title     = {File Organization Using Composite Perfect Hashing},
  journal   = {ACM Trans. Database Syst.},
  volume    = {14},
  number    = {2},
  year      = {1989},
  pages     = {231-263},
  ee        = {http://doi.acm.org/10.1145/63500.63521, db/journals/tods/RamakrishnaL89.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Perfect hashing refers to hashing with no overflows. We propose and analyze a composite perfect hashing scheme for large external files. The scheme guarantees retrieval of any record in a single disk access. Insertions and deletions are simple, and the file size may vary considerably without adversely affecting the performance. A simple variant of the scheme supports efficient range searches in addition to being a completely dynamic file organization scheme. These advantages are achieved at the cost of a small amount of additional internal storage and increased cost of insertions.

Copyright © 1989 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]
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]
...
[3]
...
[4]
Larry Carter, Mark N. Wegman: Universal Classes of Hash Functions. J. Comput. Syst. Sci. 18(2): 143-154(1979) BibTeX
[5]
...
[6]
...
[7]
Richard J. Cichelli: Minimal Perfect Hash Functions Made Simple. Commun. ACM 23(1): 17-19(1980) BibTeX
[8]
Gordon V. Cormack, R. Nigel Horspool, M. Kaiserswerth: Practical Perfect Hashing. Comput. J. 28(1): 54-58(1985) BibTeX
[9]
...
[10]
M. W. Du, T. M. Hsieh, K. F. Jea, D. W. Shieh: The Study of a New Perfect Hash Scheme. IEEE Trans. Software Eng. 9(3): 305-313(1983) BibTeX
[11]
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
[12]
...
[13]
...
[14]
...
[15]
David K. Gifford, Alfred Z. Spector: The TWA Reservation System. Commun. ACM 27(7): 649-665(1984) BibTeX
[16]
Gaston H. Gonnet, Per-Åke Larson: External hashing with limited internal storage. J. ACM 35(1): 161-184(1988) BibTeX
[17]
...
[18]
...
[19]
Gerhard Jaeschke: Reciprocal Hashing: A Method for Generating Minimal Perfect Hashing Functions. Commun. ACM 24(12): 829-833(1981) BibTeX
[20]
...
[21]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[22]
Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978) BibTeX
[23]
Per-Åke Larson: Analysis of Uniform Hashing. J. ACM 30(4): 805-819(1983) BibTeX
[24]
Per-Åke Larson, Ajay Kajla: File Organization: Implementation of a Method Guaranteeing Retrieval in One Access. Commun. ACM 27(7): 670-677(1984) BibTeX
[25]
Per-Åke Larson, M. V. Ramakrishna: External Perfect Hashing. SIGMOD Conference 1985: 190-200 BibTeX
[26]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
[27]
David B. Lomet: A Simple Bounded Disorder File Organization with Good Performance. ACM Trans. Database Syst. 13(4): 525-551(1988) BibTeX
[28]
Harry G. Mairson: The Program Complexity of Searching a Table. FOCS 1983: 40-47 BibTeX
[29]
...
[30]
...
[31]
...
[32]
M. V. Ramakrishna, P. Mukhopadhyay: Analysis of Bounded Disorder File Organization. PODS 1988: 117-125 BibTeX
[33]
Thomas J. Sager: A Polynomial Time Generator for Minimal Perfect Hash Functions. Commun. ACM 28(5): 523-532(1985) BibTeX
[34]
Dilip V. Sarwate: A Note on Universal Classes of Hash Functions. Inf. Process. Lett. 10(1): 41-45(1980) BibTeX
[35]
Renzo Sprugnoli: Perfect Hashing Functions: A Single Probe Retrieving Method for Static Sets. Commun. ACM 20(11): 841-850(1977) BibTeX

Referenced by

  1. M. V. Ramakrishna, Justin Zobel: Performance in Practice of String Hashing Functions. DASFAA 1997: 215-224
  2. M. V. Ramakrishna: Bounded Disorder File Organization. IEEE Trans. Knowl. Data Eng. 6(1): 79-85(1994)
  3. Anastasia Analyti, Sakti Pramanik: Fast Search in Main Memory Databases. SIGMOD Conference 1992: 215-224
  4. M. V. Ramakrishna, G. A. Portice: Perfect Hashing Functions for Hardware Applications. ICDE 1991: 464-470
  5. Richard J. Enbody, H. C. Du: Dynamic Hashing Schemes. ACM Comput. Surv. 20(2): 85-113(1988)
  6. M. V. Ramakrishna: Hashing in Practive, Analysis of Hashing and Universal Hashing. SIGMOD Conference 1988: 191-199
  7. M. V. Ramakrishna, P. Mukhopadhyay: Analysis of Bounded Disorder File Organization. PODS 1988: 117-125
  8. M. V. Ramakrishna: An Exact Probability Model for Finite Hash Tables. ICDE 1988: 362-368
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:39:06 2008