Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
复制标题
强次二次时间中的动态时间扭曲：低距离状态和近似评估的算法
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
William Kuszmaul
中科院分区：
文献类型：
--
作者：
William Kuszmaul
动态时间翘曲距离（DTW）是时间序列之间广泛使用的距离度量。最著名的计算DTW算法在几乎二次的时间内运行，条件下限禁止存在明显更快的算法。但是，对于DTW很小的特殊情况，下限并不能阻止更快的算法。对于任意度量空间$ sigma $具有标准化的距$ sigma $ in Time $ o（n cdot operatorname {dtw}（x，y））$。我们还提出了一种近似算法，该算法计算$ operatorName {dtw}（x，y）$，以内$ o（n^epsilon）$ in time $ ililde {o}（n^{2 -epsilon}）$ 0 <Epsilon <1 $。该算法允许使用与对数深度和最多指数宽高比的任意良好分离的树度量的字符串$ x $和$ y $。进一步扩展我们的技术，我们还获得了第一个用于编辑距离的近似算法，以与从任意度量空间中获取的字符一起使用，在时间$ n^epsilon $ -Approximation时为时间$ iLde {o}（n^{2- epsilon}） ）$，具有很高的可能性。此外，我们提供了从计算编辑距离到计算DTW的简单减少。将我们的还原应用于Bringmann和Kunnemann的条件下限，与$ {0，1} $上的编辑距离有关，我们获得了一个有条件的下限，用于计算DTW在三个字母字母上计算DTW（距离为零，一个）。这在先前的Abboud，Backurs和Williams的结果上得到了改善。采用类似的方法，我们证明从计算编辑距离到计算最长的LCS长度的减少。这意味着人们可以直接从编辑距离的距离中恢复LCS的有条件下限，这不是以前认为是这种情况。
Dynamic time warping distance (DTW) is a widely used distance measure between time series. The best known algorithms for computing DTW run in near quadratic time, and conditional lower bounds prohibit the existence of significantly faster algorithms. The lower bounds do not prevent a faster algorithm for the special case in which the DTW is small, however. For an arbitrary metric space $Sigma$ with distances normalized so that the smallest non-zero distance is one, we present an algorithm which computes $operatorname{dtw}(x, y)$ for two strings $x$ and $y$ over $Sigma$ in time $O(n cdot operatorname{dtw}(x, y))$. We also present an approximation algorithm which computes $operatorname{dtw}(x, y)$ within a factor of $O(n^epsilon)$ in time $ ilde{O}(n^{2 - epsilon})$ for $0 < epsilon < 1$. The algorithm allows for the strings $x$ and $y$ to be taken over an arbitrary well-separated tree metric with logarithmic depth and at most exponential aspect ratio. Extending our techniques further, we also obtain the first approximation algorithm for edit distance to work with characters taken from an arbitrary metric space, providing an $n^epsilon$-approximation in time $ ilde{O}(n^{2 - epsilon})$, with high probability. Additionally, we present a simple reduction from computing edit distance to computing DTW. Applying our reduction to a conditional lower bound of Bringmann and Kunnemann pertaining to edit distance over ${0, 1}$, we obtain a conditional lower bound for computing DTW over a three letter alphabet (with distances of zero and one). This improves on a previous result of Abboud, Backurs, and Williams. With a similar approach, we prove a reduction from computing edit distance to computing longest LCS length. This means that one can recover conditional lower bounds for LCS directly from those for edit distance, which was not previously thought to be the case.