Reachability Query Based On Weight Constraint In Large Graph

The reachability query is used to study whether there is a reachable path between a given source point and an endpoint in a graph.The reachability query based on weight constraint is one of the reachability queries,which is used to answer whether there is a path between the vertices of two given queries,and the weight of each edge satisfies the given constraint conditions.Compared with traditional reachability query,weighted constrained reachability query is more meaningful in real life,such as gene protein biological network,communication network,road traffic network,etc.Data containing specific information are often recorded on the edge of these graphs to describe the strength of correlation between vertices,and the correlation of constraint information can't use the traditional of queries to reflect,it can only be handled by reachable queries based on weight constraints.The existing algorithms based on weights constraint accessibility query have fast query response time,but the index size built by them is too large to deal with large-scale data graphs under the condition of limited memory.To solve the above problems,three efficient indexes are proposed in this paper to support efficient processing of weight constrained reachable queries on large-scale data graphs in a limited memory environment.The research contents of this paper are as follows:Firstly,a 2-hop index based on weighted-graph and its construction algorithm is proposed.The algorithm determines the processing order of vertices based on the degree of vertices and constructs the 2-hop index of weighted graphs based on the order.The basic idea of this method is to transform the weighted constrained reachable query on a weighted graph into a set intersection operation based on vertex labels.Considering the high time and space cost of building a 2-hop index based on a weighted graph,a 2-hop index method based on minimum and maximum spanning tree is proposed.The method first constructs the minimum and maximum spanning trees of the original image,and then constructs the index on the spanning tree in order of degree from large to small,so as to reduce the time and space cost of index building.Secondly,considering that the vertex processing order will greatly affect the size and construction time of the 2-hop index,an optimal 2-hop index construction strategy is proposed.Different from the 2-hop index method proposed above,the optimization method is to dynamically determine the next most suitable vertex according to the change of the molecular graph of the vertex in the process of building the 2-hop index,so as to reduce the size of the 2-hop index and the construction time.Specifically,on the basis of a spanning tree,this method constructs a 2-hop index by finding the middle node of the tree as the hop point.After deleting this point,several subtrees can be obtained.Repeat the above operation for each subtree.Finally,based on multiple real data sets,experimental tests are conducted to verify the efficiency of the proposed algorithm with index size,index construction time and query response time as indexes.The experimental results show that both the optimization strategy based on the large vertex and the optimization strategy based on intermediate nodes can effectively reduce the index size,and the latter has better query efficiency.