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

Geometric Bloom Filter Designing and Its Analysis

作　　者：张震[1] 汪斌强[1] 陈庶樵[1] 郭通[1] 

机构地区：[1]国家数字交换系统工程技术研究中心,河南郑州450002

出　　处：《电子学报》2012年第9期1852-1857,共6页Acta Electronica Sinica

基　　金：国家重点基础研究发展规划(973计划)项目(No.2012CB312901;No.2012CB312905);国家高技术研究发展计划(863计划)课题(No.2011AA01A103)

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

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]