Bloom Filter研究进展

doi:10.3969/j.issn.1000-0801.2010.02.011

摘要/Abstract

摘要：

近年来，由于Bloom filter具有可压缩性和高效查询性，其在分布式数据库、网络缓存、对等网和信息检索等领域引起了越来越多的研究者关注。随着Bloom filter不同应用需求的出现，多种Bloom filter变体被提了出来，诸如：支持删除元素的CBF；可以统计频次型的SBF、DCF、dlCBF；大小可以动态伸长的DBF、SBF；压缩型BF等。本文对Bloom filter及其各种变体进行了介绍，并对其特点进行了分析比较，总结了它们各自的优势和不足，并进一步指出了Bloom filter未来的一些研究方向。

关键词: 分布式计算, Bloomfilter, 计算机网络

Abstract:

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,Internet 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.

Key words: computer Internet, distributed computing, bloom filter

严华云,关佶红. Bloom Filter研究进展[J]. 电信科学, 2010, 26(2): 31-36.

Huayun Yan,Jihong Guan. Survey of Bloom Filter[J]. Telecommunications Science, 2010, 26(2): 31-36.

图/表 4

参考文献 35

1	Bloom B H . Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 1970,13（7）: 422～426
2	Mcilroy M D . Development of a spelling list. IEEE Transactions on Communications, 1982,30（1）: 91～99
3	Valdurez P , Gardarin G . Join and semijoin algorithms for a multiprocessor database machine. ACM Transactions on Database Systems, 1984,9（1）: 133～161
4	Mackett L F , Lohman G M . Roptimizer validation and performance evaluation for distributed queries.In: Proc of the VLDB, Kyoto,Japan, August 1986
5	Mullin J K . Optimal semijoins for distributed database systems. IEEE Transactions on Software Engineering, 1990,16（5）: 558～560
6	Fan L , Cao P , Almeida J ,et al. Summary cache:a scalable wide-area Web cache sharing protocol. ACM Transactions on Networking, 2000,8（3）: 281～293
7	Reynolds P , Vahdat A , Efficient peer-to-peer keyword searching.In: Proc of Middleware,Riode Janeiro,Brazil, June 2003
8	Chen H H , Jin H , Wang J L ,et al. Efficient multi-keyword search over P2P web.In: Proc of the WWW, Beijing,China, April 2008
9	肖明忠，代亚非． Bloom Filter 及其应用综述．计算机科学， 2004,31（4）: 180～183
10	Broder A , Mitzenmacher M . Network applications of bloom filters:a survey. Internet Mathematics, 2005,1（4）: 485～509
11	谢鲲，文吉刚，张大方等．布鲁姆过滤器查询算法．软件学报， 2009,20（1）: 96～108
12	Bonomi F , Mitzenmacher M , Panigrahy R ,et al. An improved construction for counting bloom filters.In: Lecture Notes in Computer Science, Zurich,Switzerland, September 2006
13	Ficara D , Giordano S , Procissi G . MultiLayer compressed counting bloom filters.In: Proc of the Infocom, Phoenix,AZ,USA, April 2008
14	Saar C , Yossi M . Spectral bloom filters.In: Proc of the SIGMOD, San Diego,USA, June 2003
15	Aguilar-Saborit J , Trancoso P , Muntes-Mulero V . Dynamic count filters.In: Proc of the SIGMOD,Chicago, Chicago,USA, June 2006
16	肖明忠，代亚非，李晓明 . 拆分型Bloom Filter．电子学报， 2004,32（2）: 241～245
17	Guo D , Wu J , Chen H ,et al. Theory and network applications of dynamic bloom filters.In: Proc of the Infocom,Barcelona, Spain, April 2006
18	Almeida P S , Baquero C , Preguica N . Scalable bloom filters. Information Processing Letters, 2007,101（6）: 255～261
19	Hao F , Kodialam M , Lakshman T V . Incremental bloom filters.In: Proc of the Infocom, Phoenix,AZ,USA, April 2008
20	Mitzenmacher M . Compressed bloom filters. ACM Transactions on Networking, 2002,10（5）: 604～612
21	Mullin J K . Optimal semijoins for distributed database systems. IEEE Transactions on Software Engineering, 1990,16（5）: 558～560
22	Udi M , Sun W . An algorithm for approximate membership checking with application to password security. Information Processing Letters, 1994,50（4）: 191～197
23	Gremillion L L . Designing a bloom filter for differential file access. Communications of the ACM, 1982,25（9）: 600～604
24	James K M . A second look at bloom filters. Communications of the ACM, 1983,26（8）: 570～571
25	Ahmed R , Boutaba R . Plexus: a scalable peer-to-peer protocol enabling efficient subset search. ACM Transactions on Networking, 2009,17（1）: 130～143
26	张一鸣，卢锡城，郑倩冰等．一种面向大规模P2P系统的快速搜索算法．软件学报， 2008,19（6）: 1473～1480
27	Yu H , Mahapatra R N . A memory-efficient hashing by multi-predicate bloom filters for packet classification.In: Proc of the Infocom, Phoenix,AZ,USA, April 2008
28	Kumar A , Xu J , Wang J , Spatschek O , et al. SpaceScode bloom filter for efficient persflow traffic measurement.In: Proc of IEEE Infocom, Hongkong, March 2004
29	叶明江，崔勇，徐恪等．基于有状态Bloom filter引擎的高速分组检测．软件学报， 2007,18（1）: 117～126
30	Yu H , Mahapatra R N . A memory-efficient hashing by multipredicate bloom filters for packet classification.In: Proc of Infocom,Phoenix, AZ,USA, April 2008
31	Sarang D , Haoyu S , Jonathan T , et al. Fast packet classification using bloom filters.In: Proc of the 2006 ACM/IEEE Symp Architecture for Networking and Communications Systems, 2006
32	Heeyeol Y , Mahapatra R . A memory-efficient hashing by multi-predicate bloom filters for packet classification.In: Proc of the Infocom, Phoenix,AZ,USA, April 2008
33	Locasto M E , Parekh J J , Keromytis A D , et al. Towards collaborative security and P2P intrusion detection.In: Proc of SMC 2005, NY,USA, June 2005
34	Hebden P , Pearce A R . Data-centric routing using bloom filters in wireless sensor networks.In: Proc of ICISIP 2006, Bangalore,India, December 2006
35	Bloomfilter, .

