摘要： Bloom过滤器是一种空间高效但有一定假阳性的数据表示方法。该文分析比较计数型Bloom过滤器、光谱Bloom过滤器和动态计数过滤器的异同点及适用场合，介绍Bloom 过滤器在重复项检测及频繁项挖掘中的应用，总结Bloom过滤器给数据流带来的挑战，包括元素突发问题及数据流相异元素数目变化问题。

关键词: Bloom过滤器, 计数型Bloom过滤器, 光谱Bloom过滤器, 动态计数过滤器, 数据流

Abstract: Bloom Filter(BF) is a space-efficient randomized data structure for representing data set with a small false positive probability. This paper compares and analyzes the similarities and differences among Counting Bloom Filter(CBF), Spectral Bloom Filter(SBF) and Dynamic Counting Filter(DCF), gives some examples and applications in data stream which include duplicate items detecting and frequent items mining. It summarizes the challenges in data stream brought by BF, including element burst problem and number of distinguish element changing problem.

Key words: Bloom Filter(BF), Counting Bloom Filter(CBF), Spectral Bloom Filter(SBF), Dynamic Counting Filter(DCF), data stream

中图分类号: 

• TP311.13