Multi-criteria Multi-constraint Path Query Processing on Graph Databases

• Applicant: Dr. Theodoros Chondrogiannis
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems ; Data Management, Data-Intensive Systems, Computer Science Methods in Business Informatics
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 441421444

As large-scale data analysis increasingly focuses on the relationships between entities and the networks that are formed, the field of graph analytics has found many key applications among different domains. A key component of graph data analysis is the computation of paths between nodes of a graph. Many real world applications such as route planning for electric vehicles and routing in communication networks, require the computation of paths under multiple criteria. To provide solutions in such cases, existing works focus on queries that aim at computing paths between nodes under one or more optimization criteria and/or constraints, i.e., multi-criteria multi-contstraint (MC2) path queries. However, despite the availability of algorithms for processing MC2 path queries, the integration of such algorithms into graph DBMS and processing frameworks has been very limited, partly because many algorithms for MC2 path queries do not scale. Moreover, existing graph DBMS provide no index structures to optimize the processing of path queries that require the traversal of the underlying graph.In this project, we will focus on the processing of MC2 path queries and, in particular, we will study the index-based processing of MC2 path queries in graph DBMS. Towards this end, the research conducted in this project will be structured into two streams of work. In the first stream of work, we will focus on extending existing graph DBMS to fully support the processing of MC2 path queries. In particular, we will develop and integrate algorithms into existing graph DBMS for computing path queries under multiple optimization criteria and/or constraints. Furthermore, we will develop extensions to enable existing declarative graph query languages to facilitate the expression of such queries as well. In the second stream of work, we will investigate existing preprocessing-based methods for path queries that have been designed to work in the main memory. By utilizing ideas from these methods, we plan to design and develop novel index structures to support the efficient processing of MC2 path queries in graph DBMS, along with methods for maintaining and tuning these index structures to match the requirements of real-world applications.

• DFG Programme: Research Grants