IncGraph：支持实时计算的大规模增量图处理系统

摘要：

随着社交网络的流行，越来越多的相关应用要求能够实时地在大规模社会网络图上进行分析和计算。而目前的图处理系统，如Google的Pregel，是全局、批量处理的图处理系统，并不能实现对图的实时计算。因此，提出了一种新的图增量处理模型，当一个节点发生变化时，只需要以传播的方式更新局部范围内受影响节点。它本质上将传统的批量全局计算模型，转化成一系列的增量的、局部的图计算，保证对图变化的实时处理，并通过避免没有更新节点的重复计算来降低开销。基于这种新的图计算模型，设计了一个低开销、实时的图处理系统--IncGraph，它通过图切分技术将计算局部化，保证了计算的低开销，同时利用主动计算触发和反向链式更新技术，保证了计算的实时性和可靠性。利用真实的社交网络数据证明了IncGraph的低开销、实时性和扩展性。IncGraph的提出会为社交网络应用提供更为灵活的计算框架。

关键词：图处理系统、增量图处理、图切分、主动计算触发、反向链式更新

分类号：TP393.0(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant No.61073015;the National Science and Tech-nology Major Special Project of China under Grant No.2010ZX03004-001-03

在线出版日期：2013-12-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：1083-1092