Bloom Filter研究进展  

Survey of Bloom Filter

作　　者：严华云[1,2] 关佶红[2] 

机构地区：[1]湖州师范学院信息与工程学院,湖州313000 [2]同济大学电子与信息工程学院,上海201804

出　　处：《电信科学》2010年第2期31-36,共6页Telecommunications Science

基　　金：国家自然科学基金资助项目(No.60573183;No.60872057;No.60803053);浙江省自然科学基金杰出青年团队项目(No.R1090244);浙江省自然科学基金资助项目(No.Y107293;No.Y1080212);浙江省科技计划项目(No.2008C21083);湖州市科技攻关项目(No.2008GG11)

摘　　要：近年来,由于Bloom filter具有可压缩性和高效查询性,其在分布式数据库、网络缓存、对等网和信息检索等领域引起了越来越多的研究者关注。随着Bloom filter不同应用需求的出现,多种Bloom filter变体被提了出来,诸如:支持删除元素的CBF;可以统计频次型的SBF、DCF、dlCBF;大小可以动态伸长的DBF、SBF;压缩型BF等。本文对Bloom filter及其各种变体进行了介绍,并对其特点进行了分析比较,总结了它们各自的优势和不足,并进一步指出了Bloom filter未来的一些研究方向。In recent years, the communication community has witnessed a growing interest in Bloom filter which including two characters of compressibility and efficient query, mainly due to the awareness of its importance in many applications involving distributed database, Intemet cache, peer-to-peer, and information retrieval etc. Several variants of Bloom filter was presented as the requirement of application, such as： CBF, which support deleting elements operations; SBF,DCF,dlCBF, which support counting the frequency of elements; DBF,SBF, which can extend the length of Bloom filter; CBF, which can compress the Bloom filter. This paper introduces all the variations, analyzes their characteristics and compares them with each other. Finally, outlines the directions for future research.

关 键 词：计算机网络 分布式计算 BLOOM FILTER 

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