Continuous Graph Querying and Graph OLAP Using Differential Computation

微分计算(DC)是一种最新的方法，用于维护在输入变化下可以表示为操作符数据流的计算。在这个项目中，我们建议研究DC在图处理中的两个应用：1.连续查询：在动态图上连续计算几个图查询，如单源最短路径、单对最短路径、变长路径和任意长圈查询。图OLAP查询：评估对无状态图的多个快照或图视图的查询，这些视图定义为属性的多维立方体。这些查询可以支持金融欺诈、交通运输、网络安全等领域的几个重要应用，但目前现有的图形处理软件不支持这些查询。我们计划探索使用DC开发软件基础设施来支持这些查询的可行性。

Differential computation (DC) is a recent approach for maintaining computations that can beexpressed as a dataflow of operators under input changes. In this project, we propose to investigatetwo applications of DC to graph processing:1. Continuous queries: To continuously evaluate several graph queries, such as single-sourceshortest paths, single- pair shortest path, variable-length path, and arbitrary-length cyclequeries, over dynamic graphs.2. Graph OLAP queries: To evaluate queries over multiple snapshots or graph views of astatic graph, where the views defined as a multidimensional cube of attributes.These queries can support several important applications in financial fraud, transportation, cybersecurity and others but are currently not supported by existing graph processing software. We planto explore the feasibility of developing a software infrastructure using DC to support these queries.