Fast and Space-Efficient Perfect Hashing

From data analytics to machine learning, large amounts of input data become more and more important. The volume of collected data grows continuously. Compact data structures enable efficient access to this data and help with processing. Perfect hashing is a fundamental basis for many compact data structures and is used for example in databases, hash tables, retrieval data structures, and approximate membership data structures. A perfect hash function (PHF) maps a set $S$ of $n$ keys to the first $m$ integers without collisions, and is called minimal perfect (MPHF) if $m=n$. It may map keys that are not in $S$ to an arbitrary value. This makes it possible to store the function without representing the set $S$ itself.

In this dissertation, we present three MPHF construction algorithms. With SIMDRecSplit, we focus on space efficiency, scratching the space lower bound of representing MPHFs. We enhance the existing construction RecSplit through parallelism on many levels - bits, vectors, multicores, and the GPU. As a base case, RecSplit uses brute-force search - here we achieve impressive speedups by replacing several retries with simple bit operations or even table lookups. ... mehrWith SicHash, we aim for a good balance between query and construction performance. SicHash is based on sampling a random graph where the nodes are the output hash values. Each key, hashed with different ordinary hash functions, gives a hyperedge connecting candidate output values. The perfect hash function is given by an orientation of the edges such that the indegree of each node is at most one. SicHash works close to the orientability threshold - the factor $n/m$ below which such an orientation likely exists. With ShockHash, we combine the ideas of SIMDRecSplit and SicHash. We try to orient a graph far above the orientability threshold, which requires retrying with many different graphs. Compared to plain brute-force, this reduces the number of retries massively, leading to more than $2^n$ times faster construction asymptotically. At the same time, it still maintains the asymptotically optimal space consumption.

Monotone minimal perfect hash functions (MMPHFs) retain the natural order of the input keys. After many years in which tree-based structures were predominant, our LeMonHash moves into a novel direction. It is based on learning regularities in the input data and is efficient to query because it uses a flat structure. Finally, as a relaxation of perfect hashing, we present PaCHash - a static external memory hash table for objects of variable size. PaCHash can fetch an object using a single contiguous access to the external memory. For objects of fixed size, this is similar to what is possible using $k$-perfect hashing, where at most $k$ collisions are allowed. However, in some way, PaCHash breaks the space lower bounds of $k$-perfect hashing at the cost of sometimes fetching one external memory block too much.

The approaches presented in this dissertation are a large step forward from the state of the art. Our approaches dominate the majority of the space-time trade-off, as shown by our detailed experimental evaluation, and inspire future research in the area of perfect hashing.