Abstract: DTW（Dynamic Time Warping） has been widely used in series data alignment to measure the distance between series, but the high time complexity limits its application in long series alignment. This paper proposes a similarity alignment algorithm for series based on adaptive search window（ADTW）. The algorithm uses Piecewise Aggregate Approximation（PAA） strategy to obtain low-precision series, then computes the alignment path under low-precision series and predicts the path deviation according to the gradient variation on the low-precision distance matrix, limits the scope of the path search window. Then it improves the series accuracy gradually, modifies the path in the search window and calculates a new search window. Finally, it realizes fast solutions of DTW distances and warping path. Compared with FastDTW, the ADTW algorithm can improve the computational efficiency by about 20% with the same measurement precision and the time complexity is [O(n)].

Key words: similarity search, time series metric, Dynamic Time Warping（DTW）, searching window

摘要： DTW（Dynamic Time Warping）算法被广泛应用于序列数据比对，以度量序列间距离，但算法较高的时间复杂度限制了其在长序列比对上的应用。提出基于自适应搜索窗口的序列相似比对算法（ADTW），算法利用分段聚集平均（Piecewise Aggregate Approximation，PAA）策略进行序列抽样得到低精度序列，然后计算低精度序列下的比对路径，并根据低精度距离矩阵上的梯度变化预测路径偏差，限制路径搜索窗口的拓展范围；随后算法逐步提高序列精度，并在搜索窗口内修正路径、计算新的搜索窗口，最终，实现DTW距离和相似比对路径的快速求解。对比FastDTW，ADTW算法在同等度量准确率下提高计算效率约20%，其时间复杂度为[O(n)]。

关键词: 相似搜索, 时序度量, 动态时间规整（DTW）, 搜索窗口