Bloom Filter研究进展

doi:10.3969/j.issn.1000-0801.2010.02.011

Abstract

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

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

Figures/Tables 4

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

Metrics

Recommended 0

No Suggested Reading articles found!

每个元素的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]	Ping XIE,Xiaosong LIU. Security of the deployment of SDN-based IoT using blockchain [J]. Telecommunications Science, 2020, 36(12): 139-146.
[2]	Teng MA,Yuxiang HU. Fast and live virtual machine migration in data center networks [J]. Telecommunications Science, 2017, 33(6): 64-72.
[3]	Jianxin Ren,Huahui Chen. An Adaptive Subspace Similarity Search Approach [J]. Telecommunications Science, 2015, 31(7): 63-74.
[4]	Jie Zheng,Sheng Bao,Ying Yang. Application of Distributed Parallel Computing in Super-Resolution Image Enbancement [J]. Telecommunications Science, 2015, 31(4): 37-42.
[5]	Dagang Guo,Mingqin Zhuo,Jirong Zhang. Research of Resources Search Mechanism on Hybrid Stream Media System [J]. Telecommunications Science, 2014, 30(2): 33-39.
[6]	Jie Liu,Zhe Wang. Construction of Carrier Business Precise Operating Platform Basedon Big Data [J]. Telecommunications Science, 2013, 29(3): 22-26.
[7]	Julong Lan,Dongnian Cheng,Yu Wang,Fengyu Zhang. Initial Analysis on Intelligence Mechanisms of Reconfigurable Network Abstract Flexibility,with which a reconfigurable network adaptively tunes its structure,plays a critical role in accommodating varieties of applications with desirable service levels.Most studies avalaible,however,rarely provide clear answers about the mechanism of flexibility that supports network reconfigurations.For the mechanism more clear,this paper clarifies a key target of the consistant matching of service outcomes to application demands.What is then revealed includes the kernal characteristic,so-called outcome following demand with gardually tuning,of the reconfiguration flexibility.Furthermore,four inherent schemes and frameworks representing reconfiguration flexibility are respectively examined in depth.They are the knowledeg-driven architecture of network functionalities,cross-layer interactions of functionalities,distributed and collaborative sensing,and distributed intelligece.Finally,the method of ant conoly optimization（ACO）is emphasized by explaining its effectiveness in optimizing non-linear problems such as performence-constrained routing at small time scales.Specifically,both the advantage and significance of emergence,the prominent feature of ACO,are illustrated. [J]. Telecommunications Science, 2012, 28(8): 105-112.
[8]	Jianfeng Wen,Yirong Shi. Research on Basing Distributed Computing Framework to Achieve Accelerating the Data Analysis Application of Telecommunications [J]. Telecommunications Science, 2012, 28(2): 22-26.

Survey of Bloom Filter

RichHTML

PDF下载

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 4

References 35

Related Articles 8

Metrics

Recommended 0