DTW距离的过滤搜索方法

Filtering search method for DTW distance

动态时间弯曲(DTW)距离支持时间序列的多种形变,具有较高的匹配精度,是一种重要的相似性度量方法.然而,该方法计算复杂度较高,制约了其在相似性搜索中的应用.为了平衡匹配精度与计算效率之间的矛盾,提出一种过滤搜索方法.首先,构造一种计算代价较低的DTW下界距离,用其进行粗略过滤,得到候选集;然后,利用提前终止策略,优化计算候选集中序列的DTW距离,得到搜索结果;最后,对所提出方法进行实验验证,结果表明,该方法能够提高DTW距离的相似性搜索效率,且具有非漏报性.

Dynamic time warping（DTW） is an important similarity measure method, which supports a variety of deformation of time series and has high matching precision. However, the method has high computational complexity,which restricts its application in similarity search. In order to balance the contradiction between the matching precision and the computational efficiency, a filtering search method is proposed. Firstly, a lower-bounding distance for DTW is constructed, and it is used in the filtering search to obtain the candidate set. Then, the early abandon strategy is used in the candidate set to achieve the search results. Finally, the proposed method is verified by experiments. The results show that it can improve the similarity search efficiency under DTW and guarantee no false dismissal.