Research On Reachability Preserving Graph Based On MapReduce

The reachability query on the directed graph is an important problem while we study graph. Given a directed graph ?EVG),( and any two vertices,Vvu ?, the problem of reachability query on G is to judge whether there is a path from u to v in G. In recent years, the graph compression gradually became one of the effective solutions to solve query problem on the graph. The reachability preserving graph is a directed graph which is obtained by graph compression processing. Its aim is to improve the efficiency of reachability query on the directed graph.Traditional methods of computing reachability preserving graph usually focus on stand-alone mode and small data sets. While dealing with large-scale original data and intermediate data, traditional methods will generate the bottleneck of memory capacity and computing speed. For example, a lot of breadth-first search(BFS) results will be processed while computing equivalence class. It is a new challenge to process such large intermediate data for the traditional algorithms and computational platforms. This paper will focus on computing reachability preserving graph with BFS results based on MapReduce.Based on the traditional methods, a MapReduce-based approach is proposed for parallel computing reachability preserving graph. The approach takes advantages of the MapReduce parallel programming paradigm and the Hadoop distributed framework. The computation of reachability preserving graph is implemented in a distributed and parallel way. The main contributions include: First, we propose the approach of computing reachability preserving graph suitable for MapReduce, including BFS-based approach for detecting strongly connected components(SCC) and label propagating approach for condensing SCC. Then, we design the MapReduce-based scheme for computing and condensing SCC based on the methods above. In addition, we design the MapReduce-based scheme for computing and condensing equivalence class. We also preliminarily study the reachability query scheme based on the reachability preserving graph.Finally, we implement our approach with MapReduce. A series of experimental studies verify the feasibility, effectiveness, high efficiency and scalability of our approach.