The DOI matches its Crossref record; 77 of the 77 references it cites were found in a registry or an index.
k-Shape: Efficient and Accurate Clustering of Time Series
Abstract
The proliferation and ubiquity of temporal data across many disciplines has generated substantial interest in the analysis and mining of time series. Clustering is one of the most popular data mining methods, not only due to its exploratory power, but also as a preprocessing step or subroutine for other techniques. In this paper, we present k-Shape, a novel algorithm for time-series clustering. k-Shape relies on a scalable iterative refinement procedure, which creates homogeneous and well-separated clusters. As its distance measure, k-Shape uses a normalized version of the cross-correlation measure in order to consider the shapes of time series while comparing them. Based on the properties of that distance measure, we develop a method to compute cluster centroids, which are used in every iteration to update the assignment of time series to clusters. To demonstrate the robustness of k-Shape, we perform an extensive experimental evaluation of our approach against partitional, hierarchical, and spectral clustering methods, with combinations of the most competitive distance measures. k-Shape outperforms all scalable approaches in terms of accuracy. Furthermore, k-Shape also outperforms all non-scalable (and hence impractical) combinations, with one exception that achieves similar accuracy results. However, unlike k-Shape, this combination requires tuning of its distance measure and is two orders of magnitude slower than k-Shape. Overall, k-Shape emerges as a domain-independent, highly accurate, and highly efficient clustering approach for time series with broad applications.
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
Data mining: concepts and techniques
(2012) · Choice Reviews Online · doi:10.5860/choice.49-3305 · Cited by 28,531
(1967) · Cited by 23,719
Individual Comparisons by Ranking Methods
Wilcoxon, F. (1945) · Biometrics Bulletin · doi:10.2307/3001968 · Cited by 15,354
An algorithm for the machine calculation of complex Fourier series
Cooley, J. W., & Tukey, J. W. (1965) · Mathematics of Computation · doi:10.1090/s0025-5718-1965-0178586-1 · Cited by 13,154
Finding groups in data: an introduction to cluster analysis
(1991) · Choice Reviews Online · doi:10.5860/choice.28-4558 · Cited by 10,474
On Spectral Clustering: Analysis and an algorithm
Ng, A. Y., Jordan, M. I., & Weiss, Y. (2001) · Cited by 8,159
The use of ranks to avoid the assumption of normality implicit in the analysis of variance
Friedman, M. (1937) · Journal of the American Statistical Association · doi:10.1080/01621459.1937.10503522 · Cited by 7,005
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
Objective Criteria for the Evaluation of Clustering Methods
Rand, W. M. (1971) · Journal of the American Statistical Association · doi:10.1080/01621459.1971.10482356 · Cited by 6,566
The Design and Implementation of FFTW3
Frigo, M., & Johnson, S. G. (2005) · Proceedings of the IEEE · doi:10.1109/jproc.2004.840301 · Cited by 5,086 · cited 1×
“Moreover, recursive algorithms compute an FFT by dividing it into pieces of power-of-two size [24].”
Method(1994) · Knowledge Discovery and Data Mining · Cited by 3,137
On Clustering Validation Techniques
Halkidi, M., Batistakis, Y., & Vazirgiannis, M. (2001) · Journal of Intelligent Information Systems · doi:10.1023/a:1012801612483 · Cited by 2,646
Clustering of time series data—a survey
Warren Liao, T. (2005) · Pattern Recognition · doi:10.1016/j.patcog.2005.01.025 · Cited by 2,401
Hierarchical structure in financial markets
Mantegna, R. N. (1999) · The European Physical Journal B · doi:10.1007/s100510050929 · Cited by 2,069
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
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
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
An Introduction to Harmonic Analysis.
Weiss, G., & Katznelson, Y. (1970) · The American Mathematical Monthly · doi:10.2307/2316172 · Cited by 1,664
Discovering 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
An Introduction to Harmonic Analysis
Katznelson, Y. (2004) · Cambridge University Press eBooks · doi:10.1017/cbo9781139165372 · Cited by 1,366
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
A global averaging method for dynamic time warping, with applications to clustering
Petitjean, F., Ketterlin, A., & Gançarski, P. (2011) · Pattern Recognition · doi:10.1016/j.patcog.2010.09.013 · Cited by 1,138
Statistical Comparisons of Classifiers over Multiple Data Sets
DemšarJanez (2006) · Journal of Machine Learning Research · doi:10.5555/1248547.1248548 · Cited by 1,074
Searching and mining trillions of time series subsequences under dynamic time warping
Rakthanmanon, T., Campana, B., Mueen, A., Batista, G., Westover, B., Zhu, Q., Zakaria, J., & Keogh, E. (2012) · Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2339530.2339576 · Cited by 1,047
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
Time series shapelets: a new primitive for data mining
Ye, L., & Keogh, E. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557122 · Cited by 987
Patterns of temporal variation in online media
Yang, J., & Leskovec, J. (2011) · Proceedings of the fourth ACM international conference on Web search and data mining · doi:10.1145/1935826.1935863 · Cited by 986
On the Complexity of Multiple Sequence Alignment
WANG, L., & JIANG, T. (1994) · Journal of Computational Biology · doi:10.1089/cmb.1994.1.337 · Cited by 934
NP-hardness of Euclidean sum-of-squares clustering
Aloise, D., Deshpande, A., Hansen, P., & Popat, P. (2009) · Machine Learning · doi:10.1007/s10994-009-5103-0 · Cited by 867
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
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
A survey of kernel and spectral methods for clustering
Filippone, M., Camastra, F., Masulli, F., & Rovetta, S. (2008) · Pattern Recognition · doi:10.1016/j.patcog.2007.05.018 · Cited by 827
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
Characteristic-Based Clustering for Time Series Data
Wang, X., Smith, K., & Hyndman, R. (2006) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-005-0039-x · Cited by 679
Zhu, Y., & Shasha, D. (2002) · VLDB '02: Proceedings of the 28th International Conference on Very Large Databases · doi:10.1016/b978-155860869-6/50039-1 · Cited by 656
Cluster analysis and mathematical programming
Hansen, P., & Jaumard, B. (1997) · Mathematical Programming · doi:10.1007/bf02614317 · Cited by 646
Rule discovery from time series
Das, G., Lin, K.-I., Mannila, H., Renganathan, G., & Smyth, P. (1998) · Cited by 637
On Clustering fMRI Time Series
Goutte, C., Toft, P., Rostrup, E., Nielsen, F. Å., & Hansen, L. K. (1999) · NeuroImage · doi:10.1006/nimg.1998.0391 · Cited by 518
Clustering of time-series subsequences is meaningless: implications for previous and future research
Keogh, E., & Lin, J. (2005) · Knowledge and Information Systems · doi:10.1007/s10115-004-0172-7 · Cited by 464
Distance measures for effective clustering of ARIMA time-series
Kalpakis, K., Gada, D., & Puttagunta, V. (2002) · Proceedings 2001 IEEE International Conference on Data Mining · doi:10.1109/icdm.2001.989529 · Cited by 442
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
Efficiently 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
Finding Groups in Data: An Introduction to Cluster Analysis
Hadi, A. S., Kaufman, L., & Rousseeuw, P. J. (1992) · Technometrics · doi:10.2307/1269576 · Cited by 378
CID: an efficient complexity-invariant distance for time series
Batista, G. E. A. P. A., Keogh, E. J., Tataw, O. M., & de Souza, V. M. A. (2014) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-013-0312-3 · Cited by 359
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
The Planar k-Means Problem is NP-Hard
Mahajan, M., Nimbhorkar, P., & Varadarajan, K. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-00202-1_24 · Cited by 308
Logical-shapelets: an expressive primitive for time series classification
Mueen, A., Keogh, E., & Young, N. (2011) · Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2020408.2020587 · Cited by 282
Correlating financial time series with micro-blogging activity
Ruiz, E. J., Hristidis, V., Castillo, C., Gionis, A., & Jaimes, A. (2012) · Proceedings of the fifth ACM international conference on Web search and data mining · doi:10.1145/2124295.2124358 · Cited by 272
Haar 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 correlation‐based fuzzy logic clustering algorithm for FMRI
Golay, X., Kollias, S., Stoll, G., Meier, D., Valavanis, A., & Boesiger, P. (1998) · Magnetic Resonance in Medicine · doi:10.1002/mrm.1910400211 · Cited by 253
Clustering Time Series Using Unsupervised-Shapelets
Zakaria, J., Mueen, A., & Keogh, E. (2012) · 2012 IEEE 12th International Conference on Data Mining · doi:10.1109/icdm.2012.26 · Cited by 231
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
Index-based Most Similar Trajectory Search
Frentzos, E., Gratsias, K., & Theodoridis, Y. (2007) · Proceedings - International Conference on Data Engineering · doi:10.1109/icde.2007.367927 · Cited by 199
Iterative Incremental Clustering of Time Series
Lin, J., Vlachos, M., Keogh, E., & Gunopulos, D. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24741-8_8 · Cited by 192
The Move-Split-Merge Metric for Time Series
Stefan, A., Athitsos, V., & Das, G. (2013) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2012.88 · Cited by 191
Discovering clusters in motion time-series data
Alon, J., Sclaroff, S., Kollios, G., & Pavlovic, V. (2003) · 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings. · doi:10.1109/cvpr.2003.1211378 · Cited by 185
SpADe: On Shape-based Pattern Detection in Streaming Time Series
Chen, Y., Nascimento, M. A., Ooi, B. C., & Tung, A. K. H. (2007) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2007.367924 · Cited by 181
Mining the stock market (extended abstract): which measure is best?
Gavrilov, M., Anguelov, D., Indyk, P., & Motwani, R. (2000) · Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/347090.347189 · Cited by 180
An efficient and accurate method for evaluating time series similarity
Morse, M. D., & Patel, J. M. (2007) · Proceedings of the 2007 ACM SIGMOD international conference on Management of data · doi:10.1145/1247480.1247544 · Cited by 180
Nonlinear alignment and averaging for estimating the evoked potential
Gupta, L., Molfese, D. L., Tammana, R., & Simos, P. G. (1996) · IEEE Transactions on Biomedical Engineering · doi:10.1109/10.486255 · Cited by 174
BRAID: stream mining through group lag correlations
Sakurai, Y., Papadimitriou, S., & Faloutsos, C. (2005) · Proceedings of the 2005 ACM SIGMOD international conference on Management of data · doi:10.1145/1066157.1066226 · Cited by 166
Indexing Multidimensional Time-Series
Vlachos, M., Hadjieleftheriou, M., Gunopulos, D., & Keogh, E. (2005) · The VLDB Journal · doi:10.1007/s00778-004-0144-2 · Cited by 154
Time Series Classification under More Realistic Assumptions
Hu, B., Chen, Y., & Keogh, E. (2013) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972832.64 · Cited by 151
Mixtures of ARMA models for model-based time series clustering
Xiong, Y., & Yeung, D. (2003) · Proceedings · doi:10.1109/icdm.2002.1184037 · Cited by 138
Time Series Epenthesis: Clustering Time Series Streams Requires Ignoring Some Data
Rakthanmanon, T., Keogh, E., Lonardi, S., & Evans, S. (2011) · Proceedings · doi:10.1109/icdm.2011.146 · Cited by 119
A Multiresolution Symbolic Representation of Time Series
Megalooikonomou, V., Wang, Q., Li, G., & Faloutsos, C. (2005) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2005.10 · Cited by 112
Indexable PLA for efficient similarity search
Chen, Q., Chen, L., Lian, X., Liu, Y., & Yu, J. X. (2007) · Cited by 107
A decade of progress in indexing and mining large time series databases
Keogh, E. (2006) · Very Large Data Bases · doi:10.5555/1182635.1164262 · Cited by 101
Clustering time series from ARMA models with clipped data
Bagnall, A. J., & Janacek, G. J. (2004) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1014052.1014061 · Cited by 101
MALM: a framework for mining sequence database at multiple abstraction levels
Li, C., Yu, P. S., & Castelli, V. (1998) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/288627.288666 · Cited by 86
Summarizing a set of time series by averaging: From Steiner sequence to compact multiple alignment
Petitjean, F., & Gançarski, P. (2011) · Theoretical Computer Science · doi:10.1016/j.tcs.2011.09.029 · Cited by 83
Embedding-based subsequence matching in time-series databases
Papapetrou, P., Athitsos, V., Potamias, M., Kollios, G., & Gunopulos, D. (2011) · ACM Transactions on Database Systems · doi:10.1145/2000824.2000827 · Cited by 76
Shape averaging under Time Warping
Niennattrakul, V., & Ratanamahatana, C. A. (2009) · International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON) · doi:10.1109/ecticon.2009.5137128 · Cited by 69
An Empirical Comparison of Dissimilarity Measures for Time Series Classification
Giusti, R., & Batista, G. E. A. P. A. (2013) · Brazilian Conference on Intelligent Systems · doi:10.1109/bracis.2013.22 · Cited by 66
Detecting Leaders from Correlated Time Series
Wu, D., Ke, Y., Yu, J. X., Yu, P. S., & Chen, L. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-12026-8_28 · Cited by 37
Clustering of time-series subsequences is meaningless
KeoghEamonn, & LinJessica (2005) · Knowledge and Information Systems · doi:10.5555/2993947.2993982 · Cited by 35
Cited by
Dau, H. A., Bagnall, A., Kamgar, K., Yeh, C.-C. M., Zhu, Y., Gharghabi, S., Ratanamahatana, C. A., & Keogh, E. (2019) · IEEE/CAA Journal of Automatica Sinica · doi:10.1109/jas.2019.1911747 · Cited by 1,128
Unsupervised Machine Learning for Networking: Techniques, Applications and Research Challenges
Usama, M., Qadir, J., Raza, A., Arif, H., Yau, K.-L. A., Elkhatib, Y., Hussain, A., & Al-Fuqaha, A. (2019) · IEEE Access · doi:10.1109/access.2019.2916648 · Cited by 575
Machine Learning for Network Automation: Overview, Architecture, and Applications [Invited Tutorial]
Rafique, D., & Velasco, L. (2018) · Journal of Optical Communications and Networking · doi:10.1364/jocn.10.00d126 · Cited by 298
Teichgraeber, H., & Brandt, A. R. (2019) · Applied Energy · doi:10.1016/j.apenergy.2019.02.012 · Cited by 257
Sheng, C., Mendler, I.-H., Rieke, S., Snyder, P., Jentsch, M., Friedrich, D., Drossel, B., & Loewer, A. (2019) · Cell Reports · doi:10.1016/j.celrep.2019.03.031 · Cited by 45
“SBD tolerates both amplitude and time variances, allowing pairwise comparisons of single-cell trajectories.”
MethodInfluential
Metadata
- Authors
- Paparrizos, J., & Gravano, L.
- Venue
- Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data
- Publisher
- ACM
- Published
- 2015-05-27
- Pages
- 1855-1870
- ISSN
- 0730-8078 (ISSN-L)
- OpenAlex
- W2037537012
- Cited by
- 680
- References
- 77
- FWCI
- 22.74
- 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.