4种计数型Bloom Filter的性能分析与比较

• 作者: 刘勤让 张进 邬江兴
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 计数型Bloom filter 性能评估 性能比较 负载适应性
• 年，卷（期）: 2010,（5）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 1098-1114
• 分类号: TP393
• 字数: 11457字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2010.03495

摘要

对3种已有的计数型Bloom filter--Na(I)ve Counting Bloom Filter(NCBF),Space-Code Bloom Filter (SCBF)和d-left Counting Bloom Filter(dlCBF)--的查询错误概率进行了分析,得出了NCBF的计数器防溢出条件以及SCBF和dlCBF的参数最优设置准则.提出了一种衡量计数型Bloom filter性能的指标:负载适应性.针对dlCBF负载适应性差的问题,对dlCBF进行了改进,提出了一种计数型Bloom filter:Binary Shrinking d-left Counting Bloom Filter(BSdlCBF).通过仿真实验,以计数误差、空间复杂度以及负载适应性为性能指标,对上述4种CBF进行了比较.实验结果表明,BSdlCBF具有最低的空间复杂度、最小的计数误差以及最佳的负载适应性. BSdlCBF赢得上述性能优势的代价在于其计算复杂度比其他3种计数型Bloom filter略高.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	邬江兴		93	559	12.0	19.0
2	刘勤让		58	257	9.0	13.0
3	张进		9	48	3.0	6.0