Effiziente Adaptive Datenstrukturen

• Antragsteller: Professor Dr. László Kozma
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 430150252

Elementare Datenstrukturen sind kritische Komponenten in der modernen digitalen Infrastruktur, z.B. in Datenbanken, Dateisystemen und Webservern; das effiziente Speichern und Abrufen ist entscheidend in allen datenintensiven Anwendungen. Neben den direkten praktischen Auswirkungen offenbaren Design und Analyse von Datenstrukturen eine reichhaltige mathematische Theorie mit Verbindungen in die Kombinatorik, Informationstheorie, Algebra und Analysis. Adaptive Datenstrukturen verwenden Regelmäßigkeiten in der Eingabe und können daher effizienter sein, als ihre Worst-Case-Analyse voraussagt. Binäre Suchbäume und Heaps sind zwei gut untersuchte und elementare Datenstrukturen mit vielen Anwendungen. Selbst-organisierende Bäume und Heaps sind wegen ihrer Einfachheit besonders attraktiv. Die prominenteste Datenstruktur in dieser Familie ist der von Sleator und Tarjan 1985 entwickelte Splay-Baum. Splay-Bäume haben viele bekannte adaptive Eigenschaften und es wird vermutet, dass sie instanzoptimal (d.h. bis auf einen konstanten Faktor für jede Eingabe so gut wie jeder andere dynamische Baum) sind. Das ist die berühmte "Dynamic Optimality"-Vermutung. Für Heaps wurden in den letzten Jahrzehnten mehrere raffinierte Designs entwickelt. Fibonacci-Heaps und seine Varianten erreichen die theoretisch optimale amortisierte Laufzeit. Im Vergleich zu Suchbäumen ist deutlich weniger über die adaptiven Eigenschaften von Heaps bekannt. Im Allgemeinen sind selbst-organisierende Datenstrukturen nicht vollständig verstanden, da die Werkzeuge fehlen, um ihr Verhalten zu beschreiben. Das Ziel dieses Antrags ist es, das Verständnis von adaptiven Datenstrukturen zu vertiefen. Dabei soll der Fokus auf selbst-organisierende Binäre Suchbäume und Heaps gelegt werden. In vorherigen Arbeiten des Antragstellers, seiner Mitautoren und anderer, wurden mehrere neue Algorithmen, Modelle und Verbindungen zwischen diesen beiden Familien von Datenstrukturen eingeführt. Diese neuen Ergebnisse ermöglichen neuen Techniken, um selbst-organisierende Datenstrukturen zu erforschen und eröffnen neue Forschungsbereiche. Einige der Themen, die wir untersuchen möchten sind:(1) Design und Analyse von Heaps mit adaptiven Eigenschaften und der theoretischen Grenzen der Adaptivität und Effizienz von Heaps. (2) Untersuchung der "Dynamic Optimality"-Vermutung und ihrer zahlreichen Korollare und verwandten Fragenstellungen. (3) Untersuchung möglicher Strukturen in Eingaben an welche sich Datenstrukturen anpassen können, sowie ein Vergleich von Datenstrukturen in Bezug auf ihre adaptiven Eigenschaften. (4) Neuartige Techniken für die Analyse von Datenstrukturen.

• DFG-Verfahren: Sachbeihilfen