相似时间序列的快速检索算法

Quick Search Algorithm of Finding Similar Sequence

在前人提出的扩展时序数据距离定义的基础上 ,首先提出一种在时域上计算时序数据距离的新算法 ,该算法时间复杂度为 O( n× m ) ,能够解决时序数据在 Y轴上的漂移和伸缩带来的问题 ;之后提出一种在频域上计算时序数据距离的新算法 ,该算法时间复杂度仅为 O( n× fc) ,效率很高 ,便于在线实现 ,而且同样能够解决时序数据漂移和伸缩的问题 ;本文还给出和证明了该算法的一个重要组成部分 :时序数据增量式的

Basing on the extended definition of time series distance, first presents a new algorithm of computing the time series distance on time domain. The time complexity of the algorithm is O(n×m). The algorithm can solve the problems brought by the data scaling and shifting on the Y axis. Then presents a new algorithm of computing the time series distance on frequency domain. The algorithm, with the time complexity of O(n×f c), is very effective, so it can be implemented online. The algorithm can also adaptive to the extended distance definition. This paper also gives and proves an important part of the new algorithm: a increment DFT algorithm on time series.