Research On Query Algorithms Of Road Network Shortest Path And Distance Based On Representation Learning

With the development of map-based applications and the proliferation of GPS-enabled mobile technologies,many location-based services providers have emerged in recent years.These providers process different types of queries every day,e.g.,finding the nearest restaurant,and planning travel routes.The most basic and important types of queries among them are the shortest path query and the shortest distance query.Its computational efficiency greatly affects the quality of service and user experience.The existing shortest path and its distance query algorithm do not fully exploit and utilize the Spatio-temporal information of query and path,and the algorithm computation efficiency cannot meet the practical application requirements.In this thesis,based on the analysis of the shortage of existing work,we study the shortest path and its distance query algorithm for road networks.In order to utilize the computational results of different path queries and to mine the distance information between road network vertexes,this thesis uses a representation learning model to capture the Spatio-temporal information in the road networks and query to improve the computational efficiency.The main research work of this thesis is as follows:(1)To address the problem that the existing approximate shortest distance query algorithm does not fully exploit the shortest path distance information,which leads to a large calculation error,this thesis proposes a representation learning-based shortest path query algorithm for road networks.Our method utilizes the representation learning model to embed the road network vertexes and estimates the shortest path distance between two vertexes by calculating the distance of the embedded vectors.Meanwhile,we propose a new training data generation method,which generates training data that can cover most of the area of the road network.Experiments on three real-world datasets have proved that our method is better than the state-of-the-art approximate shortest distance query algorithm in terms of error rate and computation time.(2)To address the problem that existing shortest path query algorithms do not consider sharing computation results among multiple queries and are not optimized for high concurrency scenarios,this thesis proposes a representation learning-based shortest path query algorithm for road networks.Our algorithm uses a representation learning model to learn the Spatio-temporal information of shortest path query and represents the query as embedding vector.After that,the algorithm clusters the batch queries into different query subsets based on the embedding vectors.Then,we use a grid-based cache structure to store the computation results of previous queries to improve the computation efficiency of batch shortest path queries.Experiments on a large real-world data set show that our method achieves better results than the state-of-the-art batch shortest path query algorithm in terms of hit ratio and computation time.