@inproceedings{8046070cdb834274849b61451c3870c8,
title = "Graphs, Hypergraphs and Hashing",
abstract = "Minimal perfect hash functions are used for memory efficient storage and fast retrieval of items from static sets. We present an infinite family of efficient and practical algorithms for generating minimal perfect hash functions which allow an arbitrary order to be specified for the keys. We show that almost all members of the family are space and time optimal, and we identify the one with minimum constants. Members of the family generate a minimal perfect hash function in two steps. First a special kind of function into an r-graph is computed probabilistically. Then this function is refined deterministically to a minimal perfect hash function. We give strong practical and theoretical evidence that the first step uses linear random time. The second step runs in linear deterministic time. The family not only has theoretical importance, but also offers the fastest known method for generating perfect hash functions.",
author = "George Havas and Majewski, {Bohdan S.} and Wormald, {Nicholas C.} and Czech, {Zbigniew J.}",
year = "1994",
language = "English",
isbn = "9783540578994",
volume = "790 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag London Ltd.",
pages = "153--165",
booktitle = "Graph-Theoretic Concepts in Computer Science - 19th International Workshop, WG 1993, Proceedings",
address = "Germany",
note = "19th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1993 ; Conference date: 16-06-1993 Through 18-06-1993",
}