Counting Data Stream based on Improved Counting Bloom Filter

摘要

Burst detection is an inherent problem for data streams, so it has attracted extensive attention in research community due to its broad applications. One of the basic problems in burst detection is how to count frequencies of all elements in data stream. This paper presents a novel solution based on Improved Counting Bloom Filter, which is also called BCBF+HSet. Comparing with intuitionistic approach such as array and list, our solution significantly reduces space complexity though it introduces few error rates. Further, we discuss space/time complexity and error rate of our solution, and compare it with two classic Counting Bloom Filters, CBF and DCF. Theoretical analysis and simulation results demonstrate the efficiency of the proposed solution.