期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于最窄平行四边形的数据流突变检测算法

Narrowest Parallelogram Coverage Burst Detection in Data Streams
在线阅读 下载PDF
导出
摘要 数据流上的突变检测在网络流量监测、金融风险分析、传感器网络等领域都有着十分广泛的应用.传统的突变检测算法只能对流上的聚集函数值进行检测,这在实际应用中往往不能满足用户的需求.提出了一种新颖的数据流上的突变检测算法,即最窄平行四边形法.该方法用一系列很窄的平行四边形来表示流上具有相同趋势的点,并保证每个点的误差不超过平行四边形宽度的一半.于是,对等距到达的数据,便可根据所得的平行四边形还原其中的每一个点,从而实现基于任意类型函数的突变检测.此外,对最窄平行四边形算法作了改进,使其时间复杂度降为O(h),其中h为平行四边形内凸包的顶点个数.最后,通过在两个真实数据集上的实验,以及与现有突变检测算法的比较,验证了最窄平行四边形算法在时间和空间上的高效性.
作者 陈飞波 钱卫宁 周傲英
机构地区 复旦大学计算机科学与工程系
出处 《计算机研究与发展》 EI CSCD 北大核心 2007年第z3期505-510,共6页 Journal of Computer Research and Development
基金 国家自然科学基金项目(60673134,60673134)
关键词 数据流 突变检测 最窄平行四边形
分类号 TP311 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献13

  • 1金澈清,钱卫宁,周傲英.流数据分析与管理综述[J].软件学报,2004,15(8):1172-1181. 被引量：161
  • 2[2]B Brian,B Shivanath,D Mayur,et al.Models and issues in data stream systems.PODS'02,Madison,Wisconsin,USA,2002
  • 3[3]J Kleinberg.Bursty and hierarchical structure in streams.SIGKDD'02,Edmonton,Alberta,Canada,2002
  • 4李建中,郭龙江,张冬冬,王伟平.数据流上的预测聚集查询处理算法[J].软件学报,2005,16(7):1252-1261. 被引量：24
  • 5[5]G Cormode,S Muthukrishnan.What's new:Finding significant differences in network data streams.IEEE/ACM Trans on Networking,2005,13(6):1219-1232
  • 6[6]B Krishnamurthy,S Sen,Y Zhang,et al.Sketch-based change detection:Methods,evaluation,and applications.INFOCOM'04,Hong Kong,2004
  • 7[7]A C Gelbert,et al.Fast,small-space algorithms for approximate histogram maintenance.STOC'02,Montréal,Québec,Canada,2002
  • 8[8]Aoying Zhou,Shouke Qin,Weining Qian.Adaptively detecting aggregation bursts in data streams.DASFAA'05,Beijing,2005
  • 9[9]Shouke Qin,Weining Qian,Aoying Zhou.Approximately processing multi-granularity aggregate queries over data streams.ICDE'06,Atlanta,Georgia,USA,2006
  • 10秦首科,钱卫宁,周傲英.基于分形技术的数据流突变检测算法[J].软件学报,2006,17(9):1969-1979. 被引量：12

二级参考文献55

  • 1金澈清,钱卫宁,周傲英.流数据分析与管理综述[J].软件学报,2004,15(8):1172-1181. 被引量：161
  • 2郭龙江,李建中,王伟平,张冬冬.数据流上的连续预测聚集查询[J].计算机研究与发展,2004,41(10):1690-1695. 被引量：4
  • 3李建中,郭龙江,张冬冬,王伟平.数据流上的预测聚集查询处理算法[J].软件学报,2005,16(7):1252-1261. 被引量：24
  • 4Babcock B, Babu S, Datar M, Motwani R, Widom J. Models and issues in data streams. In: Popa L, ed. Proc. of the 21st ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. Madison: ACM Press, 2002. 1～16.
  • 5Terry D, Goldberg D, Nichols D, Oki B. Continuous queries over append-only databases. SIGMOD Record, 1992,21(2):321-330.
  • 6Avnur R, Hellerstein J. Eddies: Continuously adaptive query processing. In: Chen W, Naughton JF, Bernstein PA, eds. Proc. of the 2000 ACM SIGMOD Int'l Conf. on Management of Data. Dallas: ACM Press, 2000. 261～272.
  • 7Hellerstein J, Franklin M, Chandrasekaran S, Deshpande A, Hildrum K, Madden S, Raman V, Shah MA. Adaptive query processing: Technology in evolution. IEEE Data Engineering Bulletin, 2000,23(2):7-18.
  • 8Carney D, Cetinternel U, Cherniack M, Convey C, Lee S, Seidman G, Stonebraker M, Tatbul N, Zdonik S. Monitoring streams?A new class of DBMS applications. Technical Report, CS-02-01, Providence: Department of Computer Science, Brown University, 2002.
  • 9Guha S, Mishra N, Motwani R, O'Callaghan L. Clustering data streams. In: Blum A, ed. The 41st Annual Symp. on Foundations of Computer Science, FOCS 2000. Redondo Beach: IEEE Computer Society, 2000. 359-366.
  • 10Domingos P, Hulten G. Mining high-speed data streams. In: Ramakrishnan R, Stolfo S, Pregibon D, eds. Proc. of the 6th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. Boston: ACM Press, 2000. 71-80.

共引文献191

计算机研究与发展
2007年 第z3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部