Ultra-fast meta-parameter optimization for time series similarity measures with application to nearest neighbour classification
Open Access
- 13 January 2023
- journal article
- research article
- Published by Springer Nature in Knowledge and Information Systems
- Vol. 65 (5) , 2123-2157
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(L^2)$$ 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.
Keywords
Funding Information
- Australian Research Council (DP210100072)
This publication has 40 references indexed in Scilit:
- Weighted dynamic time warping for time series classificationPattern Recognition, 2011
- A global averaging method for dynamic time warping, with applications to clusteringPattern Recognition, 2011
- Classification of Pulse Waveforms Using Edit Distance with Real PenaltyEURASIP Journal on Advances in Signal Processing, 2010
- Faster retrieval with a two-pass dynamic-time-warping lower boundPattern Recognition, 2009
- Exact indexing of dynamic time warpingKnowledge and Information Systems, 2005
- Making Time-series Classification More Accurate Using Learned Constraints2004
- On The Marriage of Lp-norms and Edit Distance2004
- Derivative Dynamic Time Warping2001
- Comparison of video shot boundary detection techniquesJournal of Electronic Imaging, 1996
- Minimum prediction residual principle applied to speech recognitionIEEE Transactions on Acoustics, Speech, and Signal Processing, 1975