Skip to main content

Subtrajectory clustering: Models and algorithms

Publication ,  Conference
Agarwal, PK; Fox, K; Munagala, K; Nath, A; Pan, J; Taylor, E
Published in: Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
May 27, 2018

We propose a model for subtrajectory clustering'the clustering of subsequences of trajectories; each cluster of subtrajectories is represented as a pathlet, a sequence of points that is not necessarily a subsequence of an input trajectory. Given a set of trajectories, our clustering model attempts to capture the shared portions between them by assuming each trajectory is a concatenation of a small set of pathlets, with possible gaps in between. We present a single objective function for finding the optimal collection of pathlets that best represents the trajectories taking into account noise and other artifacts of the data. We show that the subtrajectory clustering problem is NP-Hard and present fast approximation algorithms for subtrajectory clustering. We further improve the running time of our algorithm if the input trajectories are “well-behaved." Finally, we present experimental results on both real and synthetic data sets. We show via visualization and quantitative analysis that the algorithm indeed handles the desiderata of being robust to variations, being efficient and accurate, and being data-driven.

Duke Scholars

Published In

Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

DOI

ISBN

9781450347068

Publication Date

May 27, 2018

Start / End Page

75 / 87
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Agarwal, P. K., Fox, K., Munagala, K., Nath, A., Pan, J., & Taylor, E. (2018). Subtrajectory clustering: Models and algorithms. In Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (pp. 75–87). https://doi.org/10.1145/3196959.3196972
Agarwal, P. K., K. Fox, K. Munagala, A. Nath, J. Pan, and E. Taylor. “Subtrajectory clustering: Models and algorithms.” In Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 75–87, 2018. https://doi.org/10.1145/3196959.3196972.
Agarwal PK, Fox K, Munagala K, Nath A, Pan J, Taylor E. Subtrajectory clustering: Models and algorithms. In: Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. 2018. p. 75–87.
Agarwal, P. K., et al. “Subtrajectory clustering: Models and algorithms.” Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2018, pp. 75–87. Scopus, doi:10.1145/3196959.3196972.
Agarwal PK, Fox K, Munagala K, Nath A, Pan J, Taylor E. Subtrajectory clustering: Models and algorithms. Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. 2018. p. 75–87.

Published In

Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

DOI

ISBN

9781450347068

Publication Date

May 27, 2018

Start / End Page

75 / 87