中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
DRONE: An Efficient Distributed Subgraph-Centric Framework for Processing Large-Scale Power-law Graphs

文献类型：期刊论文

作者Zhang, Shuai3,4; Jiang, Zite2,3,4; Hou, Xingzhong3,4; Li, Mingyu4; Yuan, Mengting1; You, Haihang2,4
刊名IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
出版日期2023-02-01
卷号34期号:2页码:463-474
关键词Fault tolerance graph partition large-scale power-law graph parallel graph computation subgraph-centric model
ISSN号1045-9219
DOI10.1109/TPDS.2022.3223068
英文摘要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.
资助项目Natural Science Foundation of China[41930110] ; Natural Science Foundation of China[61872272]
WOS研究方向Computer Science ; Engineering
语种英语
WOS记录号WOS:000902093700004
出版者IEEE COMPUTER SOC
源URL[http://119.78.100.204/handle/2XEOYT63/20095]  
专题中国科学院计算技术研究所期刊论文
通讯作者Yuan, Mengting; You, Haihang
作者单位1.Wuhan Univ, Sch Comp Sci, Wuhan 430072, Hubei, Peoples R China
2.Zhongguancun Lab, Beijing 102206, Peoples R China
3.Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing 101408, Peoples R China
4.Chinese Acad Sci, Inst Comp Technol, State Key Lab Processors, Beijing 100190, 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.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。