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

发布时间：2018-08-13 12:48

【摘要】：针对传统算法中有关时间序列流不协调子序列计算代价比较高的问题,提出了一种快速发现Top-K不协调子序列的算法。该算法通过特殊的数据结构保留计算结果,避免了大量的重复计算,从而达到降低时间复杂度的目的;同时也通过一定的保留策略只保留有用的计算结果并及时清理无用的计算结果,从而达到降低空间复杂度的目的。实验采用随机数据和真实数据进行算法测试,其结果表明,该算法能显著降低计算量从而实现快速发现Top-K不协调子序列的目的。
[Abstract]:In order to solve the problem of high computation cost of time series flow uncoordinated subsequences in traditional algorithms, a fast algorithm for discovering Top-K discordant subsequences is proposed. The algorithm preserves the computation result through the special data structure, avoids a lot of duplicate computation, thus achieves the goal of reducing the time complexity; At the same time, only useful computing results are retained and the useless results are cleaned up in time by a certain retention strategy, so that the space complexity can be reduced. The experiment uses random data and real data to test the algorithm. The results show that the algorithm can significantly reduce the computational complexity and achieve the purpose of quickly discovering the Top-K discordant subsequences.
【作者单位】： 天津大学计算机科学与技术学院;
【基金】：国家自然科学基金资助项目(61303021) 水利部公益性行业科研专项基金资助项目(201401033)
【分类号】：TP311.13

【相似文献】

相关期刊论文 前10条

1 方俊初;吕虹;张爱雪;;产生m子序列的一种实用算法[J];河北工程大学学报(自然科学版);2012年04期

2 胡晓琳;陈晓云;;基于符号化表示的时间序列频繁子序列挖掘[J];计算机工程;2008年10期

3 张力生;杨美洁;雷大江;;时间序列重要点分割的异常子序列检测[J];计算机科学;2012年05期

4 王防修;周康;;基于最长公共子序列的随机路径选择算法设计[J];计算机工程与设计;2014年06期

5 郑翠玲;;最长公共子序列算法的分析与实现[J];武夷学院学报;2010年02期

6 王达,荣冈,李鸿亮;一种变步长趋势子序列搜索算法[J];浙江大学学报(工学版);2004年12期

7 郭冬梅;;基于状态压缩的最长公共上升子序列快速算法[J];计算机技术与发展;2014年05期

8 杨海斌;赵学锋;王秀花;张利香;;一种求所有最长增量子序列的算法[J];山东大学学报(工学版);2010年06期

9 孟升卫;陈陆君;郭耀;;同相反相混合孤子序列的相互作用及其通信应用初探[J];西安电子科技大学学报;1993年04期

10 李欣,舒风笛;最长公共子序列问题的改进快速算法[J];计算机应用研究;2000年02期

相关会议论文 前5条

1 赵丽丽;王建波;杨会杰;;人类启动子序列的复杂性[A];数学·力学·物理学·高新技术交叉研究进展——2010（13）卷[C];2010年

2 刘维;陈];;基于剪枝跳跃技术的最长公共子序列算法[A];2006年全国理论计算机科学学术年会论文集[C];2006年

3 柯琦;钟诚;李智;王刚强;;多核计算机上最大和子序列线程级并行算法[A];全国第21届计算机技术与应用学术会议（CACIS·2010）暨全国第2届安全关键技术与应用学术会议论文集[C];2010年

4 倪晟宇;;在流数据模式下计算最长递增子序列长度[A];2005年全国理论计算机科学学术年会论文集[C];2005年

5 苗玉发;李波;;CMV启动子序列检测的复合实时定量PCR方法的建立[A];中国毒理学会第六届全国毒理学大会论文摘要[C];2013年

相关重要报纸文章 前4条

1 ;编程沙龙[N];电脑报;2003年

2 PALADIN;编程沙龙[N];电脑报;2003年

3 PALADIN;编程沙龙[N];电脑报;2003年

4 信息产业部电信设备认证中心 周冉;分子序列压缩：提高广域网效率的利器[N];通信产业报;2006年

相关博士学位论文 前2条

1 王树林;生物子序列频数分布与肿瘤亚型分类模型研究[D];国防科学技术大学;2007年

2 孙芳;零和自由序列的子序列和问题[D];南开大学;2010年

相关硕士学位论文 前3条

1 赵晓燕;基于多索引的高维时间序列子序列检索研究[D];大连理工大学;2010年

2 朱鹤;结果分级的快速子序列相似查询方法研究[D];燕山大学;2010年

3 高鸿远;基于子序列匹配的压缩XML查询[D];哈尔滨工业大学;2009年

，

本文编号：2181044