2023-06-252023-06-25https://tore.tuhh.de/handle/11420/15839Ziel 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.The main research goal of this project is the quest for a rigorous mathematical theory of input-output efficient preprocessing. This new theory will develop the computational tools to design powerful algorithms for preprocessing very large instances of hard problems that very efficiently compress those instances to smaller ones with guaranteed size. Our motivation is the incapability of current preprocessing routines with compression guarantee (kernelizations) to handle very large instances that do not fit into main memory. The theory also seeks to rigorously explain the practical successes of preprocessing very large instances by algorithms without compression guarantee (heuristics), and will lead to a concept of computational intractability to explain the limitations of heuristics. The project aims to design preprocessing algorithms that harness the full capabilities of advanced processor technology and memory hierarchies of computing hardware in science and industry, to efficiently compress big data sets. With new multivariate computational models that utilize instance structure and hardware structure at the same time, we will deepen the understanding of the mathematical origins of compressibility and serve to build more powerful algorithms for preprocessing massive data sets.