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 ...

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/smod7592 or /cdrom

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

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

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

, 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)
[CHNG]: C. C. Chang: The Study of an Ordered Minimal Perfect Hashing Scheme. Commun. ACM 27(4): 384-387(1984)
[CRCN]: ...
[CRMC]: Gordon V. Cormack, R. Nigel Horspool, M. Kaiserswerth: Practical Perfect Hashing. Comput. J. 28(1): 54-58(1985)
[CRTR]: Larry Carter, Mark N. Wegman: Universal Classes of Hash Functions (Extended Abstract). STOC 1977: 106-112
[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
[GNT]: Gaston H. Gonnet, Per-Åke Larson: External Hashing with Limited Internal Storage. PODS 1982: 256-261
[JSCH]: Gerhard Jaeschke: Reciprocal Hashing: A Method for Generating Minimal Perfect Hashing Functions. Commun. ACM 24(12): 829-833(1981)
[LRSN]: Per-Åke Larson, Ajay Kajla: File Organization: Implementation of a Method Guaranteeing Retrieval in One Access. Commun. ACM 27(7): 670-677(1984)
[SPRG]: Renzo Sprugnoli: Perfect Hashing Functions: A Single Probe Retrieving Method for Static Sets. Commun. ACM 20(11): 841-850(1977)