Tripoline: generalized incremental graph processing via graph triangle inequality
Tripoline: generalized incremental graph processing via graph triangle inequality
复制标题
DOI：
10.1145/3447786.3456226
复制
发表时间：
2021-04
期刊：
影响因子：
--
通讯作者：
Xiaolin Jiang;Chengshuo Xu;Xizhe Yin;Zhijia Zhao;Rajiv Gupta
中科院分区：
文献类型：
--
作者：
Xiaolin Jiang;Chengshuo Xu;Xizhe Yin;Zhijia Zhao;Rajiv Gupta
对于在流图上进行计算密集型迭代查询，连续和逐步评估查询以达到最佳效率至关重要。但是，现有的增量图处理需要对查询的先验知识（例如，特定于顶点特定查询的源顶点）；否则，它必须回到从头开始的昂贵的完整评估。为了减轻这一限制，这项工作提出了一种有原则的解决方案，可以逐步评估渐进图处理处理，以便在没有其先验知识的情况下查询。解决方案集中在图三角形不平等的概念中，这是受欧几里得空间中经典三角不平等原则启发的想法。有趣的是，对于许多顶点特定的图形问题，也可以得出类似的原则。这些原则可以帮助建立一个图查询的评估和另一个图的结果之间的严格约束，从而使后者可以加速前者。基于这一发现，建立了一个新颖的流式图系统，称为Tripoline，可以在没有其先验知识的情况下对查询进行增量评估。 Tripoline建立在最先进的共享内存流图引擎（ASPEN）的顶部，本身支持高通量低成本图形更新。具有八个顶点特异性图问题和四个现实世界大图的系统评估既证实了所提出的技术的有效性，也证实了三翼的效率。
For compute-intensive iterative queries over a streaming graph, it is critical to evaluate the queries continuously and incrementally for best efficiency. However, the existing incremental graph processing requires a priori knowledge of the query (e.g., the source vertex of a vertex-specific query); otherwise, it has to fall back to the expensive full evaluation that starts from scratch. To alleviate this restriction, this work presents a principled solution to generalizing the incremental graph processing, such that queries, without their a priori knowledge, can also be evaluated incrementally. The solution centers around the concept of graph triangle inequalities, an idea inspired by the classical triangle inequality principle in the Euclidean space. Interestingly, similar principles can also be derived for many vertex-specific graph problems. These principles can help establish rigorous constraints between the evaluation of one graph query and the results of another, thus enabling reusing the latter to accelerate the former. Based on this finding, a novel streaming graph system, called Tripoline, is built which enables incremental evaluation of queries without their a priori knowledge. Built on top of a state-of-the-art shared-memory streaming graph engine (Aspen), Tripoline natively supports high-throughput low-cost graph updates. A systematic evaluation with a set of eight vertex-specific graph problems and four real-world large graphs confirms both the effectiveness of the proposed techniques and the efficiency of Tripoline.