KIT | KIT-Bibliothek | Impressum | Datenschutz

Perfect Hash Function Generation on the GPU with RecSplit

Bez, Dominik

Abstract:

Minimale perfekte Hashfunktionen (MPHFs) bilden eine statische Menge S von beliebigen Schlüsseln auf die Menge der ersten |S| natürlichen Zahlen bijektiv ab, d. h., jeder Hashwert wird exakt einmal verwendet. Sie sind in vielen Anwendungen hilfreich, zum Beispiel, um Hashtabellen mit garantiert konstanter Zugriffszeit zu implementieren. MPHFs können sehr kompakt sein — weniger als 2 Bit pro Schlüssel sind möglich. Andererseits sind MPHFs nicht in der Lage zu entscheiden, ob ein gegebener Schlüssel zu S gehört. Zurzeit ist RecSplit die speichereffizienteste MPHF. RecSplit bietet verschiedene Kompromisse zwischen Platzverbrauch, Konstruktionszeit und Anfragezeit an. ... mehr

Abstract (englisch):

Minimal perfect hash functions (MPHFs) map a static set S of arbitrary keys bijectively into the first |S| natural numbers, i.e., each hash value is used exactly once. They are useful in many applications, for example, to implement hash tables with guaranteed constant access time. MPHFs can be very compact — less than 2 bits per key are possible. On the other hand, MPHFs are not able to decide whether a given key is in S or not. Currently, the most space-efficient practical MPHF is RecSplit. It provides various tradeoffs between the space consumption, construction time, and query time. ... mehr


Volltext §
DOI: 10.5445/IR/1000152719
Veröffentlicht am 08.12.2022
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Publikationsjahr 2022
Sprache Englisch
Identifikator KITopen-ID: 1000152719
Verlag Karlsruher Institut für Technologie (KIT)
Umfang XI, 90 S.
Art der Arbeit Abschlussarbeit - Master
Referent/Betreuer Lehmann, Hans-Peter
Kurpicz, Florian
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page