GraphDuo: A Dual-Model Graph Processing Framework

doi:10.1109/ACCESS.2018.2848291

Return

GraphDuo: A Dual-Model Graph Processing Framework

2018-01-01

Xinhui Tian

Jianfeng Zhan *

DOI：10.1109/ACCESS.2018.2848291

Original

Save

View PDF

Abstract

En 中文

Algorithms for large-scale natural graph processing can be categorized into two types based on their value propagation behaviors: the unidirectional value propagation algorithms and the bidirectional value propagation algorithms. The graph computation in different types exhibits different properties on how vertices interact with their neighbors and has different requirements on system design. Current distributed graph processing systems usually try to support both types in one general-purpose computing model, which can result in suboptimial performance, high communication overhead, and high resource consumption. In this paper, we propose GraphDuo, a new Spark-based graph processing framework that provides two efficient computing models for unidirectional and bidirectional value propagation algorithms, respectively. Combined with a degree-based graph partitioning scheme, a locality-aware graph layout, and other optimization techniques, GraphDuo achieves low computation cost, low communication overhead, small memory footprint, and good communication balance for two types of algorithms. According to the experimental results, GraphDuo can outperform GraphX from 1.76x to 6.56x and from 1.11x to 1.26x for two types of algorithms, respectively, with much less memory consumption and communication cost. The source code of GraphDuo is publicly available from http://prof.ict.ac.cn/GraphDuo.

Keywords:

Data processing

distributed processing

graph theory

large-scale systems

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.