Research On Rule-based Shortest Path Query Over The Large Graphs

The shortest path query is a very important problem in graph data management.This paper studies the shortest path query problem based on some constraints.Different constraints correspond to different problems.They are a special type of shortest path query problem.In this paper,the shortest path based on constraint means that given the set of must-visited vertices,the shortest path returned passes through all vertices in the set of must-visited vertices and the path satisfies the constraint.The current work focuses on the shortest path problem on spatial datasets(the shortest distance between two vertices is expressed in Euclidean distance),which exhaustively lists all paths that satisfy the constraint,and selects the path with the smallest length as a solution to the problem.However,in an actual road network,the distance between two vertices is equal to the length of the shortest path between two vertices,which is often greater than the Euclidean distance.In addition,the existing algorithms for solving such problem are equivalent to enumerating all the permutations of the must-visited vertices that satisfy the constraint.However,most of the permutations are redundant for solving the shortest path problem,and an exhaustive approach results in a large number of repetitive calculations.In this paper,the corresponding algorithm is designed for each problem.The specific work is as follows:1.The shortest path query problem based on vertex constraint,that is,given some must-visited vertices,to find a shortest path from the starting vertex to the ending vertex and passing the given must-visited vertices.For this problem,the main work of this paper is: a novel and effective algorithm is proposed,and two optimizing techniques are designed to find the shortest path with vertex constraint.An approximate algorithm for polynomial time that can be applied to large graphs is designed,and the approximation ratio of the approximation algorithm is proved to be 3.A large number of experiments are performed on several real datasets,and the algorithm of this paper is compared with the most advanced algorithms.The experimental results verify the effectiveness of the algorithm.2.The rule-based shortest path query problem,that is,given the starting vertex and the ending vertex,to find a shortest path from the starting vertex to the ending vertex,so that the path passes through all the vertices in the user specified vertices set and the access of some vertices must meet a certain order.For this problem,the main work of this paper is as follows: the concept of generalized rule tree is proposed,and the algorithm for generating generalized rule tree is designed.The general rule tree is used to judge whether the algorithm finds a shortest path based on rule.A forward expansion algorithm based on optimal sub-path is designed.The algorithm can quickly solve the rule-based shortest path problem.The improved algorithm of forward expansion algorithm is designed which is the forward expansion algorithm based on the shortest priority strategy.A large number of experiments are designed on the real datasets and the algorithm of this paper is compared with the best performance algorithms.The experimental results verify the effectiveness of the proposed algorithm.This paper mainly studies the shortest path query based on some constraints,and designs the corresponding algorithm based on different problems corresponding to different constraints.The algorithm designed in this paper has better query performance than the existing algorithms in the same problem.