论文标题
更快地减少动态时间翘曲距离至最长增加的子序列长度
A faster reduction of the dynamic time warping distance to the longest increasing subsequence length
论文作者
论文摘要
一对时间序列（即按时间顺序的索引值序列）之间的相似性通常是由动态时间扭曲（DTW）距离估算的，而不是在良好的度量家族中，包括最长的共同子序列（LCS）长度和编辑距离。尽管似乎DTW和LCS（类似）度量基本上是不同的，但我们揭示了DTW距离可以用一系列整数的最长增加子序列（LIS）长度表示，这是Integer序列之间的LCS长度，这是Integer序列之间的LCS长度。对于给定的长度$ n $的时间序列，使任何元素之间的差异是零和$ c $之间的整数，我们提出了一个整数序列，代表任何子字符串 - 缩放dtw距离作为其带subsubstring lis长度。生成的整数序列的长度为$ O（C n^2）$，可以将其转换为$ O（n^2）$，用于恒定差异函数。为了证明在LCS（ - 样）测量中开发的技术直接适用于通过将DTW减少到LIS的时间序列分析，我们提出了使用用于LCS相关问题的半局部序列比较技术的DTW相关问题的时间效率算法。
The similarity between a pair of time series, i.e., sequences of indexed values in time order, is often estimated by the dynamic time warping (DTW) distance, instead of any in the well-studied family of measures including the longest common subsequence (LCS) length and the edit distance. Although it may seem as if the DTW and the LCS(-like) measures are essentially different, we reveal that the DTW distance can be represented by the longest increasing subsequence (LIS) length of a sequence of integers, which is the LCS length between the integer sequence and itself sorted. For a given pair of time series of length $n$ such that the dissimilarity between any elements is an integer between zero and $c$, we propose an integer sequence that represents any substring-substring DTW distance as its band-substring LIS length. The length of the produced integer sequence is $O(c n^2)$, which can be translated to $O(n^2)$ for constant dissimilarity functions. To demonstrate that techniques developed under the LCS(-like) measures are directly applicable to analysis of time series via our reduction of DTW to LIS, we present time-efficient algorithms for DTW-related problems utilizing the semi-local sequence comparison technique developed for LCS-related problems.
