A Reachability Query Method Based on Labeling Index on Large-Scale Graphs

As a general data structure, graphs have been applied widely in many fields, for instance, geographical navigation, web semantic analysis, XML databases, etc. With the successful application of graphs in various fields, the rampant growth of graph data, and the structures of graph data becoming more complex, the analysis, storage and management for graph data are facing the unprecedented challenge. As a common analysis technology on large-scale DAG data, reachability query has been widely studied. Whereas, the existing reachability query mechanisms on large-scale graphs have some problems such as index creation requires a lot of time consumption and large storage space, query efficiency is low and so on. Therefore, in order to solve the above problems and implement efficient reachability query, we propose a labeling index method based on graph stratification (GSL), this method utilizes the properties of bipartite graph to link all vertexes into a mutually disjoint chain structure, creates unique chain-in label and chain-out label for each vertex, Besides this paper proposes two kinds of reachability query methods: chain-in reachability query and chain-out reachability query, Extensive experimental results verify the reachability query methods we propose have good query performance on the real-world networks, large-scale sparse graphs and dense graphs, increase efficiency of reachability query on large-scale DAG vastly.