Large Graph Reachability Query Research On Distributed System

Graph data gains its popularity in science and technology, so it often encounter computing problems about reachability queries. With the expanding of big data, traditional reachability methods can not meet the requirements on large graph data,which makes processing reachability queries on large graphs has become an important problem.Reachability query is closely related to computing model and processing algorithms. Traditional reachability methods have issues of locality, insufficient processing ability and poor scalability. Improved algorithms are limited on stand-alone environment. To solve the reachability query problem for large graph, the reachability framework in a distributed environment for large graph is designed, in which massive million-level graph with tens of millions of vertices and edges can be computed and queried.For processing the distributed large graph, a reachability framework for large graph is designed. The graph can be pre-processed and partitioned by Balanced Topology Graph Partition algorithms for the reachability queries, which makes subgraphs have good internel cohension by one-time partition. In addition, a distributed graph index Distributed Cross-Subgraph Index for efficient reachability queries of the subgraphs is designed, building indexes among the bone vertices and out vertices, makes the reachability queries can efficiently compute on the subgraphs. Both partition and reachability experiments proved that our reachabilty framwork for large graph reachability queries is more effective than traditional methods.