I/O efficient: computing SCCs in massive graphs

Publisher:
Springer New York LLC
Publication Type:
Journal Article
Citation:
VLDB Journal, 2015, 24 (2), pp. 245 - 270
Issue Date:
2015-09-24
Full metadata record
Files in This Item:
Filename Description Size
ThumbnailO Efficient - Computing SCCs in Massive Graphs.pdfPublished Version1.47 MB
Adobe PDF
A strongly connected component ((Formula presented.)) is a maximal subgraph of a directed graph (Formula presented.) in which every pair of nodes is reachable from each other in the (Formula presented.). With such a property, a general directed graph can be represented by a directed acyclic graph (DAG) by contracting every (Formula presented.) of (Formula presented.) to a node in DAG. In many real applications that need graph pattern matching, topological sorting, or reachability query processing, the best way to deal with a general directed graph is to deal with its DAG representation. Therefore, finding all (Formula presented.)s in a directed graph (Formula presented.) is a critical operation. The existing in-memory algorithms based on depth first search (DFS) can find all (Formula presented.)s in linear time with respect to the size of a graph. However, when a graph cannot reside entirely in the main memory, the existing external or semi-external algorithms to find all (Formula presented.)s have limitation to achieve high I/O efficiency. In this paper, we study new I/O-efficient semi-external algorithms to find all (Formula presented.)s for a massive directed graph (Formula presented.) that cannot reside in main memory entirely. To overcome the deficiency of the existing DFS-based semi-external algorithm that heavily relies on a total order, we explore a weak order based on which we investigate new algorithms. We propose a new two-phase algorithm, namely, tree construction and tree search. In the tree construction phase, a spanning tree of (Formula presented.) can be constructed in bounded number of sequential scans of (Formula presented.). In the tree search phase, it needs to sequentially scan the graph once to find all (Formula presented.)s. In addition, we propose a new single-phase algorithm, which combines the tree construction and tree search phases into a single phase, with three new optimization techniques. They are early acceptance, early rejection, and batch processing. By the single-phase algorithm with the new optimization techniques, we can significantly reduce the number of I/Os and the CPU cost. We prove the correctness of the algorithms. We conduct extensive experimental studies using 4 real datasets including a massive real dataset and several synthetic datasets to confirm the I/O efficiency of our approaches.
Please use this identifier to cite or link to this item: