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

• Antragsteller: Professor Dr. Martin Dietzfelbinger
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2014
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 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-Verfahren: Sachbeihilfen