A Complexity-Invariant Distance Measure for Time Series
Abstract
The ubiquity of time series data across almost all human endeavors has produced a great interest in time series data mining in the last decade. While there is a plethora of classification algorithms that can be applied to time series, all of the current empirical evidence suggests that simple nearest neighbor classification is exceptionally difficult to beat. The choice of distance measure used by the nearest neighbor algorithm depends on the invariances required by the domain. For example, motion capture data typically requires invariance to warping. In this work we make a surprising claim. There is an invariance that the community has missed, complexity invariance. Intuitively, the problem is that in many domains the different classes may have different complexities, and pairs of complex objects, even those which subjectively may seem very similar to the human eye, tend to be further apart under current distance measures than pairs of simple objects. This fact introduces errors in nearest neighbor classification, where complex objects are incorrectly assigned to a simpler class. We introduce the first complexity-invariant distance measure for time series, and show that it generally produces significant improvements in classification accuracy. We further show that this improvement does not compromise efficiency, since we can lower bound the measure and use a modification of triangular inequality, thus making use of most existing indexing and data mining algorithms. We evaluate our ideas with the largest and most comprehensive set of time series classification experiments ever attempted, and show that complexity-invariant distance measures can produce improvements in accuracy in the vast majority of cases.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Multiscale analyses and features of entropy elucidate more information related to the complexity of a data stream than statistics alone.
“Multiscale analyses and features of entropy elucidate more information related to the complexity of a data stream than statistics alone40–42.”
From Sleep and temperature data from wearable devices support noninvasive detection of diabetes mellitus in a large-scale, retrospective analysis (2026) · cites this paper as [40]
Cites
An Introduction to Kolmogorov Complexity and Its Applications
Li, M., & Vitanyi, P. M. B. (2019) · Texts in computer science · doi:10.1007/978-3-030-11298-1 · Cited by 3,752 · see citing works
Fast subsequence matching in time-series databases
Faloutsos, C., Ranganathan, M., & Manolopoulos, Y. (1994) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/191839.191925 · Cited by 1,712 · see citing works
Querying and mining of time series data
Ding, H., Trajcevski, G., Scheuermann, P., Wang, X., & Keogh, E. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1454159.1454226 · Cited by 1,353 · see citing works
Self-citationChávez, E., Navarro, G., Baeza-Yates, R. A., & Marroquin, J. L. (2001) · ACM Computing Surveys · doi:10.1145/502807.502808 · Cited by 1,248 · see citing works
Using the triangle inequality to accelerate k-means
Elkan, C. (2003) · Cited by 705 · see citing works
Exact indexing of dynamic time warping
Keogh, E. (2002) · Cited by 594 · see citing works
Self-citationGasarch, W. I. (1997) · ACM SIGACT News · doi:10.1145/262301.1040343 · Cited by 583 · see citing works
Index-driven similarity search in metric spaces (Survey Article)
Hjaltason, G. R., & Samet, H. (2003) · ACM Transactions on Database Systems · doi:10.1145/958942.958948 · Cited by 439 · see citing works
The Anchors Hierarchy: Using the Triangle Inequality to Survive High Dimensional Data
Moore, A. (2000) · Cited by 145 · see citing works
Disk aware discord discovery: finding unusual time series in terabyte sized datasets
Yankov, D., Keogh, E., & Rebbapragada, U. D. (2008) · Knowledge and Information Systems · doi:10.1007/s10115-008-0131-9 · Cited by 139 · see citing works
Self-citationKeogh, E., Li, W., Xi, X., et al. (2008) · The VLDB Journal · doi:10.1007/s00778-008-0111-4 · Cited by 129 · see citing works
Self-citationCompression-based data mining of sequential data
Keogh, E., Lonardi, S., Ratanamahatana, C. A., Li, W., Lee, S., & Handley, J. C. (2007) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-006-0049-3 · Cited by 113 · see citing works
Self-citationA fast nearest-neighbor search algorithm
Orchard, M. T. (1991) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.1991.150755 · Cited by 102 · see citing works
Complexity analysis of stride interval time series by threshold dependent symbolic entropy
Aziz, W., & Arif, M. (2006) · European Journal of Applied Physiology · doi:10.1007/s00421-006-0226-5 · Cited by 100 · see citing works
Finding outlier light curves in catalogues of periodic variable stars
Protopapas, P., Giammarco, J. M., Faccioli, L., et al. (2006) · Monthly Notices of the Royal Astronomical Society · doi:10.1111/j.1365-2966.2006.10327.x · Cited by 81 · see citing works
Shape analysis for the automated identification of plants from images of leaves
Hearn, D. J. (2009) · Taxon · doi:10.1002/tax.583021 · Cited by 67 · see citing works
Bundo, M., Kaneoke, Y., Inao, S., Yoshida, J., Nakamura, A., & Kakigi, R. (2000) · Human Brain Mapping · doi:10.1002/1097-0193(200009)11:1 · Cited by 62 · see citing works
Finding Time Series Motifs in Disk-Resident Data
Mueen, A., Keogh, E., & Bigdely-Shamlo, N. (2009) · Proceedings · doi:10.1109/icdm.2009.15 · Cited by 46 · see citing works
Self-citationEfficiently Finding Arbitrarily Scaled Patterns in Massive Time Series Databases
Keogh, E. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-39804-2_24 · Cited by 45 · see citing works
Self-citationLi, K.-C., Yan, M., & Yuan, S. (2002) · Cited by 21 · see citing works
Autocannibalistic and Anyspace Indexing Algorithms with Application to Sensor Data Mining.
Ye, L., Wang, X., Keogh, E., et al. (2009) · SIAM International Conference on Data Mining · Cited by 11 · see citing works
Self-citationŽunić, J. D., Rosin, P. L., & Kopanja, L. (2006) · Lecture notes in computer science · doi:10.1007/11612704_2 · Cited by 11 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Classification of time series by shapelet transformation
Hills, J., Lines, J., Baranauskas, E., Mapp, J., & Bagnall, A. (2014) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-013-0322-1 · Cited by 538 · see citing works
Multi-task Self-Supervised Learning for Human Activity Detection
Saeed, A., Ozcelebi, T., & Lukkien, J. (2019) · Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies · doi:10.1145/3328932 · Cited by 346 · see citing works
Glucotypes reveal new patterns of glucose dysregulation
Hall, H., Perelman, D., Breschi, A., Limcaoco, P., Kellogg, R., McLaughlin, T., & Snyder, M. (2018) · PLOS Biology · doi:10.1371/journal.pbio.2005143 · Cited by 326 · see citing works
Classification of Heart Diseases Based On ECG Signals Using Long Short-Term Memory
Liu, M., & Kim, Y. (2018) · 2018 40th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC) · doi:10.1109/embc.2018.8512761 · Cited by 83 · see citing works
Burks, J. H., Joe, L., Kanjaria, K., Monsivais, C., O'laughlin, K., & Smarr, B. L. (2025) · PLOS Digital Health · doi:10.1371/journal.pdig.0000815 · Cited by 5 · see citing works
Viswanath, V. K., Navaneethan, S., Burks, J. H., Soltani, S., Kasl, P., Hartogensis, W., Dilchert, S., Hecht, F. M., Mason, A. E., Wang, E. J., et al. (2026) · Communications Medicine · doi:10.1038/s43856-026-01501-0
- Authors
- Batista, G. E. A. P. A., Wang, X., & Keogh, E. J.
- Affiliations
- Universidade de São Paulo (BR)
- University of California, Riverside (US)
- Venue
- Proceedings of the 2011 SIAM International Conference on Data Mining
- Published
- 2011-04-28
- Pages
- 699-710
- OpenAlex
- W2400311702
- Cited by
- 329
- References
- 22
- Citations by year
- 2026: 8 · 2025: 16 · 2024: 21 · 2023: 18 · 2022: 15 · 2021: 20 · 2020: 20 · 2019: 27 · 2018: 31 · 2017: 26 · 2016: 34 · 2015: 31 · 2014: 26 · 2013: 15 · 2012: 16
- FWCI
- 21.51
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- SIAM International Conference on Data Mining (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Signal Processing › Time Series Analysis and Forecasting
- Physical Sciences › Computer Science › Information Systems › Data Mining Algorithms and Applications
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Image Retrieval and Classification Techniques
- Keywords
- time series classification, nearest neighbor classification, time series distance measures, lower bounds, triangle inequality, time series indexing, motion capture data
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
