AWarp: Fast Warping Distance for Sparse Time Series
- 1 December 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 11, 350-359
Abstract
Dynamic Time Warping (DTW) distance has been effectively used in mining time series data in a multitude of domains. However, in its original formulation DTW is extremely inefficient in comparing long sparse time series, containing mostly zeros and some unevenly spaced non-zero observations. Original DTW distance does not take advantage of this sparsity, leading to redundant calculations and a prohibitively large computational cost for long time series. We derive a new time warping similarity measure (AWarp) for sparse time series that works on the run-length encoded representation of sparse time series. The complexity of AWarp is quadratic on the number of observations as opposed to the range of time of the time series. Therefore, AWarp can be several orders of magnitude faster than DTW on sparse time series. AWarp is exact for binary-valued time series and a close approximation of the original DTW distance for any-valued series. We discuss useful variants of AWarp: bounded (both upper and lower), constrained, and multidimensional. We show applications of AWarp to three data mining tasks including clustering, classification, and outlier detection, which are otherwise not feasible using classic DTW, while producing equivalent results. Potential areas of application include bot detection, human activity classification, and unusual review pattern mining.Keywords
This publication has 18 references indexed in Scilit:
- Accelerating Dynamic Time Warping Clustering with a Novel Admissible Pruning Strategy2015
- Dynamic time warping and sparse representation classification for birdsong phrase classification using limited training dataThe Journal of the Acoustical Society of America, 2015
- Searching and mining trillions of time series subsequences under dynamic time warping2012
- sDTWProceedings of the VLDB Endowment, 2012
- Experimental comparison of representation methods and distance measures for time series dataData Mining and Knowledge Discovery, 2012
- Anticipatory DTW for efficient similarity search in time series databasesProceedings of the VLDB Endowment, 2009
- Gait recognition using dynamic time warping2005
- Scaling up dynamic time warping for datamining applications2000
- Fast subsequence matching in time-series databasesACM SIGMOD Record, 1994
- Dynamic programming algorithm optimization for spoken word recognitionIEEE Transactions on Acoustics, Speech, and Signal Processing, 1978