A Faster Algorithm for Constructing Minimal Perfect Hash Functions
Lists
Only you see this
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...