Dynamic Time Warping is arguably the most popular similarity measure for time series, where we define a time series to be a one-dimensional polygonal curve. The drawback of Dynamic Time Warping is that it is sensitive to the sampling rate of the time series. The Fr\'echet distance is an alternative that has gained popularity, however, its drawback is that it is sensitive to outliers. Continuous Dynamic Time Warping (CDTW) is a recently proposed alternative that does not exhibit the aforementioned drawbacks. CDTW combines the continuous nature of the Fr\'echet distance with the summation of Dynamic Time Warping, resulting in a similarity measure that is robust to sampling rate and to outliers. In a recent experimental work of Brankovic et al., it was demonstrated that clustering under CDTW avoids the unwanted artifacts that appear when clustering under Dynamic Time Warping and under the Fr\'echet distance. Despite its advantages, the major shortcoming of CDTW is that there is no exact algorithm for computing CDTW, in polynomial time or otherwise. In this work, we present the first exact algorithm for computing CDTW of one-dimensional curves. Our algorithm runs in time $O(n^5)$ for a pair of one-dimensional curves, each with complexity at most $n$. In our algorithm, we propagate continuous functions in the dynamic program for CDTW, where the main difficulty lies in bounding the complexity of the functions. We believe that our result is an important first step towards CDTW becoming a practical similarity measure between curves.
翻译:动态时间扭曲可以说是时间序列中最受欢迎的相似度量, 我们在此将时间序列的复杂度与动态时间扭曲的对比性结合起来。 动态时间扭曲的缺点在于它对于时间序列的抽样率敏感。 Fr\'echet 距离是一个越来越受欢迎的替代方法, 但是, 它的偏差在于它对于外星体是敏感的。 持续动态时间扭曲( CDTW) 是最近提出的一种替代方法, 它没有表现出上述缺点。 CDTW 将Fr\'echach 距离的连续性性质与动态时间扭曲的对比性结合起来, 导致一种对采样率和外星体具有很强的相似性测量。 在最近的Brankovic 等人的实验工作中, 它表明在CDTW 的组合中避免了在动态时间扭曲下和Fr\'echetch 距离下出现的不需要的工艺。 尽管它的优点是, CDTW 的主要缺点是, 在聚合时间或其它情况下, 我们没有精确的计算 CDT 的计算方法。 在这项工作中, 我们第一次使用一种稳定的计算 CDT 的逻辑, 我们的计算中, 我们用一种直态的直径的 。