每个元素的BF向量位数m/n	8	10	14	92
每个元素传送位数z/n	8	8	8	8
哈希函数个数k	6	3	2	1
错误率f_p	0.0216	0.0199	0.0177	0.0108

[1]	谢萍,刘孝颂. 基于区块链的SDN物联网部署安全[J]. 电信科学, 2020, 36(12): 139-146.
[2]	王源,江昊,吴明,姚冬桂,张毅,羿舒文,汪海,吴静. 基于用户移动网络接入位置的高效分布式相似矩阵计算方法[J]. 电信科学, 2018, 34(5): 26-38.
[3]	任建新,陈华辉. 一种自适应子空间相似性搜索方法[J]. 电信科学, 2015, 31(7): 63-74.
[4]	郑杰,包盛,杨萤. 分布式并行计算在超分辨率图像增强中的应用[J]. 电信科学, 2015, 31(4): 37-42.
[5]	黄万伟,汪斌强,王志明,袁博. 可重构柔性网络架构与节能机制研究[J]. 电信科学, 2013, 29(9): 1-7.
[6]	刘保健,黄杰,王宝生,张潇晓. 骨干网冗余数据消除系统的研究与实现[J]. 电信科学, 2013, 29(9): 8-13.
[7]	刘洁,王哲. 基于大数据的电信运营商业务精确运营平台的构建[J]. 电信科学, 2013, 29(3): 22-26.
[8]	兰巨龙,程东年,王雨,张风雨. 网络柔性重构的智能机理浅析[J]. 电信科学, 2012, 28(8): 105-112.
[9]	闻剑峰,石屹嵘. 以分布式计算实现电信数据分析业务加速的研究[J]. 电信科学, 2012, 28(2): 22-26.