Efficient search of the best warping window for Dynamic time Warping

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

11 Citations (Scopus)

Abstract

Time series classification maps time series to labels. The nearest neighbor algorithm (NN) using the Dynamic Time Warping (DTW) similarity measure is a leading algorithm for this task and a component of the current best ensemble classifiers for time series. However, NN-DTW is only a winning combination when its meta-parameter -its warping window -is learned from the training data. The warping window (WW) intuitively controls the amount of distortion allowed when comparing a pair of time series. With a training database of N time series of lengths L, a naive approach to learning theWWrequires Θ(N2 · L3) operations. This often results in NN-DTW requiring days for training on datasets containing a few thousand time series only. In this paper, we introduce FastWWSearch: an efficient and exact method to learn WW. We show on 86 datasets that our method is always faster than the state of the art, with at least one order of magnitude and up to 1000x speed-up.

Original languageEnglish
Title of host publication2018 SIAM International Conference on Data Mining, SDM 2018
Subtitle of host publicationSan Diego Marriott Mission Valley San Diego, California USA May 3-5, 2018
EditorsMartin Ester, Dino Pedreschi
Place of PublicationPhiladelphia PA USA
PublisherSociety for Industrial & Applied Mathematics (SIAM)
Pages225-233
Number of pages9
ISBN (Electronic)9781611975321
Publication statusPublished - 2018
EventSIAM International Conference on Data Mining 2018 - San Diego Marriott Mission Valley, San Diego, United States of America
Duration: 3 May 20185 May 2018
https://epubs.siam.org/doi/10.1137/1.9781611975321.fm

Conference

ConferenceSIAM International Conference on Data Mining 2018
Abbreviated titleSDM 18
CountryUnited States of America
CitySan Diego
Period3/05/185/05/18
Internet address

Cite this

Tan, C. W., Herrmann, M., Forestier, G., Webb, G. I., & Petitjean, F. (2018). Efficient search of the best warping window for Dynamic time Warping. In M. Ester, & D. Pedreschi (Eds.), 2018 SIAM International Conference on Data Mining, SDM 2018: San Diego Marriott Mission Valley San Diego, California USA May 3-5, 2018 (pp. 225-233). Philadelphia PA USA: Society for Industrial & Applied Mathematics (SIAM).
Tan, Chang Wei ; Herrmann, Matthieu ; Forestier, Germain ; Webb, Geoffrey I. ; Petitjean, François. / Efficient search of the best warping window for Dynamic time Warping. 2018 SIAM International Conference on Data Mining, SDM 2018: San Diego Marriott Mission Valley San Diego, California USA May 3-5, 2018. editor / Martin Ester ; Dino Pedreschi. Philadelphia PA USA : Society for Industrial & Applied Mathematics (SIAM), 2018. pp. 225-233
@inproceedings{1fc879a44c4b459189848b5821814d34,
title = "Efficient search of the best warping window for Dynamic time Warping",
abstract = "Time series classification maps time series to labels. The nearest neighbor algorithm (NN) using the Dynamic Time Warping (DTW) similarity measure is a leading algorithm for this task and a component of the current best ensemble classifiers for time series. However, NN-DTW is only a winning combination when its meta-parameter -its warping window -is learned from the training data. The warping window (WW) intuitively controls the amount of distortion allowed when comparing a pair of time series. With a training database of N time series of lengths L, a naive approach to learning theWWrequires Θ(N2 · L3) operations. This often results in NN-DTW requiring days for training on datasets containing a few thousand time series only. In this paper, we introduce FastWWSearch: an efficient and exact method to learn WW. We show on 86 datasets that our method is always faster than the state of the art, with at least one order of magnitude and up to 1000x speed-up.",
author = "Tan, {Chang Wei} and Matthieu Herrmann and Germain Forestier and Webb, {Geoffrey I.} and Fran{\cc}ois Petitjean",
year = "2018",
language = "English",
pages = "225--233",
editor = "Ester, {Martin } and Pedreschi, {Dino }",
booktitle = "2018 SIAM International Conference on Data Mining, SDM 2018",
publisher = "Society for Industrial & Applied Mathematics (SIAM)",

}

