Research Of Reachability Queries Processing Within K Steps On Graph Data

Efficiently answering reachability queries within k steps is one of hot research issues in graph data management. It has been widely used in many fields in real life, including wireless or sensor networds, the Web and Internet, telecommunication networks, social networks, etc. Reachability queries within k steps can reflect the influence of the vertices, which can provide more information than the reachability queries for users in many practical applications. This paper researches reachability queries within k steps over the graph data from the following several aspects.Firstly, we find that the problem of existing methods are either inefficient, or with large indexes through the analysis of the existing algorithm.Secondly, we propose a new bidirectional processing algorithm, namely BIRCH, which uses bidirectional search strategy and interval labeling index to be judged. When checking whether a vertex u can reach v within k steps, BIRCH firstly compares the out-degree of u and the in-degree of v, and processes the one with smaller degree, such that to avoid large indexes and the inefficiency due to large degree.Thirdly, we further propose BIRCH-BL algorithm, BIRCH-BL algorithm and RE-BIRCH-BTL algorithm based on two pruning strategies of bidirectional breadth-first levels, bidirectional topological levels and bidirectional interval indexing, such that to reduce the number of visited vertexes.At last, our experimental results on 19 real datasets verify the efficiency of our method in terms of different metrics, including indexing time, index size, query processing time, the number of visited vertexes, and scalability.