Modernes Hashing:Platz- und zeiteffiziente Suchstrukturen und Simulation von Zufälligkeit mit dem Mehrfunktionen-Paradigma

• Applicant: Professor Dr. Martin Dietzfelbinger
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2014
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 60576965

Das „ two-choice paradigm" oder „ balanced allocation paradigm" („Mehrfunktionen- Paradigma") ist in verschiedenen algorithmischen Zusammenhängen von grundlegender Bedeutung: Jedem Namen („Schlüssel") aus einem Namensbereich („Universum'') wird eine kleine Anzahl leicht zu berechnender zufälliger Indizes („Hashfunktions-Werte") in einem Indexbereich zugeordnet. Der Ansatz wird u.a. dazu benutzt, um mit geringem Speicherplatzbedarf und konstanter Zugriffszeit fundamentale Datenstrukturen („Wörterbuch", „Bloom-Filter", „Minimale Perfekte Hashfunktion") zu implementieren. Ziele des Forschungsvorhabens sind: (1) Die Analysemethoden sollen verfeinert und methodisch erweitert werden, um die Wirkungsweise des Mehrfunktionen-Paradigmas noch genauer zu verstehen und um zu möglichst optimal platzeffizienten Strukturen zu gelangen. (2) Für einige Anwendungen des Mehrfunktionen- Paradigmas wird idealisierend angenommen, dass zufällige Hashfunktionen kostenlos gegeben sind. Die Implikationen, Anwendungsmöglichkeiten und Grenzen eines neuen Ansatzes („split-and-share"), der diese Zufälligkeit algorithmisch bereitstellt, sollen theoretisch und experimentell untersucht werden. (3) Das Zusammenwirken von einfachen, effizient auswertbaren Hashfunktionen mit dem Mehrfunktionen- Paradigma soll im Detail untersucht werden.

• DFG Programme: Research Grants