Ultra-fast meta-parameter optimization for time series similarity measures with application to nearest neighbour classification

Chang Wei Tan, Matthieu Herrmann, Geoffrey I. Webb

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Nearest neighbour similarity measures are widely used in many time series data analysis applications. They compute a measure of similarity between two time series. Most applications require tuning of these measures’ meta-parameters in order to achieve good performance. However, most measures have at least O(L2) complexity, making them computationally expensive and the process of learning their meta-parameters burdensome, requiring days even for datasets containing only a few thousand series. In this paper, we propose UltraFastMPSearch, a family of algorithms to learn the meta-parameters for different types of time series distance measures. These algorithms are significantly faster than the prior state of the art. Our algorithms build upon the state of the art, exploiting the properties of a new efficient exact algorithm which supports early abandoning and pruning for most time series distance measures. We show on 128 datasets from the UCR archive that our new family of algorithms are up to an order of magnitude faster than the previous state of the art.

Original languageEnglish
Pages (from-to)2123-2157
Number of pages35
JournalKnowledge and Information Systems
Volume65
Issue number5
DOIs
Publication statusPublished - May 2023

Keywords

  • Early abandoning
  • Pruning
  • Similarity measures
  • Time series

Cite this