计算机应用 ›› 2011, Vol. 31 ›› Issue (02): 450-453.

• 数据库与数据挖掘 • 上一篇    下一篇

流数据上的频繁项挖掘算法

屠莉1,陈崚2   

  1. 1. 江阴职业技术学院
    2. 扬州大学 信息工程学院; 南京大学 计算机软件新技术国家重点实验室
  • 收稿日期:2010-07-19 修回日期:2010-09-13 发布日期:2011-02-01 出版日期:2011-02-01
  • 通讯作者: 屠莉
  • 基金资助:
    蚁群优化算法的理论基础研究;基于网格环境的高维OLAP数据联机分析与处理技术研究;群体智能优化算法的自聚性、欺骗性和复杂性研究;序列概念格扩展模型及其序列模式挖掘算法研究

Mining frequent items on stream data

  • Received:2010-07-19 Revised:2010-09-13 Online:2011-02-01 Published:2011-02-01
  • Contact: TU Li

摘要: 提出了一种流数据上的频繁项挖掘算法(SW-COUNT)。该算法通过数据采样技术挖掘滑动窗口下的数据流频繁项。给定的误差ε,SW-COUNT可以在O(ε-1)空间复杂度下,检测误差在εn内的数据流频繁项,对每个数据项的平均处理时间为O(1)。大量的实验证明,该算法比其他类似算法具有较好的精度质量以及时间和空间效率。

关键词: 数据流, 频繁项, 滑动窗口, 采样技术, 数据挖掘

Abstract: A frequent items mining algorithm of stream data (SW-COUNT) was proposed, which used data sampling technique to mine frequent items of data flow under sliding windows. Given an error threshold ε, SWCOUNT can detect ε-approximate frequent items of a data stream using O(ε-1) memory space and the processing time for each data item was O(1). A lot of experiments show that SW-COUNT outperforms other methods in terms of the accuracy, memory requirement, and time and space efficiency.

Key words: data stream, frequent item, sliding window, sampling technology, data mining