Locally adaptive dimensionality reduction for indexing large time series databases

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

1,313 citations recorded by the source corpus.

Similarity search in large time series databases has attracted much research interest recently. It is a difficult problem because of the typically high dimensionality of the data.. The most promising solutions involve performing dimensionality reduction on the data, then indexing the reduced data with a multidimensional index structure. Many dimensionality reduction techniques have been proposed, including Singular Value Decomposition (SVD), the Discrete Fourier transform (DFT), and the Discrete Wavelet Transform (DWT). In this work we introduce a new dimensionality reduction technique which we call Adaptive Piecewise Constant Approximation (APCA). While previous techniques (e.g., SVD, DFT and DWT) choose a common representation for all the items in the database that minimizes the global reconstruction error, APCA approximates each time series by a set of constant value segments of varying lengths such that their individual reconstruction errors are minimal. We show how APCA can be indexed using a multidimensional index structure. We propose two distance measures in the indexed space that exploit the high fidelity of APCA for fast searching: a lower bounding Euclidean distance approximation, and a non-lower bounding, but very tight Euclidean distance approximation and show how they can support fast exact searching, and even faster approximate searching on the same index structure. We theoretically and empirically compare APCA to all the other techniques and demonstrate its superiority.

Subfields: Signal Processing

View Paper: https://www.semanticscholar.org/paper/728211a7edfe536299670f34714de1b426d969dc

How researchers see this paper

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

In Signal Processing

Citations in the corpus

k-Shape: Efficient and Accurate Clustering of Time Series (2015, neutral): “est in querying [2, 19, 45, 46, 48, 62, 74, 79], indexing [9, 13, 41, 42, 44, 77], classification [37, 56, 68, 88], clustering [43, 54, 64, 87, 89], and modeling [4, 38, 86] of such data.”
A review on time series data mining (2011, methodology): “An ensemble-index, is proposed by Keogh et al. (2001b) and Vlachos et al. (2006), which ensembles two or more representations for indexing.”
Similarity search over time-series data using wavelets (2002, background): “Later on, the Singular Value Decomposition (SVD) transformwas suggested as a very accurate (high precision), but computationally expensive, alternative [33].”
Automated extraction and parameterization of motions in large data sets (2004, background): “1993] or wavelet [Chan and Fu 1999] transform, the average values in adjacent windows [Keogh et al. 2001], and bounding boxes [Vlachos et al.”
Rotation-invariant similarity in time series using bag-of-patterns representation (2012, background): “As a result, many time series representations and similarity measures have been proposed (Chan and Fu 1999; Faloutsos et al. 1994; Keogh 2002; Keogh and Kasetty 2002; Keogh et al. 2001; Li and Vitanyi 1997; Lin et al. 2007).”
Robust and fast similarity search for moving object trajectories (2005, background): “Most of the earlier proposals on similarity-based time series data retrieval are focused on one-dimensional time series data [1, 24, 23, 20, 40].”
Highly Comparative Feature-Based Time-Series Classification (2014, methodology): “using lower bounds [1], [5], [35], and speedups can be obtained using indexing [36], [37], [38] or time-domain dimensionality reduction [39], the need to calculate many distances between pairs of time series is fundamental to”
k-Shape: Efficient and Accurate Clustering of Time Series (2016, background): “The ubiquity of time series has generated a substantial interest in querying [2, 38, 39, 41, 52, 61, 65], indexing [8, 11, 34, 35, 37, 63], classification [30, 47, 58, 70], clustering [36, 45, 54, 69, 71], and modeling [3, 31, 68] of such data.”
Characteristic-Based Clustering for Time Series Data (2006, background): “• Distance Measures: Euclidean distance, the most commonly used metric (Agrawal et al., 1993; Chan and Fu, 1999; Chu and Wong, 1999; Faloutsos et al., 1994; Keogh et al., 2001; Popivanov and Miller, 2002), is certainly not the only metric available for measuring the similarity between data series.”
Density-Connected Subspace Clustering for High-Dimensional Data (2004, background): “[Fuk90], and other transformations, for example based on wavelets [ KCP01 ] or low frequency Fourier harmonics in conjunction with Parsevals theorem [AFS93].”
Exact indexing of dynamic time warping (2002, methodology): “This is to guard against implementation bias (Hellerstein et al. 1997; Keogh et al. 2001) and to allow and encourage independent replication of our results.”
Making Time-Series Classification More Accurate Using Learned Constraints (2004, background): “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).”
EXPOSURE: Finding Malicious Domains Using Passive DNS Analysis (2011, methodology): “A typical technique to measure the level of similarity of two time series is to calculate the distance between them [23].”
Exposure: A Passive DNS Analysis Service to Detect and Report Malicious Domains (2014, methodology): “A typical technique to measure the level of similarity of two time series is to calculate the distance between them [Keogh et al. 2001].”
Finding surprising patterns in a time series database in linear time and space (2002, background): “Possible features include the mean of the data [17], the slope of the best-fitting line [12] [18], the second wavelet coefficient , the second real Fourier coefficient [8], etc.”
A symbolic representation of time series, with implications for streaming algorithms (2003, methodology): “There are two important advantages to doing this: • Dimensionality Reduction: We can use the well-defined and well-documented dimensionality reduction power of PAA [22, 35], and the reduction is automatically ca rried over to the symbolic representation.”