Spatio-temporal Indexing And Path Query Algorithm For Compressed Vehicle Trajectories

In recent years,with the popularity of GPS devices and the development of mobile Internet technology,the scale of trajectory data of moving objects collected by cloud data centers has grown exponentially.This data contains a wealth of mineable information and can provide an important source of data for Location-based services.By mining and analyzing trajectory data,you can plan travel plans,understand traffic laws,and analyze crowd behavior characteristics.However,massive trajectory data will undoubtedly bring a serious burden to trajectory analysis,storage,query and calculation.Therefore,how to effectively compress the spatio-temporal trajectory data and efficiently query the compressed trajectory data have become important research contents.To solve the above problems,we propose a path spatial query algorithm for compressed vehicle trajectories,and implement a corresponding system prototype.The specific work is as follows:In terms of the trajectory data compression,our compression coding is composed of the compression coding based on the Stroke segment and hash coding.The trajectory spatio-temporal compression process is as follows: Firstly,it matches the original trajectory point map to the road network and it obtains the compression coding based on the Stroke segment according to the Stroke road hierarchical structure and realize the trajectory spatial data compression;Secondly,it extracts the key variable speed points of the trajectory by the open window algorithm to realize the trajectory temporal data compression;Finally,a hash code is constructed to establish the relationship between trajectory space and time data,and the integrated compression of spatiotemporal data of vehicle trajectory is realized.In terms of the construction of the index structure and the trajectory query,firstly,it constructs the spatial index structure of the compression coding based on the Stroke segment of the vehicle trajectories by using suffix array.The suffix array is an index array that only needs to store the same length as the original string,which occupies less storage space and can effectively improve the efficiency of trajectory query.Secondly,based on this index structure and borrowing from the string approximation pattern matching algorithm,the point information algorithm,strict sub-path query algorithm based on suffix array and similar path query algorithm based on dynamic programming are designed for the paths corresponding to vehicle trajectories,where the degree of trajectory overlap is calculated using the longest common subsequence.Finally,based on the above query algorithm,a path query prototype system for compressed vehicle trajectories is implemented.Based on the above research,the experimental research is carried out with the road network and large-scale taxi trajectory data of Nanjing as an example.The experimental results indicate that for the original trajectory point spatial data,the compression ratio of the proposed compression coding method can reach 97:1.Compared with the conventional road segments-based coding mode,the proposed compression coding method has high path spatial queries performance.In the point information query of the path corresponding to the vehicle trajectory,the query efficiency can be increased by about 2 times.In the strict sub-path query of the vehicle trajectory,the query efficiency can be increased by about 8 times,and the growth rate of the query time is reduced by about 50% in the similar path query of the vehicle trajectory.This method plays a fundamental role in the data management of large-scale vehicle trajectories.