Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases

By Eamonn J. Keogh, Kaushik Chakrabarti, Michael J. Pazzani, Sharad Mehrotra. 2001

1,670 citations recorded by the source corpus.

Subfields: Economics and Econometrics, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Economics and Econometrics

In Signal Processing

Citations in the corpus

A Deep Learning Approach for Optimization of Systematic Signal Detection in Financial Trading Systems with Big Data (2017, background): “The granularity of approximation of PLR can be changed dynamically by setting the number of line segments [28].”
A Survey of Clustering Data Mining Techniques (2006, methodology): “A blend of attribute transformations (DFT, Polynomials) and indexing technique is presented in [Keogh et al. 2001a].”
Plato (2020, positive): “For instance, the Piecewise Aggregate Approximation (PAA) [30] and the Piecewise Linear Representation (PLR) [27] adopt polynomial functions (0-degree in PAA and 1-degree in PLR) to compress the time series; [45] uses Gaussian functions; [55] applies natural logarithmic functions and natural…”
Experiencing SAX: a novel symbolic representation of time series (2007, methodology): “The review below is necessarily brief; we refer interested readers to (Keogh and Kasetty 2002; Roddick et al. 2001) for a more in depth review.”
Querying and mining of time series data: experimental comparison of representations and distance measures (2008, background): “In contrast, in Figure 5 we can see that highly periodic data can slightly favor the spectral representations (DCT, DFT, CHEB) over the polynomial representations (SAX, APCA, DWT/PAA, IPLA).”
Effortless Data Exploration with zenvisage: An Expressive and Interactive Visual Analytics System (2016, methodology): “, [33, 23, 15, 32, 13, 19, 31]; for the attributes that are queried frequently, we plan to reuse these techniques for similarity search.”
Comparisons Between Data Clustering Algorithms (2008, background): “In a sense, labels are associated with clusters also, but these category labels are data driven; that is, they are obtained solely from the data [5, 7, 8, 13].”
Making Time-Series Classification More Accurate Using Learned Constraints (2004, methodology): “During the past decade, there has been a huge amount of work on speeding up data mining time series under the Euclidean distance [7][16][24][45] (see [25] for a comprehensive listing).”
Pattern Matching in Historical Data (2002, methodology): “A number of techniques have been developed for pattern Žmatching in time-series data Faloutsos et al., 1994; Agrawal .et al., 1995; Keogh et al., 2001 , including stock market data Ž .”
Large-Scale Unusual Time Series Detection (2015, methodology): “Baseline 2 Computes similarity between time series using discrete wavelet transform (DWT) [10].”
Similarity search over time-series data using wavelets (2002, methodology): “Later on, the Singular Value Decomposition (SVD) transformwas suggested as a very accurate (high precision), but computationally expensive, alternative [33].”
A Feature Fusion Based Forecasting Model for Financial Time Series (2014, methodology): “Plenty of methods are proposed to remove noise and reduce the dimensions of raw data, such as Principal Component Analysis (PCA) [2], Kernel Principal Component Analysis [3], Perpetually Important Points [4], Piecewise Aggregate Approximation[5], Singular Spectral Analy- sis[6], Discrete Fourier Tra”
A review on time series data mining (2011, methodology): “This method is also called piecewise aggregate approximation (PAA) by Keogh et al. (2000).”
Probabilistic discovery of time series motifs (2003, methodology): “To date the majority of work in time series data mining has focused indexing time series, the efficient discovery of known patterns in time series [1, 6, 12, 21, 22, 23, 31, 35, 36, 37].”
Data Mining for the Internet of Things: Literature Review and Challenges (2015, methodology): “In non-data-adaptive representations, the parameters of the transformation remain the same for every time series regardless of its nature, related research including DFT [86], wavelet functions related topic [87], and PAA [72].”
Finding Motifs in Time Series (2002, methodology): “The triangular inequality requires that [2, 22, 33]: D(Q,Ca) ≤ D(Q,Cb) + D(Ca,Cb) (8) Filling in the known values give us 7 ≤ D(Q,Cb) + 2 (9) Rearranging the terms gives us 5 ≤ D(Q,Cb) (10) But since we are only interested in subsequences that are a distance less than 1 unit away, there is no point ”