Research On K-step Reachability Query Algorithm Based On Weight Constranit

Reachability query is one of the basic operations on data graph,which aims to answer whether there is a path between two vertices in the graph.It is widely used in biological network,communication network,social network and other fields.In practice,users are more concerned about whether the accessibility query meets specific constraints,such as the length of the path between two points or the weight constraint on the edge of the path.The existing methods to study these two constraints independently can not deal with the two constraints exist at the same time.In this paper,we study a reachability query processing algorithm that supports both weight constraint and path length constraint.The specific research contents are as follows:First,this paper defines the k-step accessibility query problem with weight constraints: to find whether there is an accessible path between two query points in the graph that satisfies the length and weight interval constraints.On this basis,an efficient index construction method WKRI based on 2-hop idea is proposed.This index pre-generates an index label of reachable path information containing length and weight interval for each vertex in the graph,based on which efficient query processing can be realized.The WKRI method provides vertex selection strategy and two effective pruning strategies in the process of index construction,which reduces invalid traversal,speeds up index construction time and makes the minimum index constructed without redundant path information.Secondly,in order to further reduce index scale and improve query efficiency,an index optimization method WKRI+ based on minimum coverage is proposed.WKRI+ method firstly obtains the minimum point coverage of the graph,prays the vertices in the minimum point coverage,and then constructs two indexes WTH and WTH*.Among them,WTH index provides the fastest query efficiency,and WTH* index provides the smallest index size.Finally,three dimensions of index construction time,index size and query response time are taken as evaluation criteria,and the scale of weight set is changed to carry out experiments on 15 real data sets.Experimental results verify the feasibility and efficiency of the proposed solution when answering k-step reachability queries with weight constraints.