Research And Implementation Of Efficient Map Matching Algorithm And Trajectory Similarity Query

Mobile positioning technology is developing rapidly in advance,and it becomes possible to collect large-scale trajectory data using the Global Positioning System(Global Positioning System,usually referred to as GPS).Trajectory data is a key part of Location Based Service(LBS).However,due to GPS positioning errors,trajectory data is often full of noise.One of the most common ways to eliminate errors is to apply a road network matching algorithm(map matching)to the trajectory data,that is,to match the trajectory data to the road segments in the digital road network.In addition,the trajectory similarity query can obtain extremely valuable information in the trajectory data,such as the mining of common human motion patterns,path navigation in tourism and parking of vehicles and other application scenarios,and large-scale trajectory data can also be compressed to Saving space and management resources occupied by data plays an important role in trajectory data analysis.As the scale of trajectory data continues to increase,road network matching algorithms need to be able to process larger-scale trajectory data and ensure the efficiency of the algorithm in terms of time and space efficiency.The method is to perform Dijkstra algorithm search for each point in the road network through pre-calculation to calculate the path and distance labels between the end points of the road network.The index of the shortest path between the end points of a road network,the most time-consuming alternative in the road network matching process-the repeated shortest distance query,is optimized for a linear time search O(n).While ensuring the matching accuracy,the algorithm proposed in this paper actually reduces the search space size and time length.Then,the existing dynamic time warping(DTW)and extensive public road section(LCRS)index methods implement a trajectory similarity search algorithm,providing efficient trajectory similarity query.Finally,through experiments on large-scale trajectory data,the algorithm proposed in this paper is compared with the current popular algorithm,which proves the high performance of the pre-computer-based road network matching algorithm and trajectory similarity query algorithm.