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.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Scaling up dynamic time warping for datamining applications
Keogh, E. J., & Pazzani, M. J. (2000) · Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/347090.347153 · Cited by 820
Fast Time Sequence Indexing for Arbitrary Lp Norms
Yi, B.-K., & Faloutsos, C. (2018) · doi:10.1184/r1/6605618 · Cited by 650
Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases
Agrawal, R., Lin, K.-I., Sawhney, H., & Shim, K. (1995) · Cited by 649
Trajectory clustering with mixtures of regression models
Gaffney, S., & Smyth, P. (1999) · Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/312129.312198 · Cited by 443
Mobile computing and databases-a survey
Barbará, D. (1999) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.755619 · Cited by 385
Landmarks: a new model for similarity-based pattern querying in time series databases
Perng, C.-S., Wang, H., Zhang, S. R., & Parker, D. S. (2002) · Proceedings of 16th International Conference on Data Engineering (Cat. No.00CB37073) · doi:10.1109/icde.2000.839385 · Cited by 297
Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces
Chakrabarti, K., & Mehrotra, S. (2000) · Cited by 230
Deformable Markov model templates for time-series pattern matching
Ge, X., & Smyth, P. (2000) · Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/347090.347109 · Cited by 178
Similarity search for multidimensional data sequences
Lee, S., Chun, S.-J., Kim, D., et al. (2002) · Proceedings - International Conference on Data Engineering · doi:10.1109/icde.2000.839473 · Cited by 155
Variable length queries for time series data
Kahveci, T., & Singh, A. K. (2002) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2001.914838 · Cited by 146
Supporting fast search in time series for movement patterns in multiple scales
Qu, Y., Wang, C., & Wang, X. S. (1998) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/288627.288664 · Cited by 76
Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbour Searches
Goldstein, J., & Ramakrishnan, R. (2000) · Very Large Data Bases · Cited by 47
THE CAMERA MOUSE: PRELIMINARY INVESTIGATION OF AUTOMATED VISUAL TRACKING FOR COMPUTER ACCESS
Gips, J., Betke, M., & Fleming, P. J. S. (2000) · Cited by 32
Bounded similarity querying for time-series data
Goldin, D., Millstein, T. D., & Kutlu, A. (2004) · Information and Computation · doi:10.1016/j.ic.2004.07.001 · Cited by 24
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
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.