Tan, CW, Herrmann, M, Forestier, G, Webb, GI & Petitjean, F 2018, Efficient search of the best warping window for Dynamic time Warping. in M Ester & D Pedreschi (eds), 2018 SIAM International Conference on Data Mining, SDM 2018: San Diego Marriott Mission Valley San Diego, California USA May 3-5, 2018. Society for Industrial & Applied Mathematics (SIAM), Philadelphia PA USA, pp. 225-233, SIAM International Conference on Data Mining 2018, San Diego, United States of America, 3/05/18.

Efficient search of the best warping window for Dynamic time Warping. / Tan, Chang Wei; Herrmann, Matthieu; Forestier, Germain; Webb, Geoffrey I.; Petitjean, François.

2018 SIAM International Conference on Data Mining, SDM 2018: San Diego Marriott Mission Valley San Diego, California USA May 3-5, 2018. ed. / Martin Ester; Dino Pedreschi. Philadelphia PA USA : Society for Industrial & Applied Mathematics (SIAM), 2018. p. 225-233.

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

TY - GEN

T1 - Efficient search of the best warping window for Dynamic time Warping

AU - Tan, Chang Wei

AU - Herrmann, Matthieu

AU - Forestier, Germain

AU - Webb, Geoffrey I.

AU - Petitjean, François

PY - 2018

Y1 - 2018

N2 - Time series classification maps time series to labels. The nearest neighbor algorithm (NN) using the Dynamic Time Warping (DTW) similarity measure is a leading algorithm for this task and a component of the current best ensemble classifiers for time series. However, NN-DTW is only a winning combination when its meta-parameter -its warping window -is learned from the training data. The warping window (WW) intuitively controls the amount of distortion allowed when comparing a pair of time series. With a training database of N time series of lengths L, a naive approach to learning theWWrequires Θ(N2 · L3) operations. This often results in NN-DTW requiring days for training on datasets containing a few thousand time series only. In this paper, we introduce FastWWSearch: an efficient and exact method to learn WW. We show on 86 datasets that our method is always faster than the state of the art, with at least one order of magnitude and up to 1000x speed-up.

AB - Time series classification maps time series to labels. The nearest neighbor algorithm (NN) using the Dynamic Time Warping (DTW) similarity measure is a leading algorithm for this task and a component of the current best ensemble classifiers for time series. However, NN-DTW is only a winning combination when its meta-parameter -its warping window -is learned from the training data. The warping window (WW) intuitively controls the amount of distortion allowed when comparing a pair of time series. With a training database of N time series of lengths L, a naive approach to learning theWWrequires Θ(N2 · L3) operations. This often results in NN-DTW requiring days for training on datasets containing a few thousand time series only. In this paper, we introduce FastWWSearch: an efficient and exact method to learn WW. We show on 86 datasets that our method is always faster than the state of the art, with at least one order of magnitude and up to 1000x speed-up.

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

M3 - Conference Paper

AN - SCOPUS:85048332835

SP - 225

EP - 233

BT - 2018 SIAM International Conference on Data Mining, SDM 2018

A2 - Ester, Martin

A2 - Pedreschi, Dino

PB - Society for Industrial & Applied Mathematics (SIAM)

CY - Philadelphia PA USA

ER -

Tan CW, Herrmann M, Forestier G, Webb GI, Petitjean F. Efficient search of the best warping window for Dynamic time Warping. In Ester M, Pedreschi D, editors, 2018 SIAM International Conference on Data Mining, SDM 2018: San Diego Marriott Mission Valley San Diego, California USA May 3-5, 2018. Philadelphia PA USA: Society for Industrial & Applied Mathematics (SIAM). 2018. p. 225-233