Accelerating Minimal Perfect Hash Function Construction Using GPU Parallelization

Eine Minimale Perfekte Hashfunktion (MPHF) bildet eine Menge von N Schlüsseln kollisionsfrei auf die Menge [N ] := {0, .., N − 1} ab. Diese Thesis leistet einen signifikanten Beitrag für den folgenden generischen MPHF Konstruktionsalgorithmus. Im ersten Schritt werden die Schlüssel in Buckets unterschiedlicher erwarteter Größe verteilt. Wir zeigen, dass die Wahl der erwarteten Bucketgröße ein Optimierungsproblem darstellt welches durch die Euler-Lagrange Gleichung gelöst werden kann. Dies resultiert in eine signifikante Verbesserung im Vergleich zum derzeitigen Stand der Forschung. ... mehrIm zweiten Schritt werden die Buckets primär in nicht aufsteigender Größe geordnet. Wir zeigen, dass der Platzbedarf verbessert wird wenn Buckets gleicher Größe sekundär in aufsteigender Erwartungsgröße angeordnet werden. Die Buckets werden dann im dritten Schritt in dieser Reihenfolge verarbeitet indem eine Hashfunktion gefunden wird welche alle Schlüssel des Buckets kollisionsfrei auf [N ] abbildet. Abschließend wird für jeden Bucket ein Identifikator der Hashfunktion komprimiert gespeichert. Wir präsentieren eine neue Kompressionstechnik, welche die Identifikatoren in unterschiedliche Enkodierer anordnet, sodass alle Identifikatoren innerhalb eines Enkodierers der gleichen statistischen Verteilung folgen. Dies verbessert die Komprimierbarkeit der Identifikatoren. Wir nutzen die parallele Leistungsfähigkeit von GPUs um die Konstruktion von MPHFs weiter zu beschleunigen. Unsere GPU Implementierung konstruiert eine MPHF mit 1,73 Bits pro Schlüssel in nur 36 ns pro Schlüssel mit einer CPU Abfragezeit von 44 ns. Eine solch geringe Abfragezeit bei gleichzeitig niedrigem Platzbedarf ist nach heutigem Stand, wie z.B. mit PTHash, nicht erreichbar. Eine MPHF, die einen höheren Platzbedarf von 1,88 Bits pro Schlüssel aufweist, wird mit unserer Implementierung 9926 mal schneller konstruiert als durch PTHash. Die meisten unserer Beiträge sind über unsere spezifische Implementierung hinaus anwendbar und können selbst modernste Techniken weiter verbessern.

A Minimal Perfect Hash Function (MPHF) maps a set of N keys to [N ] := {0, .., N − 1} without collisions. This thesis contributes significant advances to the following generic MPHF construction algorithm. In a first step, the keys are distributed into buckets of differ- ent expected sizes. We show that determining the expected bucket sizes is an optimization problem which can be solved using the Euler-Lagrange equation. The optimization sig- nificantly improves performance compared to the state-of-the-art. In a second step, the buckets are primarily ordered by non-increasing size. ... mehrWe demonstrate that ordering buckets of equal size secondarily by increasing expected size improves space consumption. The buckets are processed in that order in a third step by finding a hash function that maps the keys of the bucket to [N ] without collisions. In a last step, an identifier of the hash function of each bucket is stored in a compressed manner. We present a new compression technique which assigns the identifiers to different encoders, such that all identifiers within the encoders follow almost the same statistical distribution. Thereby, improving the compressibility of the identifiers significantly. We harness the power of GPU parallelization to further accelerate MPHF construction. Our GPU implementation constructs an MPHF of 1.73 bits per key in just 36 ns per key with a CPU query time of 44 ns. Such a fast query time and simultaneously low space requirement is unreachable by current state-of-the-art implementations like PTHash. An MPHF that has a higher space consumption of 1.88 bits per key is constructed 9926 times faster by our implementation compared to PTHash. Most of our contributions are applicable beyond our specific implementation and can improve the performance of state-of-the-art approaches like PTHash.