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

• 学术论文 • 上一篇    下一篇

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

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

  1. 国家数字交换系统工程技术研究中心, 河南郑州 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   

  1. 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)

摘要: 针对经典计数型布鲁姆过滤器(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

中图分类号: