Efficient search of the best warping window for Dynamic time Warping

Chang Wei Tan, Matthieu Herrmann, Germain Forestier, Geoffrey I. Webb, François Petitjean

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

27 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
Country/TerritoryUnited States of America
CitySan Diego
Period3/05/185/05/18
Internet address

Cite this