Zusammenfassung:

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. Es entsteht ein "Zufallsgraph" oder "Zufallshypergraph". 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.

Projektmitarbeiter: Dipl.-Inf. Michael Rink

Ansprechpartner: Prof. M. Dietzfelbinger