Paper Info
Title
CGraph: A Distributed Storage and Processing System for Concurrent Iterative Graph Analysis Jobs
Abstract
Distributed graph processing platforms usually need to handle massive Concurrent iterative Graph Processing (CGP) jobs for different purposes. However, existing distributed systems face high ratio of data access cost to computation for the CGP jobs, which incurs low throughput. We observed that there are strong spatial and temporal correlations among the data accesses issued by different CGP jobs, because these concurrently running jobs usually need to repeatedly traverse the shared graph structure for the iterative processing of each vertex. Based on this observation, this article proposes a distributed storage and processing system CGraph for the CGP jobs to efficiently handle the underlying static/evolving graph for high throughput. It uses a data-centric load-trigger-pushing model, together with several optimizations, to enable the CGP jobs to efficiently share the graph structure data in the cache/memory and their accesses by fully exploiting such correlations, where the graph structure data is decoupled from the vertex state associated with each job. It can deliver much higher throughput for the CGP jobs by effectively reducing their average ratio of data access cost to computation. Experimental results show that CGraph improves the throughput of the CGP jobs by up to 3.47× in comparison with existing solutions on distributed platforms.
Year
DOI
Venue
2019
10.1145/3319406
ACM Transactions on Storage (TOS)
Keywords
Field
DocType
Data access correlations, data access cost, throughput
Vertex (geometry),Cache,Computer science,Parallel computing,Distributed data store,Power graph analysis,Throughput,Data access,Distributed computing,Computation,Traverse
Journal
Volume
Issue
ISSN
15
2
1553-3077
Citations 
PageRank 
References 
2
0.36
0
Authors
8
Name
Order
Citations
PageRank
Yu Zhang16917.13
jin zhao2123.30
Xiaofei Liao31145120.57
Hai Jin46544644.63
Lin Gu5738.80
Haikun Liu660935.79
Bingsheng He72810179.09
Ligang He854256.73