Using Adaptive Downsampling to Compare Time Series with Warping

Dynamic time warping (DTW) is widely used in many practical domains to compare time series with warping (i.e., signals where similar activity may not be perfectly aligned by sample number). In this paper, we explore different ways to improve upon the efficiency and accuracy of the basic DTW algorithm. Central to our work is the concept of adaptive down sampling using trace segmentation. We describe how the size of the data being compared can be reduced substantially with limited loss of information by down sampling slowly changing parts of the signals much more than rapidly changing regions. We propose two novel measures based on the notion of adaptive down sampling: trace profile comparison (TPC), which compares the reduced representations obtained by adaptive down sampling using a weighting scheme that assesses the relative importance of changes in amplitude and timing, and piecewise linear DTW (PLDTW), which compares piecewise linear segments of the reduced signals using a modified dynamic programming algorithm and cost function. When evaluated on the UCR Time Series dataset, TPC provided an improvement in runtime over the basic DTW algorithm and recent optimizations to it, while PLDTW improved the accuracy of DTW for classification in different datasets.