一种高效的基于滑动窗口的数据流频繁元素挖掘算法
挖掘频繁元素是数据流研究领域的一个重要问题。由于数据流具有高速流动、规模无限等特点，因此在数据流上挖掘频繁元素很具挑战性，主要有：动态的维护概要数据结构;使用远小于数据规模的内存空间;快速的响应用户查询。本文提出了一种新的确定的基于滑动窗口的数据流频繁元素挖掘算法。该算法将固定元素个数的滑动窗口划分为若干基本窗口，在每个基本窗口上用较小的空间维护较高精度的概要数据结构。算法既能够以基本窗口为单位定期返回满足ε-近似要求的结果，也可以对任意时刻的即席查询请求返回近似结果。实验表明，该算法在zipf数据分布下性能较好，处理即席查询的误差也比较小。
数据流 频繁元素 滑动窗口 基本窗口 ε-近似
李坤 王永炎 王宏安
中国科学院软件技术研究所人机交互技术与智能信息处理实验室，北京，100080 中国科学院研究生院，北京，100049 中国科学院软件技术研究所人机交互技术与智能信息处理实验室，北京，100080
国内会议
苏州
中文
1033-1041
2007-10-18（万方平台首次上网日期，不代表论文的发表时间）