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

Shuai Zhang

doi:10.1109/TPDS.2022.3223068

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

2023-02-01

3

PRE

AI

DOI：10.1109/TPDS.2022.3223068

原文链接

原文求助

摘要

En 中文

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.

Keyword:

Fault tolerance

graph partition

large-scale power-law graph

parallel graph computation

subgraph-centric model

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

摘要

期刊

机构

引用论文