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

摘要：

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

关键词：数据流、频繁项、滑动窗口

所属期刊栏目：33

分类号：TP311(计算技术、计算机技术)

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

在线出版日期：2012-09-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：940-949