ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

External Perfect Hashing.

Per-Åke Larson, M. V. Ramakrishna: External Perfect Hashing. SIGMOD Conference 1985: 190-200
@inproceedings{DBLP:conf/sigmod/LarsonR85,
  author    = {Per-{\AA}ke Larson and
               M. V. Ramakrishna},
  editor    = {Shamkant B. Navathe},
  title     = {External Perfect Hashing},
  booktitle = {Proceedings of the 1985 ACM SIGMOD International Conference on
               Management of Data, Austin, Texas, May 28-31, 1985},
  publisher = {ACM Press},
  year      = {1985},
  pages     = {190-200},
  ee        = {http://doi.acm.org/10.1145/318898.318916, db/conf/sigmod/LarsonR85.html},
  crossref  = {DBLP:conf/sigmod/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A hashing function is perfect if it does not create any overflow records. The use of perfect hashing functions has previously been studied only for small static sets stored in main memory. In this paper we describe a perfect hashing scheme for large external files which we are currently investigating. The scheme guarantees retrieval of any record in a single disk access. This is achieved at the cost of a small in-core table and increased cost of insertions. We also suggest a policy for limiting the cost of insertions and we study the tradeoff between expected storage utilization, size of the internal table and cost of insertions under this policy. The results obtained so far are very promising. They indicate that it may indeed by possible to design practical perfect hashing schemes for external files based on the suggested approach.

Copyright © 1985 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.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Shamkant B. Navathe (Ed.): Proceedings of the 1985 ACM SIGMOD International Conference on Management of Data, Austin, Texas, May 28-31, 1985. ACM Press 1985 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 14(4)
Contents

Online Edition: ACM Digital Library


References

[CCHL]
Richard J. Cichelli: Minimal Perfect Hash Functions Made Simple. Commun. ACM 23(1): 17-19(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CHNG]
C. C. Chang: The Study of an Ordered Minimal Perfect Hashing Scheme. Commun. ACM 27(4): 384-387(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CRCN]
...
[CRMC]
Gordon V. Cormack, R. Nigel Horspool, M. Kaiserswerth: Practical Perfect Hashing. Comput. J. 28(1): 54-58(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CRTR]
Larry Carter, Mark N. Wegman: Universal Classes of Hash Functions (Extended Abstract). STOC 1977: 106-112 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DVS]
...
[FRDM]
Michael L. Fredman, János Komlós, Endre Szemerédi: Storing a Sparse Table with O(1) Worst Case Access Time. FOCS 1982: 165-169 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GNT]
Gaston H. Gonnet, Per-Åke Larson: External Hashing with Limited Internal Storage. PODS 1982: 256-261 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[JSCH]
Gerhard Jaeschke: Reciprocal Hashing: A Method for Generating Minimal Perfect Hashing Functions. Commun. ACM 24(12): 829-833(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LRSN]
Per-Åke Larson, Ajay Kajla: File Organization: Implementation of a Method Guaranteeing Retrieval in One Access. Commun. ACM 27(7): 670-677(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SPRG]
Renzo Sprugnoli: Perfect Hashing Functions: A Single Probe Retrieving Method for Static Sets. Commun. ACM 20(11): 841-850(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Mon Mar 15 03:54:27 2010 by Michael Ley (ley@uni-trier.de)