Research On K-step Reachability Query Processing On Directed Graphs

The k-step reachability query processing has a wide range of applications in the real world,such as friend recommendation,traffic route query,network routing and so on.The k-step reachability query is used to answer whether there is a path that does not exceed k in length between two vertices.Compared with the traditional reachability query,the k-step reachability query can provide more information.However,most of the existing k-step reachability query algorithms can only be applied to directed acyclic graphs.The k-step reachability query algorithm that can be applied to the general directed graph with circles has many problems such as large index size,long index construction time and low query efficiency.This paper studies the problem of k-step reachability query processing on directed graphs with circles.The research content is as follows.Firstly,an algorithm for computing approximate minimum vertex cover based on greedy idea is proposed.In each iteration,the algorithm selects the vertex with the largest degree on the fly and add it to the cover set,such that to reduce the cover set.By using the hash counting method,an approximate minimum vertex cover set can be obtained in linear time.A 2-hop index based on the minimum vertex cover is proposed.This method combines the advantages of the minimum vertex cover and the 2-hop index.By building a 2-hop index containing only the vertexes in the cover set,the index construction time,the index size and query time can then be reduced.Secondly,three optimization strategies are proposed to further accelerate the query processing.The first is the optimization of unreachability queries based on reciprocal reversed topological numbers,which improves the processing efficiency of unreachability queries.The second is an equivalent compression strategy based on directed graphs with circles,which further reduces the scale of the graph.The third is a threshold-based index optimization strategy,which improves the efficiency of queries answering for nodes that do not belong to the cover set.Finally,the proposed algorithm for computing the minimum covering set is compared with the existing algorithms on 25 real data sets.The experimental results show that the vertex cover proposed in this paper is smaller.And the index construction method based on the cover set vertex is better than existing algorithms for index construction time,index size and query time.It can support efficient queries answering for graphs with tens of millions of vertices under the limitation of 16 GB memory size.