海量数据流上快速Top-K子序列匹配算法研究  

Research on the Fast Top-K Subsequence Matching Algorithm over Massive Data Streams

作　　者：苏亮[1] 邹鹏[1] 贾焰[1] 杨树强[1] 

机构地区：[1]国防科技大学计算机学院,湖南长沙410073

出　　处：《计算机工程与科学》2009年第6期58-61,共4页Computer Engineering & Science

基　　金：国家863计划资助项目(2006AA01Z451;2006AA10Z237);国家973计划资助项目(2005CB321804)

摘　　要：数据流技术在金融分析、网络监控等诸多领域得到了广泛应用,而已有的子序列匹配算法主要针对静态序列,难于直接应用到海量、高速和连续的流数据。本文在动态时间规整技术的基础上,提出了一种新颖的TopKSM算法,能渐进、实时地获取Top-K相似子序列。算法完全符合数据流"单遍扫描"的性能要求。大量的实验表明,与现有的SPRING算法相比,该算法具有更高的性能。Data stream techniques have been applied in wide fields such as financial analysis and network monitoring. The existing subsequence matching algorithms mainly focus on the static time series and are hardly used to massive, highspeed and continuous steam data. Based on the dynamic time warping technique, this paper provides a novel TopKSM algo rithm which can find the top- K similar subsequences in a progressive and real time fashion. It completely fits the ＂single pass＂ requirement of data streams. Comprehensive experiments show that our algorithm has higher performance than the SPRING algorithm.

关 键 词：子序列匹配 动态时间规整 TOP-K 数据流 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]