Big-Data-DynAmO: Dynamische, approximative, and online Methoden für große Datenmengen

• Antragsteller: Professor Dr.-Ing. Ulrich Meyer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2014 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 255326380

Big data wird oft durch die sogenannten drei Vs charakterisiert: Volume (die gigantische Menge der Daten), Variety (unterschiedlichste Datenformen) und Velocity (die hohe Geschwindigkeit ein- und ausgehender Daten). In diesem Antrag interessieren uns vor allem die algorithmischen Herausforderungen, die sich aus der Kombination von Volume und Velocity unter Resourcenbeschränkungen ergeben: mit einem Fokus auf Graphprobleme, die aus unterschiedlichsten Anwendungen stammen können, werden wir Möglichkeiten und Grenzen dynamischer Datenverabeitung untersuchen, bei der nach Datenänderungen auf schon bestehenden Lösungen aufgesetzt wird, statt alles von Grunde auf neu zu berechnen.Trotz Parallelverarbeitung und der effizienten Nutzung von Speicherhierarchien werden wir aufgrund der schieren Datenmenge oft gezwungen sein exakte Berechnungen aufzugeben und eine sinnvolle Balance zwischen Lösungsqualität und Berechnungsaufwand durch Approximationen zu suchen. Nicht nur die hochfrequenten Datenaktualisierungen sondern auch die Berechnungsplattform an sich kann zu einem Onlineszenario beitragen. Resourcen wie Hauptspeicher oder Cache werden oft zwischen mehreren nicht kooperierenden Prozessen geteilt, woraus sich für die beteiligten Prozessen dann hochvariable individuelle Cachegrößen mit oftmals dramatischen Pagingkosten ergeben. Wir möchten dazu sowohl gegen dynamische Cachegrößenänderungen robuste Algorithmen als auch faire Cache-Verteilungsverfahren (teilweise basierend auf algorithmischer Spieltheorie) untersuchen. Bei allen zu untersuchenden Aspekten streben wir nicht nur nach theoretischen Resultaten sondern möchten den ganzen Algorithm Engineering Zyklus durchlaufen. Das Arbeitsgebiet erstreckt sich von verbesserten Datenmodellen, über das Engineering besserer Algorithmen und Datenstrukturen bis zu deren Integration in Programmbibliotheken wie STXXL oder Thrill, so dass sie von anderen Teilnehmern des Schwerpunktprogramms (und darüber hinaus) genutzt werden können.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1736: Algorithmen für große Datenmengen