一种面向数据流模型的流计数算法

摘要：

在研究数据流过程中,基于现有的概要数据结构Bloom Filter,给出改进的K-Bloom Filter结构,从理论上对假阳性误判进行分析,得出两者具有相同的在误判率f0下表示集合规模的上限n0,因此,K-Bloom Filter的误判率在可控范围内.提出基于K-Bloom Filter的流计数算法,与基于Bloom Filter的流计数算法相比,在相同的空间复杂度O(m)和插入操作时间复杂度O(k)情况下,该算法降低了统计结果的误差.

关键词：数据流、布鲁姆过滤器、概要数据结构

所属期刊栏目：36

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

资助基金：国家"973"计划基金资助项目2007CB311100

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

页数：共4页

页码：31-33,35