Research On Reachability Queries Processing Based On RCN Reduction

Answering reachability queries is one of the fundamental graph operations to determine whether there is a reachable path between the two nodes in the graph.Existing reachability queries algorithms can be divided into two categories.One way to make acceleration is directly building index on the input graph,but its query performance is affected by the input graph size.The other way is reducing the size of the input graph,such that the given queries can be answered over a smaller graph,but its query performance on reduced graphs cannot be guaranteed.This paper studies the problems of existing approaches as follows.First,this paper proposes a graph reduction approach to accelerate reachability queries processing,named RCN(Removable Complete Node)reduction,to reduce the input graph G with |V| nodes into a smaller one Gr with |Vr| nodes.Assume that the probability of a node of G to be a query node is 1/|V|,we show that based on our appraoch,the lower bound probability that a query q can be answered in constant time is 1-(Vr|/|V|)2,which means the smaller the reduced graph,the larger the probability that q can be answered in constant time.The key to RCN reduction is to find more RCNs in the graph to reduce the size of the reduction graph,thus increasing the probability that the query can be answered in constant time.This paper first proposes the Yes-Label expansion approach,which can effectively increase the number of RCNs in the graph,but its execution efficiency and expansion result are greatly affected by No-Label.Based on this,this paper proposes a BT-order based No-Label,which can support an interval expansion well,further increasing the number of RCNs.Subsequently,this paper proposes two optimizations to enhance interval expansion to find more RCNs,including large-node based pruning and relaxed ER.Second,this paper proposes a new labeling scheme based on RCN reduction,named IL,which determines the processing sequence of nodes based on the influence of nodes,which can ensure that nodes with a large reachability relationship coverage are processed as soon as possible.The IL scheme introduces a new pruning strategy based on RCN reduction:if a node has no in-neighbor,there is no need to construct labels for it.This significantly reduces the index size and supports efficient query processing.Finally,this paper conducts experiments on 20 data sets.The effectiveness of RCN reduction in processing reachability queries is verified from two aspects:graph reduction and reachability query processing.The experimental results show that RCN reduction performs much better than existing graph reduction approaches.Based on RCN reduction,the query processing time of the-state-of-the-art approaches can be reduced significantly.