Kevin Toohey
Abstract
Storing, querying, and analyzing trajectories is becoming increasingly important, as the availability and volumes of trajectory data increases. One important class of trajectory analysis is computing trajectory similarity. This paper introduces and compares four of the most common measures of trajectory similarity: longest common subsequence (LCSS), Fréchet distance, dynamic time warping (DTW), and edit distance. These four measures have been implemented in a new open source R package, freely available on CRAN [19]. The paper highlights some of the differences between these four similarity measures, using real trajectory data, in addition to indicating some of the important emerging applications for measurement of trajectory similarity.
- H. Alt and M. Godau. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry and Applications, 5(01n02):75--91, 1995.Google Scholar
Cross Ref
- D. Berndt and J. Clifford. Using dynamic time warping to find patterns in time series. In KDD workshop, volume 10, pages 359--370. Seattle, WA, 1994.Google ScholarDigital Library
- K. Buchin, M. Buchin, J. Gudmundsson, M. Löffler, and J. Luo. Detecting commuting patterns by clustering subtrajectories. In S.-H. Hong, H. Nagamochi, and T. Fukunaga, editors, Algorithms and Computation, volume 5369 of Lecture Notes in Computer Science, pages 644--655. Springer, 2008. Google ScholarDigital Library
- M. Buchin, S. Dodge, and B. Speckmann. Similarity of trajectories taking into account geographic context. Journal of Spatial Information Science, 9(1):101--124, 2014.Google Scholar
- L. Chen and R. Ng. On the marriage of lp-norms and edit distance. In Proc. 30th International Conference on Very Large Data Bases, pages 792--803, 2004. Google ScholarDigital Library
- L. Chen, M. T. Özsu, and V. Oria. Robust and fast similarity search for moving object trajectories. In Proc. ACM SIGMOD International Conference on Management of Data, SIGMOD '05, pages 491--502, New York, NY, USA, 2005. ACM. Google ScholarDigital Library
- S. Dodge. Exploring Movement Using Similarity Analysis. PhD thesis, Universität Zürich, 2011.Google Scholar
- C. Faloutsos, M. Ranganathan, and Y. Manolopoulos. Fast subsequence matching in time-series databases. SIGMOD Rec., 23(2):419--429, May 1994. Google ScholarDigital Library
- M. M. Fréchet. Sur quelques points du calcul fonctionnel. Rendiconti del Circolo Matematico di Palermo, 22(1):1--72, 1906.Google Scholar
- J. Gudmundsson, P. Laube, and T. Wolle. Movement patterns in spatiotemporal data. In Encyclopedia of GIS, pages 726--732. Springer US, 2008.Google ScholarCross Ref
- J. Gudmundsson, P. Laube, and T. Wolle. Computational movement analysis. In Springer handbook of geographic information, pages 423--438. Springer, 2012.Google Scholar
- J. Haase and U. Brefeld. Finding similar movements in positional data streams. In Proc. ECML/PKDD Workshop on Machine Learning and Data Mining for Sports Analytics, 2013.Google Scholar
- E. Keogh and M. Pazzani. Scaling up dynamic time warping for datamining applications. In Proc. 6th ACM International Conference on Knowledge Discovery and Data Mining, pages 285--289, 2000. Google ScholarDigital Library
- E. Keogh and C. A. Ratanamahatana. Exact indexing of dynamic time warping. Knowledge and Information Systems, 7(3):358--386, 2005. Google ScholarDigital Library
- P. Laube and R. S. Purves. How fast is a cow? Cross-scale analysis of movement data. Transactions in GIS, 15(3):401--418, 2011.Google ScholarCross Ref
- T. Li, H. Chang, M. Wang, B. Ni, R. Hong, and S. Yan. Crowded scene analysis: A survey. IEEE Transactions on Circuits and Systems for Video Technology, (99):1--20, 2014.Google Scholar
- M. Perše, M. Kristan, S. Kovačič, G. Vučkovič, and J. Perš. A trajectory-based analysis of coordinated team activity in a basketball game. Computer Vision and Image Understanding, 113(5):612--621, 2009. Computer Vision Based Analysis in Sport Environments. Google ScholarDigital Library
- P. Ranacher and K. Tzavella. How to compare movement? A review of physical movement similarity measures in geographic information science and beyond. Cartography and Geographic Information Science, 41(3):286--307, 2014.Google ScholarCross Ref
- K. Toohey. SimilarityMeasures: Trajectory Similarity Measures, 2015. R package version 1.4, http://CRAN.R-project.org/package=SimilarityMeasures.Google Scholar
- M. Vlachos, G. Kollios, and D. Gunopulos. Discovering similar multidimensional trajectories. In Proc. 18th International Conference on Data Engineering (ICDE), pages 673--684, 2002. Google ScholarDigital Library
- H. Wang, H. Su, K. Zheng, S. Sadiq, and X. Zhou. An effectiveness study on trajectory similarity measures. In Proc. 24th Australasian Database Conference, volume 137, pages 13--22, 2013. Google ScholarDigital Library
- Y. Yuan. Image-based gesture recognition with support vector machines. ProQuest, 2008.Google Scholar
- Z. Zhang, K. Huang, and T. Tan. Comparison of similarity measures for trajectory clustering in outdoor surveillance scenes. In Proc. 18th International Conference on Pattern Recognition (ICPR), volume 3, pages 1135--1138, 2006. Google ScholarDigital Library
Index Terms
- Trajectory similarity measures
Recommendations
Trajectory similarity clustering based on multi-feature distance measurement
With the development of GPS-enabled devices, wireless communication and storage technologies, trajectories representing the mobility of moving objects are accumulated at an unprecedented pace. They contain a large amount of temporal and spatial semantic ...
SST: Synchronized Spatial-Temporal Trajectory Similarity Search
AbstractThe volume of trajectory data has become tremendously large in recent years. How to effectively and efficiently search similar trajectories has become an important task. Firstly, to measure the similarity between a trajectory and a query, ...
Some cosine similarity measures and distance measures between q‐rung orthopair fuzzy sets
AbstractIn this paper, we consider some cosine similarity measures and distance measures between q‐rung orthopair fuzzy sets (q‐ROFSs). First, we define a cosine similarity measure and a Euclidean distance measure of q‐ROFSs, their properties are also ...
Comments