计算机科学与探索Issue(12)：1083-1092,10.DOI:10.3778/j.issn.1673-9418.1305031
IncGraph：支持实时计算的大规模增量图处理系统
IncGraph：Large-Scale Graph Processing System for Real-Time and Incremental Computing
摘要
Abstract
With the increasing popularity of online social networks (OSNs), more and more related applications need a computation framework for processing large social graphs in a real-time manner. However, the existing graph processing systems, such as Google’s Pregel, cannot achieve real-time performance due to processing the graph in global and batch manners. Therefore, this paper proposes a new graph computation model that restricts the computation to a local area when a node is updated. In essence, it transforms the traditional batch and global computations to a series of incremental and local computations. By this way, people achieve the goal of real-time computation, and avoid the overhead of dupli-cate computation on nodes that have not changed. Based on this new computation model, this paper designs IncGraph, a real-time large graph processing system. To achieve an efficient and scalable implementation, this paper uses graph parti-tion techniques to exploit the computation locality in social graph, moreover, uses proactive computing trigger and inversing update chain to realize the real-time and reliable computing. Finally, this paper uses real social network data to validate the system performance. IncGraph can provide social network applications a more flexible computation framework.关键词
图处理系统/增量图处理/图切分/主动计算触发/反向链式更新Key words
graph processing system/incremental graph processing/graph partition/proactive computing trigger/inversing update chain分类
信息技术与安全科学引用本文复制引用
申林,薛继龙,曲直,杨智,代亚非..IncGraph：支持实时计算的大规模增量图处理系统[J].计算机科学与探索,2013,(12):1083-1092,10.基金项目
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(国家科技重大专项) （国家科技重大专项）
