典型Bloom过滤器的研究及其数据流应用  

Research on Typical Bloom Filters and Their Data Stream Applications

作　　者：袁志坚[1] 陈颖文[1] 缪嘉嘉[1] 贾焰[1] 杨树强[1] 

机构地区：[1]国防科技大学计算机学院,长沙410073

出　　处：《计算机工程》2009年第7期5-7,共3页Computer Engineering

基　　金：国家"863"计划基金资助项目(2006AA01Z451;2007AA01Z474;2007AA010502);国家部委预研基金资助项目

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

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

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