Analyse von Random-Walk Einfügungen in Cuckoo-Hashtabellen und praxisnahe Filter-Datenstrukturen

• Antragsteller: Dr. Stefan Walzer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2021 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 465963632

Dieses Projekt beschäftigt sich mit speichereffizienten hash-basierten Datenstrukturen. Es gibt zwei Teile:Teil A: Seit der ersten Beschreibung durch Pagh und Rodler 2001 hat sich Cuckoo-Hashing als variantenreiche Konstruktionsmöglichkeit für speichereffiziente Wörterbuchdatenstrukturen etabliert. Die natürliche Frage nach der erwarteten Einfügezeit bei Verwendung der Random-Walk-Strategie bleibt auch nach den Analyseansätzen namhafter Forscher in den relevantesten Fällen ungeklärt. Dieses Projekt soll einen neuen Anlauf unternehmen, um eine erwartete Einfügezeit von O(1) zu beweisen. Im Erfolgsfall ist zu hoffen, dass das Resultat auf die wichtigsten Varianten von Cuckoo-Hashing anwendbar ist und womöglich neue Anwendungen befeuert, wo Forscher zuvor aufgrund des Mangels an theoretischen Garantien für Einfügezeiten Zurückhaltung übten.Einen fruchtbaren Ansatzpunkt könnte hierbei die Objective Method bieten, die durch Lelarge et al. Eingang in die Diskussion um Cuckoo-Hashing gefunden hat und dort einige unhandliche kombinatorische Probleme auf handhabbare analytische Probleme reduziert hat.Als erster Meilenstein im Beweis soll der Random-Walk Algorithmus auf schälbaren Cuckoo-Graphen analysiert werden, was angesichts neuer Verteilungen für Hashfunktionen mit hohen resultierenden Schälbarkeitsschwellwerten relevanter geworden ist.Teil B: Filterdatenstrukturen sind im Netzwerk- und Datenbankbereich von immenser Bedeutung. Vor Kurzem wurde eine neuartige Retrieval Datenstruktur von Peter Dillinger (einem Datenbankspezialist von Facebook) aufgegriffen, was zur Entwicklung von Ribbon-Filtern als Alternative zu (statischen) Bloomfiltern führte. Diese senken den Platzverbrauch auf Kosten einer höheren Konstruktionszeit deutlich. Dillingers Implementierung hat bereits Eingang in die verbreitete Datenbanksoftware RocksDB gefunden.Nun soll der Zirkel geschlossen und die von Dillinger entwickelten Verbesserungen zurück in den akademischen Diskurs geholt werden. Dazu gehört die erste formale Beschreibung von Ribbon-Filtern, eine mathematische Analyse seiner asymptotischen Qualitäten, die Erkundung der naheliegenden Varianten und ein Vergleich mit konkurrierenden Ansätzen in praxisrelevanten Anwendungsfällen.

• DFG-Verfahren: Sachbeihilfen