A trajectory data compression algorithm based on spatio-temporal characteristics

Abstract

Background With the growth of trajectory data, the large amount of data causes a lot of problems with storage, analysis, mining, etc. Most of the traditional trajectory data compression methods are focused on preserving spatial characteristic information and pay little attention to other temporal information on trajectory data, such as speed change points or stop points. Methods A data compression algorithm based on the spatio-temporal characteristics (CASC) of the trajectory data is proposed to solve this problem. This algorithm compresses trajectory data by taking the azimuth difference, velocity difference and time interval as parameters in order to preserve spatial-temporal characteristics. Microsoft’s Geolife1.3 data set was used for a compression test to verify the validity of the algorithm. The compression results were compared with the traditional Douglas-Peucker (DP), Top-Down Time Ratio (TD-TR) and Opening Window (OPW) algorithms. Compression rate, the direction information of trajectory points, vertical synchronization distance, and algorithm type (online/offline) were used to evaluate the above algorithms. Results The experimental results show that with the same compression rate, the ability of the CASC to retain the forward direction trajectory is optimal, followed by TD-TR, DP, and then OPW. The velocity characteristics of the trajectories are also stably retained when the speed threshold value is not more than 100%. Unlike the DP and TD-TR algorithms, CASC is an online algorithm. Compared with OPW, which is also an online algorithm, CASC has better compression quality. The error distributions of the four algorithms have been compared, and CASC is the most stable algorithm. Taken together, CASC outperforms DP, TD-TR and OPW in trajectory compression.

Keywords

• Trajectories data
• Spatial-temporal characteristics
• Data compression
• Online algorithm