ScaleG: A Distributed Disk-Based System for Vertex-Centric Graph Processing

doi:10.1109/TKDE.2021.3101057

ScaleG: A Distributed Disk-Based System for Vertex-Centric Graph Processing

2021-01-01

3

OA

AI

DOI：10.1109/TKDE.2021.3101057

Original

Original request for help

Save

Abstract

En 中文

Designing distributed graph systems has drawn a lot of research interests due to the strong expressiveness of the graph model and rapidly increasing graph volume. Most of them require the graph data and all intermediate messages to reside in main memory, which may sacrifice the scalability. Even though several disk-based systems have been studied to remedy such issue, several challenges still exist in achieving both high computational efficiency and low network communication under the limitation of memory usage. In this paper, we design a novel disk-based distributed graph system, called ScaleG. The system provides a series of user-friendly programming interfaces. Unlike previous systems, the programmer in ScaleG does not need to concern any logic regarding the communication between vertices like sending messages and combining messages. In addition, we propose several techniques to reduce both disk I/Os in each machine and message I/Os via the network. We manage all messages in memory and bound all messages by the number of vertices. We also carefully design the data structure to support partial computation and automatic vertex activation. We conduct extensive experiments on six big graphs to show the high efficiency of our system.

Keywords:

Computational modeling

Scalability

Programming

Load modeling

Australia

Optimization

Image color analysis

Graph processing

distributed system

scalability

disk I

O

ScaleG: A Distributed Disk-Based System for Vertex-Centric Graph Processing

Abstract

Journal

Organization