论文标题
在动态时间扭曲下的时间序列的确切索引
Exact Indexing of Time Series under Dynamic Time Warping
论文作者
论文摘要
动态时间扭曲（DTW）是时间序列的强大相似性度量。但是，它不满足三角形不平等，并且具有很高的计算复杂性，从而严重限制了其在大规模数据集上的相似性搜索中的应用。通常，我们求助于下限距离，以加快DTW下的相似性搜索。不幸的是，仍然缺乏有效的下限距离，可以测量不等的时间序列并且具有理想的紧密度。在论文中，我们提出了一种新颖的下限距离lb_keogh+，这是序列扩展和lb_keogh的无缝组合。它可用于不等的序列，并且计算复杂性较低。此外，lb_keogh+可以将序列扩展到任意合适的长度，而不会显着降低紧密度。接下来，基于LB_KEOGH+，设计了DTW下时间序列的精确索引。然后，我们介绍了几个定理，并完成相关的证据，以确保我们的相似性搜索中没有错误的解雇。最后，在现实世界数据集上进行了广泛的实验。实验结果表明，我们提出的方法可以对具有高度紧密度和良好修剪功率的不等长度序列进行相似性搜索。
Dynamic time warping (DTW) is a robust similarity measure of time series. However, it does not satisfy triangular inequality and has high computational complexity, severely limiting its applications in similarity search on large-scale datasets. Usually, we resort to lower bounding distances to speed up similarity search under DTW. Unfortunately, there is still a lack of an effective lower bounding distance that can measure unequal-length time series and has desirable tightness. In the paper, we propose a novel lower bounding distance LB_Keogh+, which is a seamless combination of sequence extension and LB_Keogh. It can be used for unequal-length sequences and has low computational complexity. Besides, LB_Keogh+ can extend sequences to an arbitrary suitable length, without significantly reducing tightness. Next, based on LB_Keogh+, an exact index of time series under DTW is devised. Then, we introduce several theorems and complete the relevant proofs to guarantee no false dismissals in our similarity search. Finally, extensive experiments are conducted on real-world datasets. Experimental results indicate that our proposed method can perform similarity search of unequal-length sequences with high tightness and good pruning power.
