几何布鲁姆过滤器的设计与分析

doi:10.3969/j.issn.0372-2112.2012.09.023

电子学报 ›› 2012, Vol. 40 ›› Issue (9): 1852-1857.DOI: 10.3969/j.issn.0372-2112.2012.09.023

几何布鲁姆过滤器的设计与分析

张震, 汪斌强, 陈庶樵, 郭通

国家数字交换系统工程技术研究中心, 河南郑州 450002

收稿日期:2011-09-14 修回日期:2012-05-07 出版日期:2012-09-25
- 作者简介:
- 张震 男,1985年生于山东省济宁市.现为国家数字交换系统工程技术研究中心博士研究生.主要研究方向为网络测量和网络管理. E-mail:zhangzhenhigh@gmail.com
- 基金资助:
- 国家重点基础研究发展规划 (973计划)项目 (No.2012CB312901,No.2012CB312905); 国家高技术研究发展计划 (863计划)课题 (No.2011AA01A103)

Geometric Bloom Filter Designing and Its Analysis

ZHANG Zhen, WANG Bin-qiang, CHEN Shu-qiao, GUO Tong

National Digital Switching System Engineering & Technological R&D Center, Zhengzhou, Henan 450002, China

Received:2011-09-14 Revised:2012-05-07 Online:2012-09-25 Published:2012-09-25
- Supported by:
- Program of National Program on Key Basic Research Project (973 Program) (No.2012CB312901, No.2012CB312905); Program of National High-tech R&D Program of China (863 Program) (No.2011AA01A103)

摘要/Abstract

摘要： 针对经典计数型布鲁姆过滤器(NCBF)存储和查询性能较低的缺陷,提出了几何布鲁姆过滤器结构GBF.该结构通过引入"哈希指纹"、布鲁姆过滤器两次分割、基于桶负载存放的方法,实现了集合元素的简洁存储、快速查询.基于"微分方程"和"概率论"的相关知识,对GBF模型进行了理论分析和求解,建立了错误概率和计算复杂度的关系表达式,论证了GBF的几何分布特性.仿真结果表明:与NCBF相比,GBF具有较低错误概率和计算复杂度的同时,也能保持较高的空间利用率.

关键词: 布鲁姆过滤器, 几何布鲁姆过滤器, 概要数据结构

Abstract: Considering the poor storage and query performances of nave counting Bloom filter (NCBF),a data structure called geometric Bloom filter (GBF) is presented.In order to achieve space-efficient storage and fast query,the structure introduces the idea of hash fingerprints,partitions Bloom filter twice and stores elements with buckets.Based on theory of differential equation and probability,analytical expressions of GBF are deduced.The relational expressions between error probability and space complexity are also established.Furthermore,the inner characteristic of GBF taking on geometric distribution is proved.Simulated results indicate that GBF can achieve lower error probability and computational complexity without sacrificing accuracy compared with NCBF.

Key words: Bloom filter, geometric Bloom filter, synopsis data structure

中图分类号:

TP393

张震, 汪斌强, 陈庶樵, 郭通. 几何布鲁姆过滤器的设计与分析[J]. 电子学报, 2012, 40(9): 1852-1857.

ZHANG Zhen, WANG Bin-qiang, CHEN Shu-qiao, GUO Tong. Geometric Bloom Filter Designing and Its Analysis[J]. Acta Electronica Sinica, 2012, 40(9): 1852-1857.

参考文献

[1] B Bloom.Space/ time tradeoffs in hash coding with allowable errors [J].Communications of the ACM,1970,13(7):422-426.
[2] Mullin JK.Optimal semi-joins for distributed database systems [J].IEEE Transaction on Software Engineering,1990,16(5):558-560.
[3] Byers J W,et al.Informed content delivery across adaptive overlay networks [J].IEEE/ACM Transactions on Networking,2002,12(5):767-780.
[4] 王洪波,程时端,林宇.高速网络超链接主机检测中的流抽样算法研究[J].电子学报,2008,36(4):809-818. WANG Hongbo,CHENG Shiduan,LIN Yu.On flow sampling for identifying super-connection hosts [J].Acta Electronica Sinica,2008,36(4):809-818.(in Chinese).
[5] Rhea SC,Kubiatowicz J.Probabilistic location and routing. IEEE INFOCOM. California:Berkeley,2002.1248-1257.
[6] Whitaker A,Wetherall D.Forwarding without loops in Icarus. IEEE Open Architectures and Network Programming Proceedings. Washington:University of Washington,2002.63-75.
[7] L Fan,P Cao,J Almeida,A Z Broder.Summary cache:a scalable wide-area web cache sharing protocol [J].IEEE/ACM Transactions on Networking,2000,8(3):281-293.
[8] M Mitzenmacher.Compressed Bloom filters [J].IEEE/ACM Transactions on Networking,2002,10(5):604-612.
[9] Saar C,Yossi M.Spectral Bloom filters. ACM SIGMOD. San Diego:ACM Press,2003.241-252.
[10] Xie K,Ming YH,Zhang DF,Xie GG,Wen JG.Basket Bloom filters for membership queries [J].Chinese Journal of Computers,2007,30(4):597-607.
[11] Flavio B,Michael M,Rina P,Sushil S,George V.An improved construction for counting Bloom filters. Annual European Symposium. Zurich:Springer-Verlag,2006.684-695.
[12] A Broder,M Mitzenmacher.Network applications of Bloom filters:a survey [J].Internet Mathematics,2004,1(4):485-509.
[13] T G Kurtz.Solutions of ordinary differential equations as limits of pure jump Markov processes [J].Journal of Applied Probability,1970,7(1):49-58.
[14] M Mitzenmacher.The Power of Two Choices in Randomized Load Balancing. Berkeley:University of California,1996.
[15] M Mitzenmacher,E Upfal.Probability and Computing:Randomized Algorithm and Probabilistic Analysis [M].Cambridge,U K:Cambridge Univ Press,2005.823-829.

几何布鲁姆过滤器的设计与分析

Geometric Bloom Filter Designing and Its Analysis

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

[1]	周舟, 付文亮, 嵩天, 刘庆云. 一种基于并行Bloom Filter的高速URL查找算法[J]. 电子学报, 2015, 43(9): 1833-1840.
[2]	李玮, 张大方, 黄昆, 谢鲲. 面向大数据处理的高精度多维计数布鲁姆过滤器[J]. 电子学报, 2015, 43(4): 652-657.
[3]	谢鲲;赵姣姣;张大方;毕夏安. 基于计数布鲁姆过滤器的快速多维包分类算法[J]. 电子学报, 2010, 38(5): 1046-1052.