| 摘要: |
| 对3 种已有的计数型Bloom filter——Na?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 略高. |
| 关键词: 计数型Bloom filter 性能评估 性能比较 负载适应性 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Basic Research Program of China under Grant Nos.2007CB307100, 2007CB307102 (国家重点基础研究
发展计划(973)) |
|
| Performance Evaluation and Comparison of Four Counting Bloom Filter Schemes |
|
ZHANG Jin,WU Jiang-Xing,LIU Qin-Rang
|
| Abstract: |
| The Counting Bloom Filter (CBF) is a space-efficient data structure that extends a Bloom filter so as to
allow approximate multiplicity queries on a dynamic multi-set. An in-depth study of three existing CBF schemes is
presented, that is, the Na?ve Counting Bloom Filter (NCBF), the Space-Code Bloom Filter (SCBF) and the d-left
Counting Bloom Filter (dlCBF). Then, a CBF scheme called Binary Shrinking d-left Counting Bloom Filter
(BSdlCBF) is proposed. A performance metrics named load adaptability for CBF schemes is also defined. The
performance of the four CBF schemes is evaluated by using metrics of counting error, space complexity and load
adaptability under both uniform and Zipfian multiplicity distributions. The experimental results show that the
proposed BSdlCBF outperforms the other three in terms of accuracy, space-efficiency and load adaptability. The
cost of such an advantage of BSdlCBF is a reasonable rise in computational and space complexity. |
| Key words: counting bloom filter performance evaluation performance comparison load adaptability |
