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 pr...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Office of Control and Information Technology
2024-12-01
|
| Series: | Kongzhi Yu Xinxi Jishu |
| Subjects: | |
| Online Access: | http://ctet.csrzic.com/thesisDetails#10.13889/j.issn.2096-5427.2024.05.700 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849224634295123968 |
|---|---|
| author | GAO Wei QIAN Chengyang ZHANG Qi XIE Hongquan |
| author_facet | GAO Wei QIAN Chengyang ZHANG Qi XIE Hongquan |
| author_sort | GAO Wei |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-39bf594eb7cf40ffa1d583c63e7d167f |
| institution | Kabale University |
| issn | 2096-5427 |
| language | zho |
| publishDate | 2024-12-01 |
| publisher | Editorial Office of Control and Information Technology |
| record_format | Article |
| series | Kongzhi Yu Xinxi Jishu |
| spelling | doaj-art-39bf594eb7cf40ffa1d583c63e7d167f2025-08-25T06:57:45ZzhoEditorial Office of Control and Information TechnologyKongzhi Yu Xinxi Jishu2096-54272024-12-01435073042896Trajectory Similarity Algorithm Based on DTW and Trajectory Point CompressionGAO WeiQIAN ChengyangZHANG QiXIE HongquanThe 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.http://ctet.csrzic.com/thesisDetails#10.13889/j.issn.2096-5427.2024.05.700spatio-temporal trajectorydynamic time warping(DTW)trajectory similaritytime costdata compression |
| spellingShingle | GAO Wei QIAN Chengyang ZHANG Qi XIE Hongquan Trajectory Similarity Algorithm Based on DTW and Trajectory Point Compression Kongzhi Yu Xinxi Jishu spatio-temporal trajectory dynamic time warping(DTW) trajectory similarity time cost data compression |
| title | Trajectory Similarity Algorithm Based on DTW and Trajectory Point Compression |
| title_full | Trajectory Similarity Algorithm Based on DTW and Trajectory Point Compression |
| title_fullStr | Trajectory Similarity Algorithm Based on DTW and Trajectory Point Compression |
| title_full_unstemmed | Trajectory Similarity Algorithm Based on DTW and Trajectory Point Compression |
| title_short | Trajectory Similarity Algorithm Based on DTW and Trajectory Point Compression |
| title_sort | trajectory similarity algorithm based on dtw and trajectory point compression |
| topic | spatio-temporal trajectory dynamic time warping(DTW) trajectory similarity time cost data compression |
| url | http://ctet.csrzic.com/thesisDetails#10.13889/j.issn.2096-5427.2024.05.700 |
| work_keys_str_mv | AT gaowei trajectorysimilarityalgorithmbasedondtwandtrajectorypointcompression AT qianchengyang trajectorysimilarityalgorithmbasedondtwandtrajectorypointcompression AT zhangqi trajectorysimilarityalgorithmbasedondtwandtrajectorypointcompression AT xiehongquan trajectorysimilarityalgorithmbasedondtwandtrajectorypointcompression |