A Faster Algorithm for Constructing Minimal Perfect Hash Functions.

Edward A. Fox, Qi Fan Chen, Lenwood S. Heath: A Faster Algorithm for Constructing Minimal Perfect Hash Functions. SIGIR 1992: 266-273

@inproceedings{DBLP:conf/sigir/FoxCH92,
  author    = {Edward A. Fox and
               Qi Fan Chen and
               Lenwood S. Heath},
  editor    = {Nicholas J. Belkin and
               Peter Ingwersen and
               Annelise Mark Pejtersen},
  title     = {A Faster Algorithm for Constructing Minimal Perfect Hash Functions},
  booktitle = {Proceedings of the 15th Annual International ACM SIGIR Conference
               on Research and Development in Information Retrieval. Copenhagen,
               Denmark, June 21-24, 1992},
  publisher = {ACM},
  year      = {1992},
  isbn      = {0-89791-523-2},
  pages     = {266-273},
  ee        = {db/conf/sigir/FoxCH92.html},
  crossref  = {DBLP:conf/sigir/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Our previous research on one-probe access to large collections of data indexed by alphanumeric keys has produced the first practical minimal perfect hash functions for this problem. Here, a new algorithm is described for quickly finding minimal perfect hash functions whose specification space is very close to the theoretical lower bound, i.e., around 2 bits per key. The various stages of processing are detailed, along with analytical and empirical results, including timing for a set of over 3.8 million keys that was processed on a NeXTstation in about 6 hours.

Copyright © 1992 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

CDROM Version: Load the CDROM "Volume 2 Issue 3, SIGIR, DASFAA'97, OODBS'86" 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/An2-3 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

BibTeX

Printed Edition

Nicholas J. Belkin, Peter Ingwersen, Annelise Mark Pejtersen (Eds.): Proceedings of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Copenhagen, Denmark, June 21-24, 1992. ACM 1992, ISBN 0-89791-523-2
Contents BibTeX

Online Edition: ACM Digital Library

Citation page

Referenced by

Dimitrios Dervos, P. Linardis, Yannis Manolopoulos: S-Index: a Hybrid Structure for Text Retrieval. ADBIS 1997: 204-209
Dimitrios Dervos, P. Linardis, Yannis Manolopoulos: Perfect Encoding: a Signature Method for Text Retrieval. ADBIS 1996: 176-182

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]