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

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

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). Philadelphia PA USA: Society for Industrial & Applied Mathematics (SIAM). https://doi.org/10.1137/1.9781611975673.59
Tan, Chang Wei ; Petitjean, François ; Webb, Geoffrey I. / Elastic bands across the path : a new framework and method to lower bound DTW. Proceedings of the 2019 SIAM International Conference on Data Mining. editor / Tanya Berger-Wolf ; Nitesh Chawla. Philadelphia PA USA : Society for Industrial & Applied Mathematics (SIAM), 2019. pp. 522-530
@inproceedings{ced42a5b491147fd879803856ab964ba,
title = "Elastic bands across the path: a new framework and method to lower bound DTW",
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.",
author = "Tan, {Chang Wei} and Fran{\cc}ois Petitjean and Webb, {Geoffrey I.}",
year = "2019",
doi = "10.1137/1.9781611975673.59",
language = "English",
pages = "522--530",
editor = "Tanya Berger-Wolf and Nitesh Chawla",
booktitle = "Proceedings of the 2019 SIAM International Conference on Data Mining",
publisher = "Society for Industrial & Applied Mathematics (SIAM)",

}

Tan, CW, Petitjean, F & Webb, GI 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. Society for Industrial & Applied Mathematics (SIAM), Philadelphia PA USA, pp. 522-530, SIAM International Conference on Data Mining 2019, Calgary, Canada, 2/05/19. https://doi.org/10.1137/1.9781611975673.59

Elastic bands across the path : a new framework and method to lower bound DTW. / Tan, Chang Wei; Petitjean, François; Webb, Geoffrey I.

Proceedings of the 2019 SIAM International Conference on Data Mining. ed. / Tanya Berger-Wolf; Nitesh Chawla. Philadelphia PA USA : Society for Industrial & Applied Mathematics (SIAM), 2019. p. 522-530.

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

TY - GEN

T1 - Elastic bands across the path

T2 - a new framework and method to lower bound DTW

AU - Tan, Chang Wei

AU - Petitjean, François

AU - Webb, Geoffrey I.

PY - 2019

Y1 - 2019

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

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

UR - http://www.scopus.com/inward/record.url?scp=85066076954&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975673.59

DO - 10.1137/1.9781611975673.59

M3 - Conference Paper

SP - 522

EP - 530

BT - Proceedings of the 2019 SIAM International Conference on Data Mining

A2 - Berger-Wolf, Tanya

A2 - Chawla, Nitesh

PB - Society for Industrial & Applied Mathematics (SIAM)

CY - Philadelphia PA USA

ER -

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