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

作     者：张震 汪斌强 陈庶樵 郭通 ZHANG Zhen;WANG Bin-qiang;CHEN Shu-qiao;GUO Tong

作者机构：国家数字交换系统工程技术研究中心河南郑州450002 

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

出 版 物：《电子学报》 (Acta Electronica Sinica)

年 卷 期：2012年第40卷第9期

页      码：1852-1857页

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

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

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 08[工学] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3969/j.issn.0372-2112.2012.09.023

馆 藏 号：203427104...