The computation of a distance of two time series is time-consuming for any elastic distance function that accounts for misalignments. Among those functions, DTW is the most prominent. However, a recent extensive evaluation has shown that the move-split merge (MSM) metric is superior to DTW regarding the analytical accuracy of 1-NN classifier. Unfortunately, the runtime of the standard dynamic programming algorithm for MSM distance computation is $\Omega(n^2)$, where $n$ is the length of the longest time series. In this paper, we provide approaches to reducing the cost of MSM distance computations by using lower and upper bounds for early pruning paths in the underlying dynamic programming table. For the case of one time series being a constant, we present a linear-time algorithm. In addition, we propose new linear-time heuristics and adapt heuristics known from DTW to computing the MSM distance. One heuristic employs the metric property of MSM and the previously introduced linear-time algorithm. Our experimental studies achieve substantial speed-ups in our approaches compared to previous MSM algorithms. In particular, the running time for MSM is faster for a majority of data sets than a state-of-the-art DTW distance computation.
翻译:计算两个时间序列的距离对于计算不匹配值的任何弹性距离函数都是费时的。在这些函数中,DTW是最突出的。然而,最近一项广泛的评估表明,移动-分解合并(MSM)衡量标准在1-NN分类员的分析准确性方面优于DTW。不幸的是,MSM距离计算标准动态程序算法的运行时间为$\Omega(n)2美元,其中美元是最长时间序列的长度。在本文中,我们提供一些办法,通过在基本动态程序表中使用上下限来降低MSM的距离计算成本。如果一个时间序列是固定的,我们提出线性算法。此外,我们提议新的线性时间超时算法,并调整已知的从DTW距离算法到计算MSMM的距离。一个超前MSM-M-M-M数据计算法,我们的实验研究在比前MSM-M-M-M-M-M-ML多数计算法更快的计算方法中取得了相当大的速度。