Abstract: Dynamic Time Warping (DTW) is one of the important distance measures in similarity searching of time series; however, the exact calculation has become a bottleneck. An approach named EA_DTW was proposed. The method checked if value of the cell in cumulative distance matrix exceeded the threshold and if so, it would terminate the calculation of other related cells. The theoretical analysis on the process of EA_DTW was made. The empirical experimental results show that EA_DTW outperforms the dynamic DTW calculation in terms of calculation time, and is much better when the threshold is below the real DTW distance.

Key words: time series, similarity search, Dynamic Time Warping (DTW), early abandon

摘要： 动态时间弯曲(DTW)距离是时间序列相似搜索的一种重要距离度量，但其精确计算是一个性能瓶颈。针对此问题，提出一种名为EA_DTW的方法用于加速DTW距离的精确计算，该方法在计算累积距离矩阵中每个方格的距离时都判断其是否超过阈值，一旦超过则提前终止其余相关方格的距离计算;并对EA_DTW的过程进行了理论分析。实验对比表明，EA_DTW能够提高DTW的计算效率，在阈值与DTW距离相比较小时更加明显。

关键词: 时间序列, 相似搜索, 动态弯曲距离, 提前终止