Math @ Duke

Publications [#235358] of Pankaj K. Agarwal
Papers Published
 Sankararaman, S; Agarwal, PK; Mølhave, T; Pan, J; Boedihardjo, AP, Modeldriven matching and segmentation of trajectories,
GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
(December, 2013),
pp. 234243 [doi]
(last updated on 2017/12/13)
Abstract: 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

