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

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