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

摘要

对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略高.