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

Flow Counting Algorithm for Data Stream Model

作　　者：廖豪[1,2] 梁峰[3] 谭建龙[1] 

机构地区：[1]中国科学院计算技术研究所,北京100190 [2]中国科学院研究生院,北京100049 [3]湘潭大学信息工程学院,湖南湘潭411105

出　　处：《计算机工程》2010年第23期31-33,35,共4页Computer Engineering

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

摘　　要：在研究数据流过程中,基于现有的概要数据结构Bloom Filter,给出改进的K-Bloom Filter结构,从理论上对假阳性误判进行分析,得出两者具有相同的在误判率f0下表示集合规模的上限n0,因此,K-Bloom Filter的误判率在可控范围内。提出基于K-Bloom Filter的流计数算法,与基于Bloom Filter的流计数算法相比,在相同的空间复杂度O(m)和插入操作时间复杂度O(k)情况下,该算法降低了统计结果的误差。During the process of studying data stream,this paper proposes the K-Bloom Filter structure which is based on the existing synopsis data structure,analyses the false positive misjudgment theoretically,concludes that both can present the upper limits of set scale n_（0）under the same misjudgment rate f_0,so the misjudgment rate of K-Bloom Filter is within the controllable range.The flow counting algorithm based on the K-Bloom Filter structure is gived,under the same space complexity O（m） and insert time complexity O（k）,compared to the flow counting algorithm based on the Bloom Filter structure,the error of the counting result is lower.

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

分 类 号：TP311.52[自动化与计算机技术—计算机软件与理论]