挖掘滑动窗口中的数据流频繁项算法

作     者：屠莉 陈崚 包芳 TU Li;CHEN Ling;BAO Fang

作者机构：江苏省信息融合软件工程技术研发中心江苏江阴214405 江阴职业技术学院计算机科学系江苏江阴214405 扬州大学计算机科学与工程系江苏扬州225009 南京大学南京大学计算机软件新技术国家重点实验室南京210093 

出 版 物：《小型微型计算机系统》 (Journal of Chinese Computer Systems)

年 卷 期：2012年第33卷第5期

页      面：940-949页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金项目(61070047 61003180)资助 江苏省自然科学基金项目(BK2008206 BK2010311)资助 江苏省教育厅自然科学基金项目(09KJB20013)资助 江苏省信息融合软件工程技术研发中心基金项目(SR-2011-05)资助 江苏省普通高校研究生科研创新计划项目(CX08B_098Z)资助 

主　　题：数据流 频繁项 滑动窗口 

摘      要：滑动窗口是一种对最近一段时间内的数据进行挖掘的有效的技术,本文提出一种基于滑动窗口的流数据频繁项挖掘算法.算法采用了链表队列策略大大简化了算法,提高了挖掘的效率.对于给定的阈值S、误差ε和窗口长度n,算法可以检测在窗口内频度超过Sn的数据流频繁项,且使误差在εn以内.算法的空间复杂度为O(ε-1),对每个数据项的处理和查询时间均为O(1).在此基础上,我们还将该算法进行了扩展,可以通过参数的变化得到不同的流数据频繁项挖掘算法,使得算法的时间和空间复杂度之间得到调节.通过大量的实验证明,本文算法比其它类似算法具有更好的精度以及时间和空间效率.