Elastic bands across the path: A new framework and method to lower bound DTW
Chang Wei Tan, François Petitjean, Geoffrey I. Webb · Society for Industrial and Applied Mathematics eBooks · 2019
The Nearest Neighbour algorithm coupled with the Dynamic Time Warping similarity measure (NN-DTW) is at the core of state-of-the-art classification algorithms including Ensemble of Elastic Distances and Collection of Transformation-Based Ensemble. DTW's complexity makes NN-DTW highly computationally demanding. To combat this, lower bounds to DTW are used to minimize the number of times the expensive DTW need be computed during NN-DTW search. Effective lower bounds must balance ‘time to calculate’ vs ‘tightness to DTW.‘ On the one hand, the tighter the bound the fewer the calls to the full DTW. On the other, calculating tighter bounds usually requires greater computation. Numerous lower bounds have been proposed. Different bounds provide different trade-off between computational time and tightness. In this work, we present a new class of lower bounds that are tighter than the popular Keogh lower bound, while requiring similar computation time. Our new lower bounds take advantage of the DTW boundary condition, monotonicity and continuity constraints. In contrast to most existing bounds, they remain relatively tight even for large windows. A single parameter to these new lower bounds controls the speed-tightness trade-off. We demonstrate that these new lower bounds provide an exceptional balance between computation time and tightness for the NN-DTW time series classification task, resulting in greatly improved efficiency for NN-DTW lower bound search.