Kernelisierung für große Datenmengen

• Antragsteller: Professor Dr. Matthias Mnich
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2014 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 247801001

Ziel dieses Projektes ist die Entwicklung neuer Rechenverfahren für Eingabe-Ausgabe-effiziente Vorverarbeitung. Diese Rechenverfahren werden die mathematischen Grundlagen legen für leistungsfähige Algorithmen, um sehr große Instanzen schwerer Probleme auf kleine Instanzen mit garantierter Größe zu komprimieren. Diese Komprimierung ist essenziell, denn die komplexen Fragstellungen in Wissenschaft und Industrie auf den dort stetig wachsenden Datenmengen effizient zu beantworten können nur auf kleinen (komprimierten) Instanzen gelöst werden. Vorhandene Vorverarbeitungsroutinen sind jedoch nicht in der Lage, Datenmengen effizient zu komprimieren, wenn diese Daten nicht in den Arbeitsspeicher passen, wie es in Anwendungen oft der Fall ist. Unsere neuartigen Vorverarbeitungsalgorithmen werden dagegen große Eingaben speichereffizient in kleine Ausgaben komprimieren.Dazu nutzen sie gleichzeitig die Struktur von Instanz und Hardware, und reizen sowohl tiefe Erkenntnisse über mathematische Strukturen als auch die Fähigkeiten moderner Prozessortechnologie und Speicherhierarchien aus. Überdies werden unsere Verfahren zu einem theoretischen Modell beitragen, welches die praktischen Erfolge der Vorverarbeitung sehr großer Instanzen durch Algorithmen ohne Kompressionsgarantie (Heuristiken) auf eine solide theoretische Grundlage zu stellt, aber auch die Beschränkungen von Heuristiken erklären kann.

• DFG-Verfahren: Sachbeihilfen