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

被引：12

作者：

王童童 ^{[1
,2
]}

荣垂田 ^{[3
]}

卢卫 ^{[1
,2
]}

杜小勇 ^{[1
,2
]}

机构：

[1] 数据工程与知识工程教育部重点实验室(中国人民大学)

[2] 中国人民大学信息学院

[3] 天津工业大学计算机科学与软件学院

来源：

软件学报 | 2018年 / 29卷 / 03期

关键词：

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

D O I：

10.13328/j.cnki.jos.005450

中图分类号：

TP301.6 [算法理论]; TP333 [存贮器];

学科分类号：

081202 ; 081201 ;

摘要：

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

引用

页码：569 / 586

页数：18

共 64 条

[1]

Apache Giraph. http://giraph.apache.org/ .

[2]

Distributed Algorithms. Lynch NA. . 1996

[3]

Go FFish:A sub-graph centric framework for large-scale graph analytics. Simmhan Y,Kumbhare A,Wickramaarachchi C,Nagarkar S,Ravi S,Raghavendra C. Proc.of the European Conf.on Parallel Processing . 2014

[4]

Graph Steal:Dynamic re-partitioning for efficient graph processing in heterogeneous clusters. Kumar D,Raj A,Dharanipragada J. Proc.of the 2017 IEEE 10th Int’’l Conf on Cloud Computing (CLOUD) . 2017

[5]

Apache Hama. http://hama.apache.org/ .

[6]

Gps:A graph processing system. Salihoglu S,Widom J. Proc.of the 25th Int’’l Conf.on Scientific and Statistical Database Management . 2013

[7] GraphHP:一个图迭代处理的混合平台 [J].

苏静 ;

索博 ;

陈群 ;

潘魏 ;

李战怀 .

华东师范大学学报(自然科学版), 2016, (05) :112-120

[8]

Protein‐protein interactions: Making sense of networks via graph‐theoretic modeling[J] . &nbspBioessays . 2011 (2)

[9]

PT-S cotch : A tool for efficient parallel graph ordering[J] . C. Chevalier,F. Pellegrini. &nbspParallel Computing . 2007 (6)

[10]

A high-performance, portable implementation of the MPI message passing interface standard[J] . William Gropp,Ewing Lusk,Nathan Doss,Anthony Skjellum. &nbspParallel Computing . 1996 (6)

← 1 2 3 4 5 6 7 →