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

数据流是连续的、实时的无限数据,到目前为止还没有有效的方法将数据流存储起来,因此数据流上的不同值个数的估计也就成为一个比较难的研究课题。文章在对BloomFilter进行分析研究的基础上,结合数据流无限、连续、实时等特点,提出了基于循环BloomFilter的数据流上不同值个数的估计策略。将数据流中的不同值存储在循环BloomFilter中,有效地解决了在内存有限情况下,无法保存数据流中的不同值的问题。通过与现有的估计算法的比较,实验结果表明基于循环BloomFilter的估计策略是可行和有效的。

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

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 BloomFilter.We store the distinct values over data streams in circular BloomFilter 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 BloomFilter is feasible and highly effective.