Paper Info
Title
Beyond Synchronous: New Techniques for External-Memory Graph Connectivity and Minimum Spanning Forest
Abstract
GraphChi [16] is a recent high-performance system for external memory (disk-based) graph computations. It uses the Parallel Sliding Windows (PSW) algorithm which is based on the so-called Gauss-Seidel type of iterative computation, in which updates to values are immediately visible within the iteration. In contrast, previous external memory graph algorithms are based on the synchronous model where computation can only observe values from previous iterations. In this work, we study implementations of connected components and minimum spanning forest on PSW and show that they have a competitive I/O bound of O(sort(E)log(V/M)) and also work well in practice. We also show that our MSF implementation is competitive with a specialized algorithm proposed by Dementiev et al. [10] while being much simpler.
Year
DOI
Venue
2014
10.1007/978-3-319-07959-2_11
SEA
Field
DocType
Volume
Graph,Computer science,sort,Algorithm,Connected component,Connectivity,Reverse-delete algorithm,Minimum spanning forest,Auxiliary memory,Computation
Conference
8504
ISSN
Citations 
PageRank 
0302-9743
2
0.37
References 
Authors
16
3
Name
Order
Citations
PageRank
Aapo Kyrola1104933.52
Julian Shun259332.57
Guy E. Blelloch32927207.30