Research On The Optimal Path Query Methods In Temporal Graphs

The shortest path query has been an important problem in the research field of graph,and it is used to compute the shortest path of a vertex to the other vertices,which has a wide range of applications.The main characteristic is extended from the starting vertex layer by layer until to the ending vertex.The classic shortest path query is usually defined in the static graphs,and there have been a lot of mature and efficient query algorithms up to now.However,in many practical applications,the graph models usually have time sequences,such as the temporal graph.The classic shortest path query algorithm has met a lot of challenges when dealing with this graph model,and often cannot get the optimal solution to meet the conditions of the query.In this thesis,we study the problem of path query in temporal graphs,and put forward the optimal path query algorithm according to the characteristics of the temporal graph.In addition,the graph's scale will be growing due to the big data environment,so we extend the algorithm and propose a distributed query algorithm based on Hadoop.First of all,we describe the concept and characteristics of the temporal graph,and define the five "optimal" paths: the earliest arrival path,the latest departure path,the least time path,the least transfer path and the minimum cost path,based on the consideration of time cost and fee,at the same time put forward the in-edge representation of the temporal graph.Secondly,according to the shortcomings of the classical shortest path query algorithm,we propose an optimal path query algorithm based on the temporal graph.The algorithm adopts the strategy of midway vertex elimination based on conditional constraints,and uses the reverse search method which is started from the target vertex to the starting vertex,which can effectively improve the efficiency of the query.In addition,with the development of information technology,the scale of the graph will be enlarged,and the centralized solution cannot meet the requirement of large-scale query.Therefore,in this thesis,the optimal path query algorithm is extended,and the MapReduce programming model is used for the big data environment.A distributed computing method based on Hadoop is proposed in this thesis.Finally,we experiment with the algorithm in the centralized and the distributed environment,the experimental results show that the two kinds of optimal path query methods proposed in this thesis have higher efficiency and accuracy.