Perfekte Hashfunktion auf ESA'25 ausgezeichnet

Unsere Consensus-Datenstruktur ermöglicht es, Seeds für randomisierte Datenstrukturen besonders platzeffizient zu speichern. Als Anwendung von Consensus stellen wir die weltweit platzeffizienteste perfekte Hashfunktion vor. Für die Entwicklung von Consensus wurden wir nun auf dem European Symposium on Algorithms (ESA'25) in Warschau mit dem Best Paper Award ausgezeichnet.

Viele randomisierte Datenstrukturen arbeiten nach dem Prinzip, so lange verschiedene Seeds auszuprobieren, bis ein Versuch erfolgreich ist. Haben wir viele solcher Datenstrukturen, wird klassischerweise für jede Teilstruktur der erste funktionierende Seed gespeichert. Wir zeigen, dass dieser Ansatz Speicherplatz verschwendet, selbst wenn die Seeds optimal codiert werden. Unsere neue Consensus-Datenstruktur kombiniert die Suche nach Seeds direkt mit deren Speicherung. Consensus "verwischt" die Speicherorte der einzelnen Seeds, um sowohl Platzverbrauch zu sparen, als auch die Decodierung effizienter zu machen.

Um zu zeigen, wie viel Potenzial in der Idee steckt, betrachten wir als Anwendung minimal perfekte Hashfunktionen. Mit Consensus-RecSplit präsentieren wir die erste minimal perfekte Hashfunktion, deren Konstruktionszeit nur linear im inversen Platz-Overhead wächst. Damit erreichen wir einen Platzverbauch extrem nahe am theoretischen Minimum, während die Konstruktion für größeren Platzverbrauch bis zu zwei Größenordnungen schneller ist als alle vorherigen Verfahren.

Die ESA ist eine der wichtigsten Konferenzen für Algorithmen, dieses Jahr mit 115 akzeptierten Papers. Wir freuen uns, dass unsere Forschung hier überzeugen konnte. Das Paper "Combined Search and Encoding for Seeds, with an Application to Minimal Perfect Hashing" von Hans-Peter Lehmann, Peter Sanders, Stefan Walzer, und Jonatan Ziegler ist als open access frei erhältlich.