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

• 作者: 廖豪 梁峰 谭建龙
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 数据流 布鲁姆过滤器 概要数据结构
• 年，卷（期）: 2010,（23）
• 页码范围: 31-33,35
• 分类号: TP311.52
• 字数: 3405字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2010.23.011

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谭建龙	中国科学院计算技术研究所	43	444	11.0	19.0
2	廖豪	中国科学院计算技术研究所	3	5	1.0	2.0
6	梁峰	湘潭大学信息工程学院	1	1	1.0	1.0