Trajectory Similarity Algorithm Based on DTW and Trajectory Point Compression

The rapid development of technologies including wireless communication, video surveillance, and satellite positioning has led to the generation of substantial amounts of trajectory data from the movement of mobile device holders. Understanding the behavior characteristics of these holders through processing massive trajectory data has become an important issue to be addressed using trajectory similarity algorithms. To optimize the computational efficiency of the algorithm while maintaining its accuracy, this paper presents an algorithm based on an improved dynamic time warping (DTW) algorithm, i.e. the compression DTW (CN-DTW) algorithm to overcome the deficiencies of long running time and ill-conditioned alignment in the DTW algorithm. A duplicate point removal algorithm is introduced for trajectory preprocessing, where time intervals serve as thresholds to delete trajectory points with identical latitude and longitude values. This algorithm also allows for preserving trajectory shapes by retaining feature points, thereby minimizing the impact of data compression on algorithm accuracy. Experiments were performed on the DTW algorithm, improved DTW algorithm, and CN-DTW algorithm by a ladder method. The experimental results indicated that both the CN-DTW and the improved DTW algorithms achieved similar accuracy levels, with enhancements over the DTW algorithm. However, the CN-DTW algorithm reduced running time by about 30% compared with the improved DTW algorithm and about 20% compared with the DTW algorithm, highlighting its advantages in terms of accuracy and running time.