Scaling up dynamic time warping for datamining applications

By Eamonn J. Keogh, Michael J. Pazzani. 2000

936 citations recorded by the source corpus.

There has been much recent interest in adapting data mining algorithms to time series databases. Most of these algorithms need to compare time series. Typically some variation of Euclidean distance is used. However, as we demonstrate in this paper, Euclidean distance can be an extremely brittle distance measure. Dynamic time warping (DTW) has been suggested as a technique to allow more robust distance calculations, however it is computationally expensive. In this paper we introduce a modification of DTW which operates on a higher level abstraction of the data, in particular, a Piecewise Aggregate Approximation (PAA). Our approach allows us to outperform DTW by one to two orders of magnitude, with no loss of accuracy.

Subfields: Computer Networks and Communications, 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 Computer Networks and Communications

In Signal Processing

Citations in the corpus

Effective and General Evaluation for Instruction Conditioned Navigation using Dynamic Time Warping (2019, background): “DTW is a similarity function for time series that has long been known and used in speech processing [12, 13, 14], robotics [15, 16], data mining [17, 18], handwriting recognition [19], gesture recognition [20, 21] and many other areas [22, 23, 24].”
Intelligent multi-camera video surveillance: A review (2013, background): “Many approaches (Keogh and Pazzani, 2000; Makris and Ellis, 2002; Porikli, 2003; Junejo et al., 2004; Fu et al., 2005; Zhang et al., 2006; Wang et al., 2011) have been proposed to cluster trajectories of objects into different activity categories without supervision.”
Derivative Dynamic Time Warping (2001, background): “In addition to data mining (Keogh & Pazzani 2000, Yi et. al.”
Toward accurate dynamic time warping in linear time and space (2007, neutral): “The Abstraction algorithm used in this evaluation ﬁrst samples the data, and then runs DTW to ﬁnd a warp path on the sampled data similar to the Piecewise Dynamic Time Warping algorithm (PDTW) [13].”
A survey of temporal data mining (2006, methodology): “Recently, Keogh & Pazzani (2000) used a piece-wise aggregate model for time-series to allow faster matching using dynamic time warping.”
Imaging Time-Series to Improve Classification and Imputation (2015, methodology): “(8). the GAFs, we apply Piecewise Aggregation Approximation (PAA) [ Keogh and Pazzani, 2000 ] to smooth the time series while preserving the trends.”
Exact indexing of dynamic time warping (2002, background): “However, there is an increasing awareness that the Euclidean distance is a very brittle distance measure (Aach and Church 2001; Bar-Joseph et al. 2002; Berndt and Clifford 1994; Chu et al. 2002; Diez and Gonzalez 2000; Kadous 1999; Keogh and Pazzani 2000; Kollios et al. 2002; Schmill et al. 1999; Yi”
A review on time series data mining (2011, background): “Keogh and Pazzani (2000b) introduce a modification of DTW, which integrates with PAA and operates on a higher level abstraction of the time series.”
Robust and fast similarity search for moving object trajectories (2005, background): “The two labelled trajectory data sets are the “Cameramouse” (CM) [11] and the Australian Sign Language (ASL) data sets which were also used in [22, 36].”
Encoding Time Series as Images for Visual Inspection and Classification Using Tiled Convolutional Neural Networks (2014, methodology): “To reduce the size of the GAF, we apply Piecewise Aggregation Approximation (Keogh and Pazzani 2000) to smooth the time series and while keeping trends.”
Hierarchical Aligned Cluster Analysis for Temporal Clustering of Human Motion (2013, methodology): “Previous work by Keogh and Pazzani [54] used this strategy to speed up the computation of DTW. Unlike [54], we used the values from the lower level to compute the similarity in a bottom-up way.”
FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space (2004, methodology): “Data abstraction speeds up the DTW algorithm by run ning DTW on a reduced representation of the data [2][9].”
A brief survey on sequence classification (2010, background): “Dynamic time warping distance (DTW) [28] is proposed to overcome this problem and does not require two time series to be of the same length.”