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.

作者: Zhijian Yuan Jiajia Miao Yan Jia Le Wang

作者单位: Computer School,National University of Defense Technology,Changsha,China

会议类型: 国际会议

会议名称: The Ninth International Conference on Web-Age Information Management(第九届web时代信息管理国际会议)(WAIM 2008)

会议地点: 张家界

会议语种:英文

在线出版日期: 2008-07-20（万方平台首次上网日期，不代表论文的发表时间）