The DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.
Discovering similar multidimensional trajectories
Abstract
We investigate techniques for analysis and retrieval of object trajectories in two or three dimensional space. Such data usually contain a large amount of noise, that has made previously used metrics fail. Therefore, we formalize non-metric similarity functions based on the longest common subsequence (LCSS), which are very robust to noise and furthermore provide an intuitive notion of similarity between trajectories by giving more weight to similar portions of the sequences. Stretching of sequences in time is allowed, as well as global translation of the sequences in space. Efficient approximate algorithms that compute these similarity measures are also provided. We compare these new methods to the widely used Euclidean and time warping distance functions (for real and synthetic data) and show the superiority of our approach, especially in the strong presence of noise. We prove a weaker version of the triangle inequality and employ it in an indexing structure to answer nearest neighbor queries. Finally, we present experimental results that validate the accuracy and efficiency of our approach.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1973) · CERN Document Server (European Organization for Nuclear Research) · Cited by 12,895
Dynamic Programming Algorithm Optimization for Spoken Word Recognition
Sakoe, H., & Chiba, S. (1978) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/tassp.1978.1163055 · Cited by 6,727
Pattern Classification and Scene Analysis.
Clarke, M. R. B., Duda, R. O., & Hart, P. E. (1974) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2344977 · Cited by 3,222
(1999) · Cited by 3,186
(1994) · Knowledge Discovery and Data Mining · Cited by 3,137
When Is ''Nearest Neighbor'' Meaningful?
Beyer, K., Goldstein, J., Ramakrishnan, R., & Shaft, U. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-49257-7_15 · Cited by 2,403
Efficient similarity search in sequence databases
Agrawal, R., Faloutsos, C., & Swami, A. (1993) · Lecture Notes in Computer Science · doi:10.1007/3-540-57301-1_5 · Cited by 1,979
Fast subsequence matching in time-series databases
Faloutsos, C., Ranganathan, M., & Manolopoulos, Y. (1994) · Proceedings of the 1994 ACM SIGMOD international conference on Management of data · doi:10.1145/191839.191925 · Cited by 1,709
Faloutsos, C., & Lin, K.-I. (1995) · Proceedings of the 1995 ACM SIGMOD international conference on Management of data - SIGMOD '95 · doi:10.1145/223784.223812 · Cited by 897
Locally adaptive dimensionality reduction for indexing large time series databases
Keogh, E., Chakrabarti, K., Pazzani, M., & Mehrotra, S. (2001) · Proceedings of the 2001 ACM SIGMOD international conference on Management of data · doi:10.1145/375663.375680 · Cited by 866
Cited by
Data mining: concepts and techniques
(2012) · Choice Reviews Online · doi:10.5860/choice.49-3305 · Cited by 28,531
Exact indexing of dynamic time warping
Keogh, E., & Ratanamahatana, C. A. (2005) · Knowledge and Information Systems · doi:10.1007/s10115-004-0154-9 · Cited by 1,962
Time-series clustering – A decade review
Aghabozorgi, S., Seyed Shirkhorshidi, A., & Ying Wah, T. (2015) · Information Systems · doi:10.1016/j.is.2015.04.007 · Cited by 1,826
A symbolic representation of time series, with implications for streaming algorithms
Lin, J., Keogh, E., Lonardi, S., & Chiu, B. (2003) · Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery · doi:10.1145/882082.882086 · Cited by 1,799
Experiencing SAX: A novel symbolic representation of time series
Lin, J., Keogh, E., Wei, L., & Lonardi, S. (2007) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-007-0064-z · Cited by 1,618
A survey on deep learning and its applications
Dong, S., Wang, P., & Abbas, K. (2021) · Computer Science Review · doi:10.1016/j.cosrev.2021.100379 · Cited by 1,544
A review on time series data mining
Fu, T.-C. (2011) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2010.09.007 · Cited by 1,500
Trajectory clustering: a partition-and-group framework
Lee, J.-G., Han, J., & Whang, K.-Y. (2007) · Proceedings of the 2007 ACM SIGMOD international conference on Management of data · doi:10.1145/1247480.1247546 · Cited by 1,363
Ding, H., Trajcevski, G., Scheuermann, P., Wang, X., & Keogh, E. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1454159.1454226 · Cited by 1,354
Robust and fast similarity search for moving object trajectories
Chen, L., Özsu, M. T., & Oria, V. (2005) · Proceedings of the 2005 ACM SIGMOD international conference on Management of data · doi:10.1145/1066157.1066213 · Cited by 1,336
Esling, P., & Agon, C. (2012) · ACM Computing Surveys · doi:10.1145/2379776.2379788 · Cited by 997
Experimental comparison of representation methods and distance measures for time series data
Wang, X., Mueen, A., Ding, H., Trajcevski, G., Scheuermann, P., & Keogh, E. (2013) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-012-0250-5 · Cited by 845
Map-matching for low-sampling-rate GPS trajectories
Lou, Y., Zhang, C., Zheng, Y., Xie, X., Wang, W., & Huang, Y. (2009) · Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems · doi:10.1145/1653771.1653820 · Cited by 797
On The Marriage of Lp-norms and Edit Distance
Chen, L., & Ng, R. (2004) · Proceedings 2004 VLDB Conference · doi:10.1016/b978-012088469-8.50070-x · Cited by 774
Weighted dynamic time warping for time series classification
Jeong, Y.-S., Jeong, M. K., & Omitaomu, O. A. (2011) · Pattern Recognition · doi:10.1016/j.patcog.2010.09.022 · Cited by 695
k-Shape: Efficient and Accurate Clustering of Time Series
Paparrizos, J., & Gravano, L. (2015) · Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2723372.2737793 · Cited by 680
Probabilistic discovery of time series motifs
Chiu, B., Keogh, E., & Lonardi, S. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956808 · Cited by 573
The BOSS is concerned with time series classification in the presence of noise
Schäfer, P. (2015) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-014-0377-7 · Cited by 560
Exact Indexing of Dynamic Time Warping
Keogh, E. (2002) · VLDB '02: Proceedings of the 28th International Conference on Very Large Databases · doi:10.1016/b978-155860869-6/50043-3 · Cited by 532
Crowded Scene Analysis: A Survey
Li, T., Chang, H., Wang, M., Ni, B., Hong, R., & Yan, S. (2015) · IEEE Transactions on Circuits and Systems for Video Technology · doi:10.1109/tcsvt.2014.2358029 · Cited by 479
A Survey of Vision-Based Trajectory Learning and Analysis for Surveillance
Morris, B. T., & Trivedi, M. M. (2008) · IEEE Transactions on Circuits and Systems for Video Technology · doi:10.1109/tcsvt.2008.927109 · Cited by 474
Discovery of convoys in trajectory databases
Jeung, H., Yiu, M. L., Zhou, X., Jensen, C. S., & Shen, H. T. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1453856.1453971 · Cited by 431
Lubba, C. H., Sethi, S. S., Knaute, P., Schultz, S. R., Fulcher, B. D., & Jones, N. S. (2019) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-019-00647-x · Cited by 431
On Discovering Moving Clusters in Spatio-temporal Data
Kalnis, P., Mamoulis, N., & Bakiras, S. (2005) · Lecture Notes in Computer Science · doi:10.1007/11535331_21 · Cited by 420
Making Time-series Classification More Accurate Using Learned Constraints
Ratanamahatana, C. A., & Keogh, E. (2004) · Proceedings of the 2004 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972740.2 · Cited by 407
A word at a time: computing word relatedness using temporal semantic analysis
Radinsky, K., Agichtein, E., Gabrilovich, E., & Markovitch, S. (2011) · Proceedings of the 20th international conference on World wide web · doi:10.1145/1963405.1963455 · Cited by 405
Deep Learning for Intelligent Transportation Systems: A Survey of Emerging Trends
Veres, M., & Moussa, M. (2020) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2019.2929020 · Cited by 394
Morris, B. T., & Trivedi, M. M. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.64 · Cited by 349
Using dynamic time warping distances as features for improved time series classification
Kate, R. J. (2016) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-015-0418-x · Cited by 348
Path Similarity Skeleton Graph Matching
Bai, X., & Latecki, L. J. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.70769 · Cited by 343
Swarm: mining relaxed temporal moving object clusters
Li, Z., Ding, B., Han, J., & Kays, R. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920934 · Cited by 325
A review of moving object trajectory clustering algorithms
Yuan, G., Sun, P., Zhao, J., Li, D., & Wang, C. (2017) · Artificial Intelligence Review · doi:10.1007/s10462-016-9477-7 · Cited by 323
Indexing spatio-temporal trajectories with Chebyshev polynomials
Cai, Y., & Ng, R. (2004) · Proceedings of the 2004 ACM SIGMOD international conference on Management of data · doi:10.1145/1007568.1007636 · Cited by 309
Wearable Sensors for Real-Time Kinematics Analysis in Sports: A Review
Rana, M., & Mittal, V. (2021) · IEEE Sensors Journal · doi:10.1109/jsen.2020.3019016 · Cited by 298
Rotation-invariant similarity in time series using bag-of-patterns representation
Lin, J., Khade, R., & Li, Y. (2012) · Journal of Intelligent Information Systems · doi:10.1007/s10844-012-0196-5 · Cited by 295
Deep Representation Learning for Trajectory Similarity Computation
Li, X., Zhao, K., Cong, G., Jensen, C. S., & Wei, W. (2018) · 2018 IEEE 34th International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2018.00062 · Cited by 279
A PCA-based similarity measure for multivariate time series
Yang, K., & Shahabi, C. (2004) · Proceedings of the 2nd ACM international workshop on Multimedia databases · doi:10.1145/1032604.1032616 · Cited by 276
Trajectory Clustering and an Application to Airspace Monitoring
Gariel, M., Srivastava, A. N., & Feron, E. (2011) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2011.2160628 · Cited by 275
A Survey on Trajectory Data Management, Analytics, and Learning
Wang, S., Bao, Z., Culpepper, J. S., & Cong, G. (2022) · ACM Computing Surveys · doi:10.1145/3440207 · Cited by 267
Clustering of Vehicle Trajectories
Atev, S., Miller, G., & Papanikolopoulos, N. P. (2010) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2010.2048101 · Cited by 257
Hierarchical and Networked Vehicle Surveillance in ITS: A Survey
Tian, B., Morris, B. T., Tang, M., Liu, Y., Yao, Y., Gou, C., Shen, D., & Tang, S. (2017) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2016.2552778 · Cited by 160
Time Geography and Space–Time Prism
Miller, H. J. (2017) · International Encyclopedia of Geography · doi:10.1002/9781118786352.wbieg0431 · Cited by 84
Gashi, S., Di Lascio, E., & Santini, S. (2019) · Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies · doi:10.1145/3314400 · Cited by 74
Metadata
- Authors
- Vlachos, M., Kollios, G., & Gunopulos, D.
- Venue
- Proceedings 18th International Conference on Data Engineering
- Publisher
- IEEE Comput. Soc
- Published
- 2003-06-25
- Pages
- 673-684
- ISSN
- 1084-4627 (ISSN-L)
- OpenAlex
- W2147880780
- Cited by
- 1,468
- References
- 24
- FWCI
- 41.34
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.