Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases. Keogh, E., Chakrabarti, K., Pazzani, M., & Mehrotra, S. Knowledge and Information Systems, 3(3):263–286, August, 2001. ![Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex The problem of similarity search in large time series databases has attracted much attention recently. It is a non-trivial problem because of the inherent high dimensionality of the data. The most promising solutions involve first performing dimensionality reduction on the data, and then indexing the reduced data with a spatial access method. Three major dimensionality reduction techniques have been proposed: Singular Value Decomposition (SVD), the Discrete Fourier transform (DFT), and more recently the Discrete Wavelet Transform (DWT). In this work we introduce a new dimensionality reduction technique which we call Piecewise Aggregate Approximation (PAA). We theoretically and empirically compare it to the other techniques and demonstrate its superiority. In addition to being competitive with or faster than the other methods, our approach has numerous other advantages. It is simple to understand and to implement, it allows more flexible distance measures, including weighted Euclidean queries, and the index can be built in linear time.
@article{keogh_dimensionality_2001,
title = {Dimensionality {Reduction} for {Fast} {Similarity} {Search} in {Large} {Time} {Series} {Databases}},
volume = {3},
issn = {0219-1377},
url = {https://doi.org/10.1007/PL00011669},
doi = {10.1007/PL00011669},
abstract = {The problem of similarity search in large time series databases has attracted much attention recently. It is a non-trivial problem because of the inherent high dimensionality of the data. The most promising solutions involve first performing dimensionality reduction on the data, and then indexing the reduced data with a spatial access method. Three major dimensionality reduction techniques have been proposed: Singular Value Decomposition (SVD), the Discrete Fourier transform (DFT), and more recently the Discrete Wavelet Transform (DWT). In this work we introduce a new dimensionality reduction technique which we call Piecewise Aggregate Approximation (PAA). We theoretically and empirically compare it to the other techniques and demonstrate its superiority. In addition to being competitive with or faster than the other methods, our approach has numerous other advantages. It is simple to understand and to implement, it allows more flexible distance measures, including weighted Euclidean queries, and the index can be built in linear time.},
language = {en},
number = {3},
urldate = {2022-09-02},
journal = {Knowledge and Information Systems},
author = {Keogh, Eamonn and Chakrabarti, Kaushik and Pazzani, Michael and Mehrotra, Sharad},
month = aug,
year = {2001},
keywords = {Keywords: Data mining; Dimensionality reduction; Indexing and retrieval; Time series},
pages = {263--286},
}
Downloads: 0
{"_id":"ZCCu2mikFwNi4w3Ys","bibbaseid":"keogh-chakrabarti-pazzani-mehrotra-dimensionalityreductionforfastsimilaritysearchinlargetimeseriesdatabases-2001","author_short":["Keogh, E.","Chakrabarti, K.","Pazzani, M.","Mehrotra, S."],"bibdata":{"bibtype":"article","type":"article","title":"Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases","volume":"3","issn":"0219-1377","url":"https://doi.org/10.1007/PL00011669","doi":"10.1007/PL00011669","abstract":"The problem of similarity search in large time series databases has attracted much attention recently. It is a non-trivial problem because of the inherent high dimensionality of the data. The most promising solutions involve first performing dimensionality reduction on the data, and then indexing the reduced data with a spatial access method. Three major dimensionality reduction techniques have been proposed: Singular Value Decomposition (SVD), the Discrete Fourier transform (DFT), and more recently the Discrete Wavelet Transform (DWT). In this work we introduce a new dimensionality reduction technique which we call Piecewise Aggregate Approximation (PAA). We theoretically and empirically compare it to the other techniques and demonstrate its superiority. In addition to being competitive with or faster than the other methods, our approach has numerous other advantages. It is simple to understand and to implement, it allows more flexible distance measures, including weighted Euclidean queries, and the index can be built in linear time.","language":"en","number":"3","urldate":"2022-09-02","journal":"Knowledge and Information Systems","author":[{"propositions":[],"lastnames":["Keogh"],"firstnames":["Eamonn"],"suffixes":[]},{"propositions":[],"lastnames":["Chakrabarti"],"firstnames":["Kaushik"],"suffixes":[]},{"propositions":[],"lastnames":["Pazzani"],"firstnames":["Michael"],"suffixes":[]},{"propositions":[],"lastnames":["Mehrotra"],"firstnames":["Sharad"],"suffixes":[]}],"month":"August","year":"2001","keywords":"Keywords: Data mining; Dimensionality reduction; Indexing and retrieval; Time series","pages":"263–286","bibtex":"@article{keogh_dimensionality_2001,\n\ttitle = {Dimensionality {Reduction} for {Fast} {Similarity} {Search} in {Large} {Time} {Series} {Databases}},\n\tvolume = {3},\n\tissn = {0219-1377},\n\turl = {https://doi.org/10.1007/PL00011669},\n\tdoi = {10.1007/PL00011669},\n\tabstract = {The problem of similarity search in large time series databases has attracted much attention recently. It is a non-trivial problem because of the inherent high dimensionality of the data. The most promising solutions involve first performing dimensionality reduction on the data, and then indexing the reduced data with a spatial access method. Three major dimensionality reduction techniques have been proposed: Singular Value Decomposition (SVD), the Discrete Fourier transform (DFT), and more recently the Discrete Wavelet Transform (DWT). In this work we introduce a new dimensionality reduction technique which we call Piecewise Aggregate Approximation (PAA). We theoretically and empirically compare it to the other techniques and demonstrate its superiority. In addition to being competitive with or faster than the other methods, our approach has numerous other advantages. It is simple to understand and to implement, it allows more flexible distance measures, including weighted Euclidean queries, and the index can be built in linear time.},\n\tlanguage = {en},\n\tnumber = {3},\n\turldate = {2022-09-02},\n\tjournal = {Knowledge and Information Systems},\n\tauthor = {Keogh, Eamonn and Chakrabarti, Kaushik and Pazzani, Michael and Mehrotra, Sharad},\n\tmonth = aug,\n\tyear = {2001},\n\tkeywords = {Keywords: Data mining; Dimensionality reduction; Indexing and retrieval; Time series},\n\tpages = {263--286},\n}\n\n","author_short":["Keogh, E.","Chakrabarti, K.","Pazzani, M.","Mehrotra, S."],"key":"keogh_dimensionality_2001","id":"keogh_dimensionality_2001","bibbaseid":"keogh-chakrabarti-pazzani-mehrotra-dimensionalityreductionforfastsimilaritysearchinlargetimeseriesdatabases-2001","role":"author","urls":{"Paper":"https://doi.org/10.1007/PL00011669"},"keyword":["Keywords: Data mining; Dimensionality reduction; Indexing and retrieval; Time series"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://bibbase.org/zotero/mh_lenguyen","dataSources":["iwKepCrWBps7ojhDx"],"keywords":["keywords: data mining; dimensionality reduction; indexing and retrieval; time series"],"search_terms":["dimensionality","reduction","fast","similarity","search","large","time","series","databases","keogh","chakrabarti","pazzani","mehrotra"],"title":"Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases","year":2001}