DynMDL: A Parallel Trajectory Segmentation Algorithm

Eleazar Leal, Le Gruenwald

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 languageEnglish (US)
Title of host publicationProceedings - 2018 IEEE International Congress on Big Data, BigData Congress 2018 - Part of the 2018 IEEE World Congress on Services
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages215-218
Number of pages4
ISBN (Electronic)9781538672327
DOIs
StatePublished - Sep 7 2018
Event7th IEEE International Congress on Big Data, BigData Congress 2018 - San Francisco, United States
Duration: Jul 2 2018Jul 7 2018

Publication series

NameProceedings - 2018 IEEE International Congress on Big Data, BigData Congress 2018 - Part of the 2018 IEEE World Congress on Services

Other

Other7th IEEE International Congress on Big Data, BigData Congress 2018
CountryUnited States
CitySan Francisco
Period7/2/187/7/18

    Fingerprint

Keywords

  • MDL principle
  • multicore algorithms
  • parallel computing
  • trajectory data
  • trajectory segmentation

Cite this

Leal, E., & Gruenwald, L. (2018). DynMDL: A Parallel Trajectory Segmentation Algorithm. In Proceedings - 2018 IEEE International Congress on Big Data, BigData Congress 2018 - Part of the 2018 IEEE World Congress on Services (pp. 215-218). [8457752] (Proceedings - 2018 IEEE International Congress on Big Data, BigData Congress 2018 - Part of the 2018 IEEE World Congress on Services). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/BigDataCongress.2018.00036