计算机工程与应用2019，Vol.55Issue(2)：54-59,71,7.DOI:10.3778/j.issn.1002-8331.1801-0383
基于自适应搜索窗口的序列相似比对算法
Similarity Alignment Algorithm for Series Based on Adaptive Searching Window
摘要
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 align-ment algorithm for series based on adaptive search window(ADTW). The algorithm uses Piecewise Aggregate Approxi-mation(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 calcu-lates a new search window. Finally, it realizes fast solutions of DTW distances and warping path. Compared with Fast-DTW, the ADTW algorithm can improve the computational efficiency by about 20% with the same measurement preci-sion and the time complexity is O(n) .关键词
相似搜索/时序度量/动态时间规整(DTW)/搜索窗口Key words
similarity search/time series metric/Dynamic Time Warping(DTW)/searching window分类
信息技术与安全科学引用本文复制引用
范纯龙,崔宇斌,滕一平..基于自适应搜索窗口的序列相似比对算法[J].计算机工程与应用,2019,55(2):54-59,71,7.基金项目
国家自然科学基金(No.61261018,No.61472094) （No.61261018,No.61472094）
广西自然科学基金杰出青年基金(No.2014GXNSFGA118007) （No.2014GXNSFGA118007）
2018年浙江省重点研发计划(No.2018C01059). （No.2018C01059）
