Verarbeitung von Pfadanfragen in Graphdatenbanken mit mehreren multikriteriellen Nebenbedingungen

• Antragsteller: Dr. Theodoros Chondrogiannis
• Fachliche Zuordnung: Sicherheit und Verlässlichkeit, Betriebs-, Kommunikations- und verteilte Systeme ; Datenmanagement, datenintensive Systeme, Informatik-Methoden in der Wirtschaftsinformatik
• Förderung: Förderung seit 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 441421444

Da sich großangelegte Datenanalyse zunehmend auf die Beziehungen zwischen Entitäten und die daraus gebildeten Netzwerke konzentriert, findet die Analyse von Graphen viele wichtige Anwendungen in verschiedensten Bereichen. Eine Schlüsselkomponente der Graphdatenanalyse ist die Berechnung von Pfaden zwischen den Knoten eines Graphen. Anwendungen wie z.B. die Navigationsplanung für Elektrofahrzeuge und das Routing von Datenpaketen in Kommunikationsnetzen erfordern die Berechnung von Wegen nach mehreren Kriterien. Um in solchen Fällen Lösungen anzubieten, konzentrieren sich bestehende Arbeiten auf Anfragen, die Pfade zwischen Knoten unter einem oder mehreren Optimierungskriterien und/oder Nebenbedingungen, d.h. Pfadanfragen mit mehreren multikriterielle Nebenbedingungen (MC2), berechnen. Obwohl Algorithmen zur Verarbeitung solcher MC2-Pfadanfragen existieren, hält sich deren Integration in Graphdatenbanksysteme und -verarbeitungsplattformen in Grenzen, da viele Algorithmen für MC2-Pfadanfragen nicht skalieren. Darüber hinaus bieten vorhandene Graphdatenbanksysteme keine Indexstrukturen an, um die Verarbeitung von Pfadanfragen, die die Traversierung des zugrunde liegenden Graphen erfordern, zu optimieren.In diesem Projekt werden wir uns auf die Verarbeitung von MC2-Pfadanfragen konzentrieren und insbesondere die indexbasierte Verarbeitung von MC2-Pfadanfragen in Graphdatenbanksystemen untersuchen. Zu diesem Zweck wird die in diesem Projekt durchgeführte Forschung in zwei Teile gegliedert. Im ersten Teil des Projekts werden wir ein bestehendes Graphdatenbanksystem erweitern, sodass es die Verarbeitung von MC2-Pfadanfragen vollständig unterstützt. Insbesondere werden wir Algorithmen, um Pfadanfragen unter mehreren Optimierungskriterien und/oder Einschränkungen zu berechnen, entwickeln und ins System integrieren. Darüber hinaus werden wir auch bestehende deklarative Graphanfragesprachen erweitern, sodass solche Anfragen syntaktisch einfach ausgedrückt werden können. Im zweiten Teil der Arbeit werden wir bestehende vorverarbeitungsbasierte Methoden für Pfadanfragen untersuchen, die für die Ausführung im Hauptspeicher konzipiert wurden. Wir planen, Ideen aus diesen Methoden zu verwenden, um neuartige Indexstrukturen zu entwerfen und zu entwickeln. Auf diese Weise werden wir die effiziente Verarbeitung von MC2-Pfadanfragen in Graphdatenbanksystemen gewährleisten sowie die Pflege und Anpassung dieser Indexstrukturen an die Anforderungen von realen Anwendungen unterstützen.

• DFG-Verfahren: Sachbeihilfen