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

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.

随着大规模数据分析越来越关注实体与形成网络之间的关系，图形分析领域发现了不同域之间的许多关键应用程序。图形数据分析的关键组成部分是计算图形节点之间的路径。许多现实世界的应用，例如电动汽车的路线规划和通信网络中的路由，都需要在多个标准下计算路径。为了提供解决方案，在这种情况下，现有作品着重于旨在计算一个或多个优化标准和/或约束的节点之间的查询，即多标准多标准多键盘（MC2）路径查询。然而，尽管有用于处理MC2路径查询的算法，但将这种算法集成到图形DBM和处理框架中非常有限，部分原因是MC2路径查询的许多算法都没有扩展。此外，现有的图形DBM不提供索引结构，以优化需要跨层图的路径查询的处理。在本项目中，我们将重点关注MC2路径查询的处理，尤其是我们将研究基于索引的基于索引的MC2路径查询。为此，该项目中进行的研究将分为两种工作流。在第一个工作流中，我们将专注于扩展现有的图形DBM，以完全支持MC2路径查询的处理。特别是，我们将在多个优化标准和/或约束下开发并将算法整合到现有的图形dbms中，以计算路径查询。此外，我们将开发扩展，以启用现有的声明图查询语言，以促进此类查询的表达。在第二次工作流中，我们将调查现有的基于预处理的路径查询方法，这些方法旨在在主内存中使用。通过利用这些方法中的想法，我们计划设计和开发新的索引结构，以支持Graph DBMS中MC2路径查询的有效处理，以及维护和调整这些索引结构的方法，以符合现实世界应用的要求。