DynMDL: A Parallel Trajectory Segmentation Algorithm

Eleazar Leal; Le Gruenwald

doi:10.1109/BigDataCongress.2018.00036

DynMDL: A Parallel Trajectory Segmentation Algorithm

Eleazar Leal, Le Gruenwald

Computer Science (Duluth)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Scopus citations

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 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.
Pages	215-218
Number of pages	4
ISBN (Electronic)	9781538672327
DOIs	https://doi.org/10.1109/BigDataCongress.2018.00036
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

Publication series

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

Other

Other	7th IEEE International Congress on Big Data, BigData Congress 2018
Country/Territory	United States
City	San Francisco
Period	7/2/18 → 7/7/18

Bibliographical note

Funding Information:
ACKNOWLEDGMENT This work is supported in part by the National Science Foundation under Grant No. 1302439 and 1302423.We also thank Martin Werner [8] and Simon Zu.

Funding Information:
This work is supported in part by the National Science Foundation under Grant No. 1302439 and 1302423. We also thank Martin Werner [8] and Simon Zu.

Publisher Copyright:
© 2018 IEEE.

Keywords

MDL principle
multicore algorithms
parallel computing
trajectory data
trajectory segmentation

Publisher link

10.1109/BigDataCongress.2018.00036

Find It

Find It at U of M Libraries

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). Article 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

DynMDL: A Parallel Trajectory Segmentation Algorithm. / Leal, Eleazar; Gruenwald, Le.
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., 2018. p. 215-218 8457752 (Proceedings - 2018 IEEE International Congress on Big Data, BigData Congress 2018 - Part of the 2018 IEEE World Congress on Services).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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., 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., pp. 215-218, 7th IEEE International Congress on Big Data, BigData Congress 2018, San Francisco, United States, 7/2/18. https://doi.org/10.1109/BigDataCongress.2018.00036

Leal E, Gruenwald L. 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. Institute of Electrical and Electronics Engineers Inc. 2018. p. 215-218. 8457752. (Proceedings - 2018 IEEE International Congress on Big Data, BigData Congress 2018 - Part of the 2018 IEEE World Congress on Services). doi: 10.1109/BigDataCongress.2018.00036

Leal, Eleazar ; Gruenwald, Le. / DynMDL : A Parallel Trajectory Segmentation Algorithm. 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., 2018. pp. 215-218 (Proceedings - 2018 IEEE International Congress on Big Data, BigData Congress 2018 - Part of the 2018 IEEE World Congress on Services).

@inproceedings{ea2d0403295b4b2b86924fbf5184b0f2,

title = "DynMDL: A Parallel Trajectory Segmentation Algorithm",

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.",

keywords = "MDL principle, multicore algorithms, parallel computing, trajectory data, trajectory segmentation",

author = "Eleazar Leal and Le Gruenwald",

note = "Funding Information: ACKNOWLEDGMENT This work is supported in part by the National Science Foundation under Grant No. 1302439 and 1302423.We also thank Martin Werner [8] and Simon Zu. Funding Information: This work is supported in part by the National Science Foundation under Grant No. 1302439 and 1302423. We also thank Martin Werner [8] and Simon Zu. Publisher Copyright: {\textcopyright} 2018 IEEE.; 7th IEEE International Congress on Big Data, BigData Congress 2018 ; Conference date: 02-07-2018 Through 07-07-2018",

year = "2018",

month = sep,

day = "7",

doi = "10.1109/BigDataCongress.2018.00036",

language = "English (US)",

series = "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.",

pages = "215--218",

booktitle = "Proceedings - 2018 IEEE International Congress on Big Data, BigData Congress 2018 - Part of the 2018 IEEE World Congress on Services",

}

TY - GEN

T1 - DynMDL

T2 - 7th IEEE International Congress on Big Data, BigData Congress 2018

AU - Leal, Eleazar

AU - Gruenwald, Le

N1 - Funding Information: ACKNOWLEDGMENT This work is supported in part by the National Science Foundation under Grant No. 1302439 and 1302423.We also thank Martin Werner [8] and Simon Zu. Funding Information: This work is supported in part by the National Science Foundation under Grant No. 1302439 and 1302423. We also thank Martin Werner [8] and Simon Zu. Publisher Copyright: © 2018 IEEE.

PY - 2018/9/7

Y1 - 2018/9/7

N2 - 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.

AB - 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.

KW - MDL principle

KW - multicore algorithms

KW - parallel computing

KW - trajectory data

KW - trajectory segmentation

UR - http://www.scopus.com/inward/record.url?scp=85057758387&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85057758387&partnerID=8YFLogxK

U2 - 10.1109/BigDataCongress.2018.00036

DO - 10.1109/BigDataCongress.2018.00036

M3 - Conference contribution

AN - SCOPUS:85057758387

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

SP - 215

EP - 218

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

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 2 July 2018 through 7 July 2018

ER -

DynMDL: A Parallel Trajectory Segmentation Algorithm

Abstract

Publication series

Other

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this