Geometric Bloom Filter Designing and Its Analysis

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

doi:10.3969/j.issn.0372-2112.2012.09.023

您当前的位置：

首页 >

文章列表页 >

Geometric Bloom Filter Designing and Its Analysis

更新时间：2025-07-16

- Geometric Bloom Filter Designing and Its Analysis
- Acta Electronica Sinica Vol. 40, Issue 9, Pages: 1852-1857(2012)
- 作者机构：
  
  国家数字交换系统工程技术研究中心,河南,郑州,450002
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2012.09.023
  CLC： TP393
- Published：2012
- 稿件说明：
移动端阅览
ZHANG Zhen, WANG Bin-qiang, CHEN Shu-qiao, et al. Geometric Bloom Filter Designing and Its Analysis[J]. Acta Electronica Sinica, 2012, 40(9): 1852-1857.
DOI：

ZHANG Zhen, WANG Bin-qiang, CHEN Shu-qiao, et al. Geometric Bloom Filter Designing and Its Analysis[J]. Acta Electronica Sinica, 2012, 40(9): 1852-1857. DOI： 10.3969/j.issn.0372-2112.2012.09.023.

摘要

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

关键词

Keywords

references

Views

1345

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Fast URL Lookup Using Parallel Bloom Filters

Related Author

ZHOU Zhou

FU Wen-liang

SONG Tian

LIU Qing-yun

Related Institution

National Engineering Laboratory for Information Security Technologies Institute of Information Engineering, Chinese Academy of Sciences

School of Computer Science, Beijing Institute Engineering, Chinese Acadenmy of Sciences

National Engineering Laboratory for Information Security Technologies Institute of Information Engineering Chinese Academy of Sciences Beijing China

School of Computer Science Beijing Institute Engineering Chinese Acadenmy of Sciences Beijing China

⁰