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...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 Naive 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 dICBF 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.展开更多
基金Supported by the National Grand Fundamental Research 973 Program of China (No.2007CB307100, No.2007CB 307102)
文摘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 Naive 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 dICBF 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.