Servicenavigation

Detailseite

Zurück

Projekt Druckansicht

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
 
Erstellungsjahr 2024

Zusammenfassung der Projektergebnisse

Dieses Projekt hatte zwei Teile. Einen theoretischen Teil zu Hashtabellen und einen praktischen Teil zu Filtern. Eine Hashtabelle ist eine grundlegende Datenstruktur zur Speicherung einer Menge von Schlüssel-Wert Paaren, die wir Elemente nennen. Die Herausforderung ist es, alle Elemente kompakt im Speicher zu platzieren, sodass jedes Element anhand seines Schlüssels schnell wiedergefunden werden kann. Die Cuckoohashing Strategie weist jedem Schlüssel über Hashfunktionen mehrere Positionen im Speicher zu, an der ein zugehöriges Element platziert werden darf und wo bei Anfrage des Schlüssels gesucht wird. Wenn zwei Schlüsseln um die gleiche Position konkurrieren, kann so einer von beiden auf eine seiner Alternativpositionen ausweichen. Der naheliegende Random-Walk Algorithmus sieht vor, dass ein Schlüssel im Kollisionsfall eine seiner Alternativpositionen zufällig wählt und dorthin ausweicht, was eine Kaskade weiterer Ausweichbewegungen nach sich ziehen kann. Dieses Projekt hat das Verständnis dieses Zufallsprozesses vertieft, insbesondere was die erwartete Anzahl nötiger Ausweichbewegungen beim Einfügen eines Elements angeht. Diese Anzahl ist unter gewissen Annahmen konstant, wächst also nicht mit der Größe der Hashtabelle. Ein Filter repräsentiert eine Menge von Objekten und hat zur Aufgabe, bei Anfrage eines Objektes zu entscheiden, ob es in der Menge enthalten ist, er antwortet also „JA“ oder „NEIN“. Dem Filter wird hierbei eine kleine Irrtumswahrscheinlichkeit zugestanden: Er darf gelegentlich „JA“ antworten, wenn die korrekte Antwort „NEIN“ ist, aber niemals „NEIN“, wenn die korrekte Antwort „JA“ ist. Durch diese Relaxierung können Filter erheblich kleiner und schneller sein als exakte Mengendatenstrukturen. Liefert der Filter eine „NEIN“-Antwort, so ist diese zuverlässig und ein Zugriff auf eine exakte Datenstruktur ist nicht nötig. Filter haben eine zentrale Rolle in effizienten Datenbanksystemen. Im Projekt wurde ein vielversprechender Ansatz zum Design von Filterdatenstrukturen ausgestaltet und feinoptimiert. Die resultierenden Ribbonfilter haben gute theoretische Eigenschaft und sind in der Praxis erheblich schneller und kompakter als seine Vorläufer.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

© 2026 DFG Kontakt / Impressum / Datenschutz

Textvergrößerung und Kontrastanpassung