Model-driven matching and segmentation of trajectories

Journal Article

A fundamental problem in analyzing trajectory data is to identify common patterns between pairs or among groups of trajectories. In this paper, we consider the problem of matching similar portions between a pair of trajectories, each observed as a sequence of points sampled from it. We present new measures of trajectory similarity - both local and global - between a pair of trajectories to distinguish between similar and dissimilar portions. We then use this model to perform segmentation of a set of trajectories into fragments, contiguous portions of trajectories shared by many of them. Our model for similarity is robust under noise and sampling rate variations. The model also yields a score which can be used to rank multiple pairs of trajectories according to similarity, e.g. in clustering applications. We present quadratic time algorithms to compute the similarity between trajectory pairs under our measures together with algorithms to identify fragments in a large set of trajectories efficiently using the similarity model. Finally, we present an extensive experimental study evaluating the effectiveness of our approach on real datasets, comparing it with earlier approaches. Our experiments show that our model for similarity is highly accurate in distinguishing similar and dissimilar portions as compared to earlier methods even with sparse sampling. Further, our segmentation algorithm is able to identify a small set of fragments capturing the common parts of trajectories in the dataset. © 2013 ACM.

Full Text

Duke Authors

Cited Authors

  • Sankararaman, S; Agarwal, PK; Mølhave, T; Pan, J; Boedihardjo, AP

Published Date

  • December 1, 2013

Published In

  • Gis: Proceedings of the Acm International Symposium on Advances in Geographic Information Systems

Start / End Page

  • 234 - 243

Digital Object Identifier (DOI)

  • 10.1145/2525314.2525360

Citation Source

  • Scopus