Continuous Graph Querying and Graph OLAP Using Differential Computation

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

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