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

对3种已有的计数型bloomfilter——na?vecountingbloomfilter(ncbf),space-codebloomfilter(scbf)和d-leftcountingbloomfilter(dlcbf)——的查询错误概率进行了分析,得出了ncbf的计数器防溢出条件以及scbf和dlcbf的参数最优设置准则.提出了一种衡量计数型bloomfilter性能的指标:负载适应性.针对dlcbf负载适应性差的问题,对dlcbf进行了改进,提出了一种计数型bloomfilter:binaryshrinkingd-leftcountingbloomfilter(bsdlcbf).通过仿真实验,以计数误差、空间复杂度以及负载适应性为性能指标,对上述4种cbf进行了比较.实验结果表明,bsdlcbf具有最低的空间复杂度、最小的计数误差以及最佳的负载适应性.bsdlcbf赢得上述性能优势的代价在于其计算复杂度比其他3种计数型bloomfilter略高.