(k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping

Milutin Brankovic, Kevin Buchin, Koen Klaren, André Nusser, Aleksandr Popov, Sampson Wong

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

Due to the massively increasing amount of available geospatial data and the need to present it in an understandable way, clustering this data is more important than ever. As clusters might contain a large number of objects, having a representative for each cluster significantly facilitates understanding a clustering. Clustering methods relying on such representatives are called center-based. In this work we consider the problem of center-based clustering of trajectories.

In this setting, the representative of a cluster is again a trajectory. To obtain a compact representation of the clusters and to avoid overfitting, we restrict the complexity of the representative trajectories by a parameter l. This restriction, however, makes discrete distance measures like dynamic time warping (DTW) less suited.

There is recent work on center-based clustering of trajectories with a continuous distance measure, namely, the Fréchet distance. While the Fréchet distance allows for restriction of the center complexity, it can also be sensitive to outliers, whereas averaging-type distance measures, like DTW, are less so. To obtain a trajectory clustering algorithm that allows restricting center complexity and is more robust to outliers, we propose the usage of a continuous version of DTW as distance measure, which we call continuous dynamic time warping (CDTW). Our contribution is twofold:
(1) To combat the lack of practical algorithms for CDTW, we develop an approximation algorithm that computes it.
(2) We develop the first clustering algorithm under this distance measure and show a practical way to compute a center from a set of trajectories and subsequently iteratively improve it.

To obtain insights into the results of clustering under CDTW on practical data, we conduct extensive experiments.
Original languageEnglish
Title of host publicationSIGSPATIAL '20
Subtitle of host publicationProceedings of the 28th International Conference on Advances in Geographic Information Systems
EditorsChang-Tien Lu, Fusheng Wang, Goce Trajcevski, Yan Huang, Shawn Newsam, Li Xiong
Place of PublicationNew York, NY, United States
PublisherAssociation for Computing Machinery, Inc
Pages99-110
Number of pages12
ISBN (Electronic)978-1-4503-8019-5
DOIs
Publication statusPublished - 13 Nov 2020
Event28th International Conference on Advances in Geographic Information Systems - Online, Seattle, United States
Duration: 3 Nov 20206 Nov 2020
https://sigspatial2020.sigspatial.org/

Conference

Conference28th International Conference on Advances in Geographic Information Systems
Abbreviated titleACM SIGSPATIAL 2020
CountryUnited States
CitySeattle
Period3/11/206/11/20
Internet address

Keywords

  • Continuous Dynamic Time Warping
  • Trajectory Clustering
  • Trajectory Similarity

Fingerprint Dive into the research topics of '(k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping'. Together they form a unique fingerprint.

Cite this