Dominik Bez, Florian Kurpicz, Hans-Peter Lehmann, Peter Sanders

arXiv:2212.09562

A minimal perfect hash function (MPHF) is a bijection from a set of objects S to the first |S| integers. It can be used as a building block in databases and data compression. RecSplit [Esposito et al., ALENEX20] is currently the most space efficient practical minimal perfect hash function. Its main building blocks are splittings and bijections. Using a tree-like data structure, RecSplit first splits the input set into small sets of constant size l and then computes a bijection on each leaf. Both splittings and bijections heavily rely on trying multiple hash functions in a brute-force way. We greatly improve the construction time of RecSplit using two orthogonal approaches. On the one hand, we explore the trade-off between (exponential time) brute force and more informed (polynomial time) search heuristics. Rotation fitting hashes the objects in each leaf to two sets and tries to combine them to a bijection by cyclically shifting one set to fill the holes in the other. ShockHash constructs a small cuckoo hash table in each leaf, which is overloaded to hold more objects than the asymptotic maximum. On the other hand, we harness parallelism on the level of bits, vectors, cores, and GPUs. In combination, the resulting improvements yield speedups up to 241 on a CPU and up to 2072 using a GPU. The original RecSplit implementation needs 19 minutes to construct an MPHF for 1 Million objects with 1.56 bits per object. On the GPU, we achieve the same space usage in 1.5 seconds. Given that the speedups are larger than the increase in energy consumption, our implementation is more energy efficient than the original implementation. As a result, our improved RecSplit implementation is now the approach to perfect hashing with the fastest construction time over a wide range of space budgets. Surprisingly, this even holds for rather high space budgets where asymptotically faster methods are available.