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

• 作者: 代亚非 曲直 杨智 申林 薛继龙
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 图处理系统 增量图处理 图切分 主动计算触发 反向链式更新
• 年，卷（期）: 2013,（12）
• 所属期刊栏目: 学术研究
• 页码范围: 1083-1092
• 页数: 10页
• 分类号: TP393.0
• 字数: 7555字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1305031

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	代亚非	北京大学计算机科学与技术系	36	851	14.0	29.0
2	杨智	北京大学计算机科学与技术系	13	134	6.0	11.0
3	曲直	北京大学计算机科学与技术系	8	37	4.0	5.0
4	申林	北京大学计算机科学与技术系	1	5	1.0	1.0
5	薛继龙	北京大学计算机科学与技术系	1	5	1.0	1.0