基于增量DFT的相似时序检索算法  

Incremental DFT based quick search algorithm of finding similar sequence

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

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

出　　处：《控制与决策》2004年第3期299-302,共4页Control and Decision

基　　金：国家自然科学基金资助项目(60272040).

摘　　要：首先提出一种在时域上计算时序数据扩展距离的新算法,该算法时间复杂度为O(n×m),能够解决时序数据在Y轴上的漂移和伸缩后仍然保留相似性的问题;然后提出一种在频域上计算时序数据扩展距离和在长时序中搜索相似子序列的新算法,该算法时间复杂度仅为O(n×fc),效率很高,便于在线实现,而且同样能够适应时序数据扩展距离的定义;最后给出时序数据和线性加权时序数据的增量式DFT算法,可以对长时序的各个窗口进行增量式的降维,将传统的O(n×m×fc)工作改进成O(n×fc).A new algorithm, with the time complexity O(n×m), of computing the time series extended distance on time domain is presented. The algorithm can solve the problems brought by the data scaling and shifting on the Y axis. An algorithm of computing the time series extended distance on reduced frequency domain and finding the most similar subsequence from given long sequence is also given. The algorithm, with the time complexity O(n×fc), can be implemented online and adapts to the extended distance definition. A incremental DFT algorithm on time series data and linear weighted time series is proposed, which greatly reduces the dimensions on each window of a long sequence.

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

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