时间序列流Top-K不协调子序列的发现  

Discovery of Top-K discords for time series stream

作　　者：姚仁贵 张坤龙[1] Yao Rengui Zhang Kunlong(School of Computer Science ＆ Technology, Tianjin University, Tianjin 300072, Chin)

机构地区：[1]天津大学计算机科学与技术学院,天津300072

出　　处：《计算机应用研究》2016年第12期3606-3610,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(61303021);水利部公益性行业科研专项基金资助项目(201401033)

摘　　要：针对传统算法中有关时间序列流不协调子序列计算代价比较高的问题,提出了一种快速发现Top-K不协调子序列的算法。该算法通过特殊的数据结构保留计算结果,避免了大量的重复计算,从而达到降低时间复杂度的目的;同时也通过一定的保留策略只保留有用的计算结果并及时清理无用的计算结果,从而达到降低空间复杂度的目的。实验采用随机数据和真实数据进行算法测试,其结果表明,该算法能显著降低计算量从而实现快速发现Top-K不协调子序列的目的。This paper proposed an algorithm for discovery of Top-K discords for time series stream to solve the problem that the traditional algorithms have high cost computation. To reduce the time complexity, the algorithm adopted a special data structure to save the results of the computation. The algorithm also could reduce the space complexity by saving only useful results and timely cleaning up useless results by some Strategies. Experiment tests on random data and real data, this proposed algorithm can significantly reduce the cost of computation and realize the real-time discovery of Top-K discords for time series stream.

关 键 词：流时间序列 不协调子序列 实时 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]