电子学报2012，Vol.40Issue(9)：1852-1857,6.DOI:10.3969/j.issn.0372-2112.2012.09.023
几何布鲁姆过滤器的设计与分析
Geometric Bloom Filter Designing and Its Analysis
摘要
Abstract
Considering the poor storage and query performances of naive 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分类
信息技术与安全科学引用本文复制引用
张震,汪斌强,陈庶樵,郭通..几何布鲁姆过滤器的设计与分析[J].电子学报,2012,40(9):1852-1857,6.基金项目
国家重点基础研究发展规划(973计划)项目(No.2012CB312901,No.2012CB312905) （973计划）
国家高技术研究发展计划(863计划)课题(No.2011AA01A103) （863计划）
