  With recent advances in sensing and tracking technology, trajectory data is
becoming increasingly pervasive and analysis of trajectory data is becoming
exceedingly important. A fundamental problem in analyzing trajectory data is
that of identifying common patterns between pairs or among groups of
trajectories. In this paper, we consider the problem of identifying 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. Our model is robust under noise and outliers, it does not
make any assumptions on the sampling rates on either trajectory, and it works
even if they are partially observed. Additionally, the model also yields a
scalar similarity score which can be used to rank multiple pairs of
trajectories according to similarity, e.g. in clustering applications. We also
present efficient algorithms for computing the similarity under our measures;
the worst-case running time is quadratic in the number of sample points.
  Finally, we present an extensive experimental study evaluating the
effectiveness of our approach on real datasets, comparing with it with earlier
approaches, and illustrating many issues that arise in trajectory data. Our
experiments show that our approach is highly accurate in distinguishing similar
and dissimilar portions as compared to earlier methods even with sparse
sampling.
