Efficient Disk-Based Directed Graph Processing: A Strongly Connected Component Approach
Authors:
- 22 November 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 29 (4) , 830-842
Abstract
Recently, there have been many disk-based systems proposed for iterative graph processing. In the popular vertex/edge-centric systems, an iterative directed graph algorithm needs to reprocess many partitions so as to update their vertices' states according to other non-convergent vertices for the unawareness of their dependencies. As a result, it induces high data access cost and a long time to converge. To tackle this problem, we propose a novel system for iterative directed graph processing with taking advantage of the strongly connected component (SCC) structure. It stores a directed graph into a directed acyclic graph (DAG) sketch, with each node representing a SCC in the original data graph. During execution, the SCCs are loaded into memory for processing in a parallel way according to the topological order of the DAG sketch, and the vertices in each SCC are tried to be handled along the directed paths. In this way, each SCC is able to reach convergence in order and needs to be loaded into the main memory for exactly once, getting much lower data access cost and faster convergence. Besides, the vertices of each SCC need fewer updates for convergence. We further develop a lightweight approach to maintain the DAG sketch and handle SCCs in an incremental way for evolving graphs. Compared with the state-of-the-art methods, experimental results show that our approach achieves a performance improvements of 1.46-8.37 times for static graphs, and can reduce the execution time by 61.4-72.7 percent for evolving graphs.Keywords
Funding Information
- National Natural Science Foundation of China (61702202, 61628204, 61732010)
- China Postdoctoral Science Foundation funded project (2017M610477, 2017T100555)
This publication has 34 references indexed in Scilit:
- SAE: Toward Efficient Cloud Data Analysis Service for Large-Scale Social NetworksIEEE Transactions on Cloud Computing, 2015
- Resisting Skew-Accumulation for Time-Stepped Applications in the Cloud via Exploiting ParallelismIEEE Transactions on Cloud Computing, 2014
- Inc-Part: Incremental Partitioning for Load Balancing in Large-Scale Behavioral SimulationsIEEE Transactions on Parallel and Distributed Systems, 2014
- Topology manipulations for speeding betweenness centrality computationJournal of Complex Networks, 2014
- Maiter: An Asynchronous Graph Processing Framework for Delta-Based Accumulative Iterative ComputationIEEE Transactions on Parallel and Distributed Systems, 2013
- Fast iterative graph computation with block updatesProceedings of the VLDB Endowment, 2013
- Medusa: Simplified Graph Processing on GPUsIEEE Transactions on Parallel and Distributed Systems, 2013
- Graph homomorphism revisited for graph matchingProceedings of the VLDB Endowment, 2010
- GRAILProceedings of the VLDB Endowment, 2010
- PageRank revisitedACM Transactions on Internet Technology, 2006