Matrix Profile I: All Pairs Similarity Joins for Time Series: A Unifying View That Includes Motifs, Discords and Shapelets. Yeh, C. M., Zhu, Y., Ulanova, L., Begum, N., Ding, Y., Dau, H. A., Silva, D. F., Mueen, A., & Keogh, E. In 2016 IEEE 16th International Conference on Data Mining (ICDM), pages 1317–1322, December, 2016. ISSN: 2374-8486doi abstract bibtex The all-pairs-similarity-search (or similarity join) problem has been extensively studied for text and a handful of other datatypes. However, surprisingly little progress has been made on similarity joins for time series subsequences. The lack of progress probably stems from the daunting nature of the problem. For even modest sized datasets the obvious nested-loop algorithm can take months, and the typical speed-up techniques in this domain (i.e., indexing, lower-bounding, triangular-inequality pruning and early abandoning) at best produce one or two orders of magnitude speedup. In this work we introduce a novel scalable algorithm for time series subsequence all-pairs-similarity-search. For exceptionally large datasets, the algorithm can be trivially cast as an anytime algorithm and produce high-quality approximate solutions in reasonable time. The exact similarity join algorithm computes the answer to the time series motif and time series discord problem as a side-effect, and our algorithm incidentally provides the fastest known algorithm for both these extensively-studied problems. We demonstrate the utility of our ideas for two time series data mining problems, including motif discovery and novelty discovery.
@inproceedings{yeh_matrix_2016,
title = {Matrix {Profile} {I}: {All} {Pairs} {Similarity} {Joins} for {Time} {Series}: {A} {Unifying} {View} {That} {Includes} {Motifs}, {Discords} and {Shapelets}},
shorttitle = {Matrix {Profile} {I}},
doi = {10.1109/ICDM.2016.0179},
abstract = {The all-pairs-similarity-search (or similarity join) problem has been extensively studied for text and a handful of other datatypes. However, surprisingly little progress has been made on similarity joins for time series subsequences. The lack of progress probably stems from the daunting nature of the problem. For even modest sized datasets the obvious nested-loop algorithm can take months, and the typical speed-up techniques in this domain (i.e., indexing, lower-bounding, triangular-inequality pruning and early abandoning) at best produce one or two orders of magnitude speedup. In this work we introduce a novel scalable algorithm for time series subsequence all-pairs-similarity-search. For exceptionally large datasets, the algorithm can be trivially cast as an anytime algorithm and produce high-quality approximate solutions in reasonable time. The exact similarity join algorithm computes the answer to the time series motif and time series discord problem as a side-effect, and our algorithm incidentally provides the fastest known algorithm for both these extensively-studied problems. We demonstrate the utility of our ideas for two time series data mining problems, including motif discovery and novelty discovery.},
booktitle = {2016 {IEEE} 16th {International} {Conference} on {Data} {Mining} ({ICDM})},
author = {Yeh, Chin-Chia Michael and Zhu, Yan and Ulanova, Liudmila and Begum, Nurjahan and Ding, Yifei and Dau, Hoang Anh and Silva, Diego Furtado and Mueen, Abdullah and Keogh, Eamonn},
month = dec,
year = {2016},
note = {ISSN: 2374-8486},
keywords = {Approximation algorithms, Clustering algorithms, Data mining, Euclidean distance, Indexes, Motif Discovery, Similarity Joins, Text processing, Time Series, Time series analysis},
pages = {1317--1322},
}
Downloads: 0
{"_id":"MeG8Nx8tA8ZfHJt35","bibbaseid":"yeh-zhu-ulanova-begum-ding-dau-silva-mueen-etal-matrixprofileiallpairssimilarityjoinsfortimeseriesaunifyingviewthatincludesmotifsdiscordsandshapelets-2016","author_short":["Yeh, C. M.","Zhu, Y.","Ulanova, L.","Begum, N.","Ding, Y.","Dau, H. A.","Silva, D. F.","Mueen, A.","Keogh, E."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"Matrix Profile I: All Pairs Similarity Joins for Time Series: A Unifying View That Includes Motifs, Discords and Shapelets","shorttitle":"Matrix Profile I","doi":"10.1109/ICDM.2016.0179","abstract":"The all-pairs-similarity-search (or similarity join) problem has been extensively studied for text and a handful of other datatypes. However, surprisingly little progress has been made on similarity joins for time series subsequences. The lack of progress probably stems from the daunting nature of the problem. For even modest sized datasets the obvious nested-loop algorithm can take months, and the typical speed-up techniques in this domain (i.e., indexing, lower-bounding, triangular-inequality pruning and early abandoning) at best produce one or two orders of magnitude speedup. In this work we introduce a novel scalable algorithm for time series subsequence all-pairs-similarity-search. For exceptionally large datasets, the algorithm can be trivially cast as an anytime algorithm and produce high-quality approximate solutions in reasonable time. The exact similarity join algorithm computes the answer to the time series motif and time series discord problem as a side-effect, and our algorithm incidentally provides the fastest known algorithm for both these extensively-studied problems. We demonstrate the utility of our ideas for two time series data mining problems, including motif discovery and novelty discovery.","booktitle":"2016 IEEE 16th International Conference on Data Mining (ICDM)","author":[{"propositions":[],"lastnames":["Yeh"],"firstnames":["Chin-Chia","Michael"],"suffixes":[]},{"propositions":[],"lastnames":["Zhu"],"firstnames":["Yan"],"suffixes":[]},{"propositions":[],"lastnames":["Ulanova"],"firstnames":["Liudmila"],"suffixes":[]},{"propositions":[],"lastnames":["Begum"],"firstnames":["Nurjahan"],"suffixes":[]},{"propositions":[],"lastnames":["Ding"],"firstnames":["Yifei"],"suffixes":[]},{"propositions":[],"lastnames":["Dau"],"firstnames":["Hoang","Anh"],"suffixes":[]},{"propositions":[],"lastnames":["Silva"],"firstnames":["Diego","Furtado"],"suffixes":[]},{"propositions":[],"lastnames":["Mueen"],"firstnames":["Abdullah"],"suffixes":[]},{"propositions":[],"lastnames":["Keogh"],"firstnames":["Eamonn"],"suffixes":[]}],"month":"December","year":"2016","note":"ISSN: 2374-8486","keywords":"Approximation algorithms, Clustering algorithms, Data mining, Euclidean distance, Indexes, Motif Discovery, Similarity Joins, Text processing, Time Series, Time series analysis","pages":"1317–1322","bibtex":"@inproceedings{yeh_matrix_2016,\n\ttitle = {Matrix {Profile} {I}: {All} {Pairs} {Similarity} {Joins} for {Time} {Series}: {A} {Unifying} {View} {That} {Includes} {Motifs}, {Discords} and {Shapelets}},\n\tshorttitle = {Matrix {Profile} {I}},\n\tdoi = {10.1109/ICDM.2016.0179},\n\tabstract = {The all-pairs-similarity-search (or similarity join) problem has been extensively studied for text and a handful of other datatypes. However, surprisingly little progress has been made on similarity joins for time series subsequences. The lack of progress probably stems from the daunting nature of the problem. For even modest sized datasets the obvious nested-loop algorithm can take months, and the typical speed-up techniques in this domain (i.e., indexing, lower-bounding, triangular-inequality pruning and early abandoning) at best produce one or two orders of magnitude speedup. In this work we introduce a novel scalable algorithm for time series subsequence all-pairs-similarity-search. For exceptionally large datasets, the algorithm can be trivially cast as an anytime algorithm and produce high-quality approximate solutions in reasonable time. The exact similarity join algorithm computes the answer to the time series motif and time series discord problem as a side-effect, and our algorithm incidentally provides the fastest known algorithm for both these extensively-studied problems. We demonstrate the utility of our ideas for two time series data mining problems, including motif discovery and novelty discovery.},\n\tbooktitle = {2016 {IEEE} 16th {International} {Conference} on {Data} {Mining} ({ICDM})},\n\tauthor = {Yeh, Chin-Chia Michael and Zhu, Yan and Ulanova, Liudmila and Begum, Nurjahan and Ding, Yifei and Dau, Hoang Anh and Silva, Diego Furtado and Mueen, Abdullah and Keogh, Eamonn},\n\tmonth = dec,\n\tyear = {2016},\n\tnote = {ISSN: 2374-8486},\n\tkeywords = {Approximation algorithms, Clustering algorithms, Data mining, Euclidean distance, Indexes, Motif Discovery, Similarity Joins, Text processing, Time Series, Time series analysis},\n\tpages = {1317--1322},\n}\n\n\n\n","author_short":["Yeh, C. M.","Zhu, Y.","Ulanova, L.","Begum, N.","Ding, Y.","Dau, H. A.","Silva, D. F.","Mueen, A.","Keogh, E."],"key":"yeh_matrix_2016","id":"yeh_matrix_2016","bibbaseid":"yeh-zhu-ulanova-begum-ding-dau-silva-mueen-etal-matrixprofileiallpairssimilarityjoinsfortimeseriesaunifyingviewthatincludesmotifsdiscordsandshapelets-2016","role":"author","urls":{},"keyword":["Approximation algorithms","Clustering algorithms","Data mining","Euclidean distance","Indexes","Motif Discovery","Similarity Joins","Text processing","Time Series","Time series analysis"],"metadata":{"authorlinks":{}},"html":""},"bibtype":"inproceedings","biburl":"https://bibbase.org/zotero/mh_lenguyen","dataSources":["h3wFt8ekw6vXRPL53","C9AxHAfyh4p5B9fd4","iwKepCrWBps7ojhDx","yBoG2HQouwgAieidJ","qG4exu4XyJLWyPN7m"],"keywords":["approximation algorithms","clustering algorithms","data mining","euclidean distance","indexes","motif discovery","similarity joins","text processing","time series","time series analysis"],"search_terms":["matrix","profile","pairs","similarity","joins","time","series","unifying","view","includes","motifs","discords","shapelets","yeh","zhu","ulanova","begum","ding","dau","silva","mueen","keogh"],"title":"Matrix Profile I: All Pairs Similarity Joins for Time Series: A Unifying View That Includes Motifs, Discords and Shapelets","year":2016}