DRONE: An Efficient Distributed Subgraph-Centric Framework for Processing Large-Scale Power-law Graphs

doi:10.1109/TPDS.2022.3223068

	DRONE: An Efficient Distributed Subgraph-Centric Framework for Processing Large-Scale Power-law Graphs
	Zhang, Shuai 1,2; Jiang, Zite 1,2,3; Hou, Xingzhong 1,2; Li, Mingyu 1; Yuan, Mengting 4; You, Haihang 1,3
	2023-02-01
发表期刊	IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
ISSN	1045-9219
卷号	34 期号:2 页码:463-474
摘要	Nowadays, the ever-increasing volume of graph-structured data such as social networks, graph databases and knowledge graphs requires to be processed efficiently and scalably. These natural graphs commonly found in the real world have highly skewed power-law degree distribution and are called power-law graphs. The subgraph-centric programming model is a promising approach applied in many state-of-the-art distributed graph computing frameworks. However, the performance of subgraph-centric frameworks is limited when processing large-scale power-law graphs. When deployed to the subgraph-centric framework, existing graph partitioning algorithms are not suitable for power-law graphs. In this paper, we present a novel distributed graph computing framework, DRONE (Distributed gRaph cOmputiNg Engine), which leverages the subgraph-centric model and the vertex-cut graph partitioning strategy. DRONE also supports the fault tolerance mechanism to accommodate the increasing scale of machines with negligible overhead (6.48% on average). We further study the execution workflow of DRONE and propose an efficient and balanced graph partition algorithm (EBV) for DRONE. Experiments show that DRONE reduces the running time on real-world graphs by 25.6%, on average, compared to the state-of-the-art distributed graph computing frameworks. In addition, the EBV graph partition algorithm reduces the replication factor by at least 21.8% than other self-based partition algorithms. Our results indicate that DRONE has excellent potential in processing large-scale power-law graphs.
关键词	Fault tolerance graph partition large-scale power-law graph parallel graph computation subgraph-centric model
DOI	10.1109/TPDS.2022.3223068
收录类别	SCI
语种	英语
资助项目	Natural Science Foundation of China[41930110] ; Natural Science Foundation of China[61872272]
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Theory & Methods ; Engineering, Electrical & Electronic
WOS记录号	WOS:000902093700004
出版者	IEEE COMPUTER SOC
引用统计	被引频次：2[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/20096
专题	中国科学院计算技术研究所期刊论文
通讯作者	Yuan, Mengting; You, Haihang
作者单位	1.Chinese Acad Sci, Inst Comp Technol, State Key Lab Processors, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing 101408, Peoples R China 3.Zhongguancun Lab, Beijing 102206, Peoples R China 4.Wuhan Univ, Sch Comp Sci, Wuhan 430072, Hubei, Peoples R China
推荐引用方式 GB/T 7714	Zhang, Shuai,Jiang, Zite,Hou, Xingzhong,et al. DRONE: An Efficient Distributed Subgraph-Centric Framework for Processing Large-Scale Power-law Graphs[J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,2023,34(2):463-474.
APA	Zhang, Shuai,Jiang, Zite,Hou, Xingzhong,Li, Mingyu,Yuan, Mengting,&You, Haihang.(2023).DRONE: An Efficient Distributed Subgraph-Centric Framework for Processing Large-Scale Power-law Graphs.IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,34(2),463-474.
MLA	Zhang, Shuai,et al."DRONE: An Efficient Distributed Subgraph-Centric Framework for Processing Large-Scale Power-law Graphs".IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 34.2(2023):463-474.