A Faster Algorithm for Constructing Minimal Perfect Hash Functions

Edward A. Fox, Qi Chen, Lenwood S. HeathSIGIR 1992 · OpenReview

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.
BibTeX
@inproceedings{fox1992faster,
  author = {Edward A. Fox and Qi Chen and Lenwood S. Heath},
  title = {{A Faster Algorithm for Constructing Minimal Perfect Hash Functions}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {1992},
  url = {https://openreview.net/forum?id=r14DMSWubS},
}

Loading related content...

Figure