CAJ | 학술논문

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