The purpose of trajectory segmentation algorithms is to replace an input trajectory by a sub-trajectory with fewer points than the input, but that is also a good approximation to the original trajectory. As such, trajectory segmentation is an essential pre-processing step for trajectory mining algorithms, such as clustering. Among the segmentation strategies that are commonly used for trajectory clustering is Minimum Description Length (MDL)-based segmentation, which consists in finding a sub-trajectory such that the sum of its distance to the input trajectory and its overall length is minimum. However, there are no efficient algorithms for optimal MDL-based segmentation; there are only approximate algorithms. In this work we fill this gap by proposing a parallel multicore algorithm for MDL-based trajectory segmentation. We use three real-life datasets to show that our algorithm achieves optimal MDL, and compare its performance against Traclus, the state-of-the-art approximate Description Length (DL) segmentation algorithm.
|Original language||English (US)|
|Title of host publication||Proceedings - 2018 IEEE International Congress on Big Data, BigData Congress 2018 - Part of the 2018 IEEE World Congress on Services|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||4|
|State||Published - Sep 7 2018|
|Event||7th IEEE International Congress on Big Data, BigData Congress 2018 - San Francisco, United States|
Duration: Jul 2 2018 → Jul 7 2018
|Name||Proceedings - 2018 IEEE International Congress on Big Data, BigData Congress 2018 - Part of the 2018 IEEE World Congress on Services|
|Other||7th IEEE International Congress on Big Data, BigData Congress 2018|
|Period||7/2/18 → 7/7/18|
Bibliographical noteFunding Information:
ACKNOWLEDGMENT This work is supported in part by the National Science Foundation under Grant No. 1302439 and 1302423.We also thank Martin Werner  and Simon Zu.
This work is supported in part by the National Science Foundation under Grant No. 1302439 and 1302423. We also thank Martin Werner  and Simon Zu.
© 2018 IEEE.
- MDL principle
- multicore algorithms
- parallel computing
- trajectory data
- trajectory segmentation