基于分形技术的数据流突变检测算法

被引：11

作者：

秦首科

钱卫宁

周傲英

机构：

[1] 复旦大学计算机科学与工程系

来源：

软件学报 | 2006年 / 09期

关键词：

数据流; 突变检测; 分形; 分段分形模型; 搜索空间;

D O I：

暂无

中图分类号：

TP393.06 [];

学科分类号：

081201 ; 1201 ;

摘要：

数据流上的突变检测技术由于其在风险分析、网络监测、趋势分析等领域广阔的应用前景而受到学术界和工业界越来越多的关注.为了在数据流上检测多个滑动窗口上的单调聚集函数值和非单调聚集函数值的突变,提出了基于分形技术的构建单调搜索空间的突变检测算法.首先给出了数据流上的分段分形模型,进而基于该模型设计了突变检测算法.该算法能够将突变检测处理时间复杂度从O(m)降为O(logm)(m为需要被检测的滑动窗口数目).提出的两种新颖的分段分形模型能够准确地对数据流的自相似性进行建模并压缩数据流.理论分析和实验结果表明,与已有研究成果相比,算法具有较高的精度和较低的时间/空间复杂度,更加适用于进行数据流的突变检测.

引用

页码：1969 / 1979

页数：11