Compacting Minimal Perfect Hashing using Symbiotic Random Search

Minimale perfekte Hashfunktionen (MPHFs) sind Datenstrukturen, die eine Menge aus $n$ Schlüsseln bijektiv auf $\{1, \ldots, n\}$ abbilden. Um diese abzuspeichern werden mindestens $n \cdot \log_2 e \approx 1.4427n$ Bits benötigt. Bisherige MPHFs erreichen bis zu 1.489 Bits pro Schlüssel, indem sie geseedete Hashfunktionen finden, welche die Schlüssel wiederholt in zwei gleich große Teile aufteilen und einen Basisfall gesondert handhaben. Allerdings werden durch das individuelle Abspeichern der Seeds bis zu $\log_2 e$ Bits pro Unterteilung verschwendet, selbst bei Verwendung einer entropieoptimalen Codierung. ... mehrWir präsentieren Symbiotic Random Search (SRS) welches dieses Problem durch ein spezielles Suchmuster löst. Durch das Beschränken der Anzahl an Versuchen eine teilende Hashfunktion in einem Anlauf zu finden und durch Backtracking, falls keine Hashfunktion gefunden wurde, erzeugt SRS eine gemeinsame Codierung aller aufteilender Seeds. SRS kann im Durchschnitt beliebig wenige $\omega > 0$ Bits pro Teilung verschwenden. Die erwartete Arbeit dafür ist linear in $1/\omega$. SRS kann immer dann angewandt werden, wenn eine Datenstruktur durch zufälliges Ausprobieren gefunden werden soll, diese Suche Schritt für Schritt vorgenommen werden kann und ein geringer Platzverbrauch ein Ziel ist. SRS-RecSplit – SRS angewandt auf RecSplit – erreicht in Praxis einen Platzverbrauch von 1.442 91 Bits pro Schlüssel bei zumutbarer Konstruktionszeit – nur 0.000 21 Bits Overhead. Für eine ähnliche Konstruktionszeit erreicht es bis zu 1/192 des Overheads des bisherigen Rekordhalters, für einen ähnlichen Overhead ist SRS-RecSplits Konstruktion bis zu 101-mal schneller. Des Weiteren erlaubt SRS-RecSplits theoretische Konstruktionszeit – linear im Kehrwert des Overheads – kleinere Overheads einfacher zu erreichen als es bei seinen Konkurrenten mit einem exponentiellen Zusammenhang der Fall ist.

Minimal perfect hash functions (MPHFs) are data structures that map a set of 𝑛 keys to $\{1, \ldots, n\}$ bijectively. To store them, at least $n \cdot \log_2 e \approx 1.4427n$ bits are necessary. Previous MPHFs reach as low as 1.489 bits per key by finding seeded hash functions that split the keys into two sets of equal size repeatedly and handling a base case. However, storing all those seeds individually - even with an entropy optimal encoding - wastes up to $\log_2 e$ bits per split. We introduce Symbiotic Random Search (SRS) which solves this problem by utilizing a special search pattern. ... mehrBy bounding the number of attempts to find a splitting hash function in one go and backtracking if none was found, SRS creates a combined encoding of all splitting seeds. SRS can waste arbitrarily little $\omega > 0$ bits per split on average. The expected work required for SRS to find such an encoding is linear in $1/\omega$. SRS can be applied whenever a data structure shall be found by trying candidates, this search can be performed step by step and using little space is a goal. SRS-RecSplit - SRS applied to RecSplit - reaches a space usage of 1.442 91 bits per key in practice with reasonable construction time - just 0.000 21 bits overhead. For similar construction time, it reaches as low as 1/192 the space overhead of the previous record holder. For a similar overhead, SRS-RecSplit’s construction is up to 101 times faster. Furthermore, SRS-RecSplit’s theoretical construction time being linear in the inverse overhead makes it reach even smaller overheads more easily than its competitors, which have an exponential relationship between these metrics.