Dekomposition und Dynamische Programmierung für komplexe Berechnungsprobleme

Die Geschichte des Computers und der Elektronischen Datenverarbeitung ist seit ihren Anfängen von zwei zentralen Einsatzgebieten geprägt worden, nämlich einerseits die effiziente Handhabung von großen Datenmengen (z.B. in Datenbankystemen für Lohnverrechnnung, Buchhhaltung, etc.) und andererseits das Abarbeiten von komplexen Algorithmen, die z.B. in Expertensystemen, Diagnose-tools, oder in Spielen wie Schach zum Tragen kommen. Aktuell gewinnen allerdings Fragestellungen die beide Problemfelder umfassen, also komplexe Berechnugen auf großen Daten, eine immer größere Bedeutung. Als ein Beispiel seien hier Plattformen wie Facebook erwähnt, die heutzutage von Hundert Millionen Usern verwendet werden, die ihrerseits in (Freundschafts-)beziehungen zueinander stehen. Ein typisches komplexes Berechnungsproblem in diesem Umfeld wäre nun z.B. das Identifizieren einer (möglichst kleinen) Menge von Benutzern sodass alle Benutzer mittels der Freundschaftsbeziehung direkt erreichbar sind. Weitere Beispiele wären sogenannte Ontologien (z.B. aus dem medizinischen Bereich, wo in SNOMED-CT ca. 311,000 hierarchisch organisierte Konzepte gespeichert sind) und der Bereich der Bio-Informatik, wo es komplexe Moleküle oder Gene zu analysieren gilt. Im Moment sind komplexe Abfragen auf großen Datenmengen ein unüberwindbares Hindernis für Standard- Algorithmen. Dieses kann jedoch überwunden werden, wenn man sich Struktureigenschaften zu Nutze macht, die sich üblicherweise in Probleminstanzen aus konkreten Anwendungsgebieten finden lassen. Tatsächlich sind weder soziale Netzwerke zufällig generierte Graphen noch repräsentieren Ontologien eine beliebige Sammlung von Relationen. Diese Faktum spiegelt sich in sog. Struktur-Parametern wider. Diese wurden wiederum im Berich der Parametrisierten Komplexität als theoretische Grundlage für effiziente Lösungsalgrorithmen für generell schwierige Aufgabenstellungen (d.h. Probleme deren Lösung im Allgemeinen einen exponentiellen Aufwand in der Größe der Datenmenge bedingt) identifiziert. Ziel dieses Projekts ist die praktische Umsetzung dieser Ideen in obengenannten Anwendungsbereichen. Zu diesem Zweck wollen wir die Konzepte der Decomposition, wo Probleme bzgl. deren Struktureigenschaften zerlegt werden, und des Dynamic Programmings, das sind spezielle Algorithmen die ein Problem entlang einer solchen Zerlegung abarbeiten, einsetzen. Der innovative Aspekt des Projekts liegt in der Tatsache, dass sich die angesprochenen Struktureigenschaften sowohl in Daten als auch in komplexen Abfragen manifestieren. Auf dieser Grundlage sollen neue innovative Methoden entwickelt werden. Spezielle Sprachen zum Formulieren obengenannter Abfragen wurden in den letzten Jahren entwickelt, darunter Varianten von sog. deduktiven Datenbankabfragen oder im Bereich der Description Logics. Einen zentralen Vertreter stellt das Paradigma des sog. Answer-Set Programming (eine spezielle Datalog Variante) dar. Answer-Set Programming wurde bereits in den erwähnten Applikationsgebieten erfolgreich eingesetzt; Anwendungen die mit sehr großen Datenmengen umgehen müssen, zeigen jedoch noch die Grenzen der heutigen Systeme auf. In der ersten Phase des Projekts werden wir die Integration der angesprochenen Methoden in diesem Paradigma untersuchen. In einer zweiten Phase sollen die gewonnenen Erkenntnisse auf verwandte Abfragesprachen angewandt werden.

Die Geschichte des Computers und der Elektronischen Datenverarbeitung ist seit ihren Anfängen von zwei zentralen Einsatzgebieten geprägt worden, nämlich einerseits die effiziente Handhabung von großen Datenmengen (z.B. in Datenbankystemen für Lohnverrechnnung, Buchhhaltung, etc.) und andererseits das Abarbeiten von komplexen Algorithmen, die z.B. in Expertensystemen, Diagnose-tools, oder in Spielen wie Schach zum Tragen kommen. Aktuell gewinnen allerdings Fragestellungen die beide Problemfelder umfassen, also komplexe Berechnugen auf großen Daten, eine immer größere Bedeutung. Als ein Beispiel seien hier Plattformen wie Facebook erwähnt, die heutzutage von Hundert Millionen Usern verwendet werden, die ihrerseits in (Freundschafts-)beziehungen zueinander stehen. Ein typisches komplexes Berechnungsproblem in diesem Umfeld wäre nun z.B. das Identifizieren einer (möglichst kleinen) Menge von Benutzern sodass alle Benutzer mittels der Freundschaftsbeziehung direkt erreichbar sind. Komplexe Abfragen auf großen Datenmengen sind oft ein unüberwindbares Hindernis für Standard-Algorithmen. Dieses kann jedoch überwunden werden, wenn man sich Struktureigenschaften zu Nutze macht, die sich üblicherweise in Probleminstanzen aus konkreten Anwendungsgebieten finden lassen. Zu diesem Zweck haben wir uns die Konzepte der Decomposition, wo Probleme bzgl. deren Struktureigenschaften zerlegt werden, und des Dynamic Programmings, das sind spezielle Algorithmen die ein Problem entlang einer solchen Zerlegung abarbeiten, zu Nutze gemacht. Zu den Hauptresultaten des Projekts zählen: - eine neue formal Methode (decomposition-guided reductions) die es erlaubt die exakte Struktur-Komplexität diverserer Probleme in einer uniformen Art und Weise zu zeigen - die Entwicklung einer Software zur Zerlegung von Problemen, welche heute von einer Vielzahl von Forschungsgruppen genutzt wird - neuartige Implementierungsmethoden die sich auf (i) speziellen Speichertechniken, (ii) Datenbank-technologien, oder (iii) neue Hardware-Komponenten wie z.B. GPUs stützen. Unsere Systeme sind nun in der Lage Probleminstanzen von überraschend hoher Strukturkomplexität zu lösen, und somit bessere Laufzeiten als etablierte Methoden zu erzielen. Unsere Forschung wurde weiters in verschiedensten Belangen ausgezeichnet. Dazu zählen Best-Paper Preise, ein Early-Career Award, sowie nationale und internationale Dissertationspreise.