Performance evaluation and comparison of three counting bloom filter schemes

The Counting Bloom Filter(CBF)is a kind of space-efficient data structure that extends a Bloom filter so as to allow approximate multiplicity queries on a dynamic multi-set.This paper evaluates the performance of multiplicity queries of three simple CBF schemes-the Na(i)ve Counting Bloom Filter(NCBF),the Space-Code Bloom Filter(SCBF)and the d-left Counting Bloom Filter (dlCBF)-using metrics of space complexity and counting error under both uniform and zipfian multiplicity distributions.We compare their counting error under same space complexity,and their space complexity when similar counting errors are achieved respectively.Our results show that dlCBF is the best while SCBF is the worst in terms of both space-efficiency and accuracy.Furthermore,the performance gap between dlCBF and the others has a trend of being enlarged with the increment of space occupation or counting accuracy.