Research On K-STEP Reachability Queries On An Uncertain Graph

An uncertain graph is an effective tool to describe the uncertain and fuzzy relationship between objects in the real world.The k-step reachability query on an uncertain graph is used to calculate the probability that a vertex can reach another vertex within k steps.The existing methods of k-step reachability query processing on uncertain graphs mainly carry out a sampling from the starting point,count the reachable number and obtain the estimated value,but the efficiency of query processing is low.To solve this problem,this paper proposes an efficient index to improve the efficiency of kstep reachability query processing on uncertain graphs.The research contents of this paper are as follows:First,this paper proposes a pruning strategy to deal with the situation where one vertex cannot reach another within k steps.The basic idea is to construct a k-step reachability index on the complete graph based on the minimum vertex coverage set,which is used to quickly identify the queries that are definitely unreachable within k steps.When solving the minimum vertex covering set,the vertices are selected in order of degree from large to small,so as to reduce the size of the covering set.When building index based on the vertex coverage set,vertices are processed from bottom to top according to the number of topological layers to speed up index construction.Different from the existing methods of direct sampling calculation,the method in this paper first quickly filters the queries on the graph that are definitely unreachable within k steps through the k-step reachability index,in order to avoid the expensive sampling calculation operation on this part of the query.Only when the query is determined to be k-step reachable,the method in this paper will carry out the subsequent calculation of reachability.When calculating the reachable probability,this paper reduces the possible world scale based on the path,and uses the strategy of bit vector to store the possible worlds in advance,so that the query can get the result directly.Secondly,this paper proposes two optimization strategies to accelerate the processing efficiency of k-step reachability query.In the aspect of probability calculation,bidirectional traversal sampling is proposed to reduce the performance inefficiency caused by the rapid increase in the number of vertices in traditional one-way sampling.The basic idea is to traverse the graph from two query vertices to each other at the same time,and always select the vertex with low degree to expand first.At the same time,the redundant vertices are marked in the traversal process,so that the scale of the graph involved in sampling is reduced again.In the aspect of unreachable query detection,the forward and reverse topological numbers are used to further accelerate the filtering of unreachable vertex pairs.Finally,the efficiency of the proposed algorithm is verified based on multiple real datasets.The experimental results are analyzed from three aspects of index construction time,index size and query efficiency.It is verified that the method proposed in this paper can quickly solve k-step reachability queries on uncertain graphs.