A MapReduce-based approach for computing reachability preserving graph

Traditional computations of reachability preservation based on breadth-first search (BFS) results usually focus on small-scale datasets on stand-alone. In order to solve the bottlenecks of memory capacity and computing speed while traditional approaches manipulate large-scale datasets and intermediate data generated, we propose a MapReduce-based approach to compute the reachability preserving graph. Based on the distributed parallel computing platform with the MapReduce programming model, we first obtain the whole strongly connected components (SCCs) based on the BFS results of original graph dataset. For condensing SCCs, we present an updating method based on label propagation. Additionally, for further compression, equivalence classes are processed via analyzing BFS results based on reachability equivalence relation. The experiments show that the BFS-based parallel computation of reachability preservation can achieve a good compression ratio and speed up well on the Hadoop computing cluster.