基于循环BloomFilter的数据流上不同值个数的估计  

The Estimation of the Number of Distinct Values over Data Streams Based on Circular Bloom-Filter

作　　者：任美睿[1] 郭龙江[1] 玄萍[1] 

机构地区：[1]黑龙江大学计算机科学技术学院,哈尔滨150080

出　　处：《计算机工程与应用》2006年第19期151-154,共4页Computer Engineering and Applications

基　　金：黑龙江省教育厅科学技术研究一般项目(编号:10551246);黑龙江大学青年基金项目(编号:QL200428;QL200432)

摘　　要：数据流是连续的、实时的无限数据,到目前为止还没有有效的方法将数据流存储起来,因此数据流上的不同值个数的估计也就成为一个比较难的研究课题。文章在对BloomFilter进行分析研究的基础上,结合数据流无限、连续、实时等特点,提出了基于循环BloomFilter的数据流上不同值个数的估计策略。将数据流中的不同值存储在循环BloomFilter中,有效地解决了在内存有限情况下,无法保存数据流中的不同值的问题。通过与现有的估计算法的比较,实验结果表明基于循环BloomFilter的估计策略是可行和有效的。Due to data streams＇ continuous,real-time and unbounded nature,at present data streams may not be stored in bounded memory by an effective method,so to estimate the number of distinct values over data streams is a more difficult problem.In this paper,combining with data streams＇ unbounded,continuous and real-time nature and analyzing BloomFilter,we present the estimation strategy of the number of distinct values over data streams based on circular BloomFiher.We store the distinct values over data streams in circular BloomFiher to solve effectively the problem that the distinct values over data streams can not be stored in bounded memory.Compared with the existing estimation algorithms,the experiments show that the estimation strategy based on circular BloomFiher is feasible and highly effective.

关 键 词：BLOOMFILTER 数据流 不同值个数 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]