Order-preserving minimal perfect hash functions and information retrieval

Reviewer: Aaron M. Tenenbaum

A perfect hash function h for a set of keys is a hash function such that h k1 ?h k2 for any two keys k 1 and k 2 in the set. Data associated with a key k at location h ( k ) in a table can therefore be located in a single access. The function h is order-preserving if h ( k 1) < h ( k 2) whenever k 1 < k 2 ; h is minimal if the largest value h ( k ) is minimized. This paper demonstrates a practical method for determining order-preserving minimal perfect hash functions for a given set of keys. Such algorithms are extremely important and useful, as the authors describe. While the exposition is clear and detailed, the paper is dependent on an earlier paper that appeared in Communications of the ACM [1]. That paper discusses methods to form minimal perfect hash functions, which are the basis of the methods described here. Without the first paper, this work is impossible to understand. In particular, it is unclear what to do when a trio of hash functions h 0 , h 1 , and h 2 produces duplicate triples for two different keys. The paper contains detailed algorithms (although they are dependent on the algorithms in the earlier paper) and proofs of order preservation and minimality. The two papers together are likely to be extremely valuable to the field of information retrieval. It is regrettable that lack of the horse makes evaluation of the cart problematic.