分布式图处理系统技术综述

来源：软件学报杂志2018年第3期北京时间：

作者：王童童,荣垂田,卢卫,杜小勇

单位：王童童，数据工程与知识工程教育部重点实验室(中国人民大学), 北京 100872;中国人民大学 信息学院, 北京 10087211,荣垂田，天津工业大学 计算机科学与软件学院, 天津 30038702,卢卫，数据工程与知识工程教育部重点实验室(中国人民大学), 北京 100872;中国人民大学 信息学院, 北京 10087203,杜小勇，数据工程与知识工程教育部重点实验室(中国人民大学), 北京 100872;中国人民大学 信息学院, 北京 10087204

摘要：图作为一种基本的数据类型，是对现实世界中对象及其关联关系的一种抽象.现实中，许多科学问题都可以被模型化为图的问题，因此，对图数据进行分析非常重要.图数据分析在语义Web分析、社交网络、生物基因分析以及信息检索等领域有着广泛的应用.随着移动互联、物联网等信息技术的发展，图数据的规模处于持续增长的状态.为了能够应对大规模图数据的高效分析和计算，Google提出了Pregel分布式图处理框架.此后，学术界和工业界提出了许多基于Pregel框架的优化技术和系统实现.在充分调研和分析的基础上，首先总结出分布式图处理系统的3个优化目标；其次，从计算粒度、任务调度、通信方式、负载划分这4个维度，综述现有分布式图处理系统中的各类优化技术；最后，对该领域未来的研究内容和发展方向进行了探讨与展望.

关键词：分布式图处理系统;计算粒度;任务调度;通信方式;负载划分

基金资助：国家自然科学基金（61502504，61402329，61732014，61472321）；中国人民大学科学研究基金（中央高校基本科研业务费专项资金）（15XNLF09）