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

Quick Search Algorithm of Finding Similar Sequence

作　　者：郑烇[1] 朱明[1] 王俊普[1] 蔡庆生[2] 

机构地区：[1]中国科学技术大学自动化系,安徽合肥230027 [2]中国科学技术大学计算机系,安徽合肥230027

出　　处：《小型微型计算机系统》2004年第5期785-789,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目 ( 60 2 72 0 40 )资助

摘　　要：在前人提出的扩展时序数据距离定义的基础上 ,首先提出一种在时域上计算时序数据距离的新算法 ,该算法时间复杂度为 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.

关 键 词：时间序列 子时序 相似度 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]