The DOI matches its Crossref record; 35 of the 35 references it cites were found in a registry or an index.
Making Time-series Classification More Accurate Using Learned Constraints
Abstract
It has long been known that Dynamic Time Warping (DTW) is superior to Euclidean distance for classification and clustering of time series. However, until lately, most research has utilized Euclidean distance because it is more efficiently calculated. A recently introduced technique that greatly mitigates DTWs demanding CPU time has sparked a flurry of research activity. However, the technique and its many extensions still only allow DTW to be applied to moderately large datasets. In addition, almost all of the research on DTW has focused exclusively on speeding up its calculation; there has been little work done on improving its accuracy. In this work, we target the accuracy aspect of DTW performance and introduce a new framework that learns arbitrary constraints on the warping path of the DTW calculation. Apart from improving the accuracy of classification, our technique as a side effect speeds up DTW by a wide margin as well. We show the utility of our approach on datasets from diverse domains and demonstrate significant gains in accuracy and efficiency.
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
Artificial intelligence: a modern approach
(1995) · Choice Reviews Online · doi:10.5860/choice.33-1577 · Cited by 21,974
Artificial intelligence: A modern approach
Nilsson, N. J. (1996) · Artificial Intelligence · doi:10.1016/0004-3702(96)00007-0 · Cited by 10,583
Fundamentals of speech recognition
Rabiner, L. R., & Juang, B.-H. F. (1993) · Cited by 7,680
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
(1994) · Knowledge Discovery and Data Mining · Cited by 3,137
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
Self-citationFast 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
Minimum prediction residual principle applied to speech recognition
Itakura, F. (1975) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1975.1162641 · Cited by 1,627
Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases
Keogh, E., Chakrabarti, K., Pazzani, M., & Mehrotra, S. (2001) · Knowledge and Information Systems · doi:10.1007/pl00011669 · Cited by 1,573
Self-citationDiscovering similar multidimensional trajectories
Vlachos, M., Kollios, G., & Gunopulos, D. (2003) · Proceedings 18th International Conference on Data Engineering · doi:10.1109/icde.2002.994784 · Cited by 1,468
Efficient time series matching by wavelets
Chan, K.-P., & Fu, A. W.-C. (1999) · Proceedings 15th International Conference on Data Engineering (Cat. No.99CB36337) · doi:10.1109/icde.1999.754915 · Cited by 1,031
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
Self-citationScaling 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
Self-citationFast Time Sequence Indexing for Arbitrary Lp Norms
Yi, B.-K., & Faloutsos, C. (2018) · doi:10.1184/r1/6605618 · Cited by 650
Rule discovery from time series
Das, G., Lin, K.-I., Mannila, H., Renganathan, G., & Smyth, P. (1998) · Cited by 637
Exact indexing of dynamic time warping
Keogh, E. (2002) · Cited by 594
Self-citationWord image matching using dynamic time warping
Rath, T. M., & Manmatha, R. (2003) · 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings. · doi:10.1109/cvpr.2003.1211511 · Cited by 574
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
Self-citationPerformance tradeoffs in dynamic time warping algorithms for isolated word recognition
Myers, C., Rabiner, L., & Rosenberg, A. (1980) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1980.1163491 · Cited by 568
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
Self-citationAligning gene expression time series with time warping algorithms
Aach, J., & Church, G. M. (2001) · Bioinformatics · doi:10.1093/bioinformatics/17.6.495 · Cited by 496
On the need for time series data mining benchmarks: a survey and empirical demonstration
Keogh, E., & Kasetty, S. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775062 · Cited by 442
Self-citationEfficiently supporting ad hoc queries in large datasets of time sequences
Korn, F., Jagadish, H. V., & Faloutsos, C. (1997) · Proceedings of the 1997 ACM SIGMOD international conference on Management of data - SIGMOD '97 · doi:10.1145/253260.253332 · Cited by 405
Considerations in dynamic time warping algorithms for discrete word recognition
Rabiner, L., Rosenberg, A., & Levinson, S. (1978) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1978.1163164 · Cited by 369
A fingerprint verification system based on triangular matching and dynamic time warping
Kovacs-Vajna, Z. M. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.888711 · Cited by 323
Iterative Deepening Dynamic Time Warping for Time Series
Chu, S., Keogh, E., Hart, D., & Pazzani, M. (2002) · Proceedings of the 2002 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972726.12 · Cited by 268
Self-citationHaar wavelets for efficient similarity search of time-series: with and without time warping
Chan, F. K., Fu, A. W.-C., & Yu, C. (2003) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2003.1198399 · Cited by 261
A new approach to analyzing gene expression time series data
Bar-Joseph, Z., Gerber, G., Gifford, D. K., Jaakkola, T. S., & Simon, I. (2002) · Proceedings of the sixth annual international conference on Computational biology · doi:10.1145/565196.565202 · Cited by 199
Munich, M. E., & Perona, P. (1999) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.1999.791205 · Cited by 167
Efficiently supporting ad hoc queries in large datasets of time sequences
Korn, F. R., Jagadish, H. V., & Faloutsos, C. (1997) · ACM SIGMOD Record · doi:10.1145/253262.253332 · Cited by 151
Learning Comprehensible Descriptions of Multivariate Time Series
Kadous, M. W. (1999) · Cited by 108
Caiani, E. G., Porta, A., Baselli, G., Turiel, M., Muzzupappa, S., Pieruzzi, F., Créma, C., Malliani, A., & Cerutti, S. (2002) · Computers in cardiology · doi:10.1109/cic.1998.731723 · Cited by 84
Performance trade-offs in dynamic time warping algorithms for isolated word recognition
Myers, C. S., Rabiner, L. R., & Rosenberg, A. E. (1979) · The Journal of the Acoustical Society of America · doi:10.1121/1.2017729 · Cited by 60
Indexing of Handwritten Historical Documents - Recent Progress
Manmatha, R., & Rath, T. M. (2003) · ScholarWorks@UMassAmherst (University of Massachusetts Amherst) · Cited by 51
Learned models for continuous planning.
Schmill, M. D., Oates, T., & Cohen, P. R. (1999) · Cited by 46
Cited by
Toward accurate dynamic time warping in linear time and space
Salvador, S., & Chan, P. (2007) · Intelligent Data Analysis · doi:10.3233/ida-2007-11508 · Cited by 1,705
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
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
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
Metadata
- Authors
- Ratanamahatana, C. A., & Keogh, E.
- Venue
- Proceedings of the 2004 SIAM International Conference on Data Mining
- Published
- 2004-04-22
- Pages
- 11-22
- OpenAlex
- W58346954
- Cited by
- 407
- References
- 35
- FWCI
- 14.15
- 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.