Elastic bands across the path: a new framework and method to lower bound DTW

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)

Abstract

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-offs 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.

Original languageEnglish
Title of host publicationProceedings of the 2019 SIAM International Conference on Data Mining
EditorsTanya Berger-Wolf, Nitesh Chawla
Place of PublicationPhiladelphia PA USA
PublisherSociety for Industrial & Applied Mathematics (SIAM)
Pages522-530
Number of pages9
ISBN (Electronic)9781611975673
DOIs
Publication statusPublished - 2019
EventSIAM International Conference on Data Mining 2019 - Calgary, Canada
Duration: 2 May 20194 May 2019
Conference number: 19th
https://www.siam.org/Conferences/CM/Conference/sdm19

Conference

ConferenceSIAM International Conference on Data Mining 2019
Abbreviated titleSDM 2019
CountryCanada
CityCalgary
Period2/05/194/05/19
Internet address

Cite this

Tan, C. W., Petitjean, F., & Webb, G. I. (2019). Elastic bands across the path: a new framework and method to lower bound DTW. In T. Berger-Wolf, & N. Chawla (Eds.), Proceedings of the 2019 SIAM International Conference on Data Mining (pp. 522-530). Society for Industrial & Applied Mathematics (SIAM). https://doi.org/10.1137/1.9781611975673.59