VRGQ: Evaluating a Stream of Iterative Graph Queries via Value Reuse
VRGQ: Evaluating a Stream of Iterative Graph Queries via Value Reuse
复制标题
VRGQ：通过值重用评估迭代图查询流
DOI：
10.1145/3469379.3469382
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Gupta, Rajiv
中科院分区：
文献类型：
--
作者：
Jiang, Xiaolin;Xu, Chengshuo;Gupta, Rajiv
虽然关于大型幂律图的图分析的大部分研究都集中在开发用于评估单个全局图查询的算法，但在实践中，我们可能会面临一系列查询。我们观察到，由于其全局性质，特定于顶点的图查询为跨查询共享工作提供了机会。为了利用这个机会，我们开发了VRGQ框架，该框架通过粗粒度的值重用来加速对查询流的评估。特别是，对一小部分源顶点的查询结果被重复使用，以加速所有未来的查询。我们提出了一个两步算法，第一步基于值重用初始化查询结果，然后在第二步迭代计算查询的收敛。少量查询的重用结果保存在重用表中。我们在4个幂定律图和5种图的数千个查询上进行了最佳重用配置的实验，平均加速比分别为143×、13.2×、6.89×、1.43×和1.18×。
While much of the research on graph analytics over large power-law graphs has focused on developing algorithms for evaluating a single global graph query, in practice we may be faced with a stream of queries. We observe that, due to their global nature, vertex specific graph queries present an opportunity for sharing work across queries. To take advantage of this opportunity, we have developed the VRGQ framework that accelerates the evaluation of a stream of queries via coarsegrained value reuse. In particular, the results of queries for a small set of source vertices are reused to speedup all future queries. We present a two step algorithm that in its first step initializes the query result based upon value reuse and then in the second step iteratively evaluates the query to convergence. The reused results for a small number of queries are held in a reuse table. Our experiments with best reuse configurations on four power law graphs and thousands of graph queries of five kinds yielded average speedups of 143×, 13.2×, 6.89×, 1.43×, and 1.18×.