电子学报
電子學報
전자학보
ACTA ELECTRONICA SINICA
2012年
9期
1852-1857
,共6页
张震%汪斌强%陈庶樵%郭通
張震%汪斌彊%陳庶樵%郭通
장진%왕빈강%진서초%곽통
布鲁姆过滤器%几何布鲁姆过滤器%概要数据结构
佈魯姆過濾器%幾何佈魯姆過濾器%概要數據結構
포로모과려기%궤하포로모과려기%개요수거결구
针对经典计数型布鲁姆过滤器( NCBF)存储和查询性能较低的缺陷,提出了几何布鲁姆过滤器结构GBF.该结构通过引入“哈希指纹”、布鲁姆过滤器两次分割、基于桶负载存放的方法,实现了集合元素的简洁存储、快速查询.基于“微分方程”和“概率论”的相关知识,对GBF模型进行了理论分析和求解,建立了错误概率和计算复杂度的关系表达式,论证了GBF的几何分布特性.仿真结果表明:与NCBF相比,GBF具有较低错误概率和计算复杂度的同时,也能保持较高的空间利用率.
針對經典計數型佈魯姆過濾器( NCBF)存儲和查詢性能較低的缺陷,提齣瞭幾何佈魯姆過濾器結構GBF.該結構通過引入“哈希指紋”、佈魯姆過濾器兩次分割、基于桶負載存放的方法,實現瞭集閤元素的簡潔存儲、快速查詢.基于“微分方程”和“概率論”的相關知識,對GBF模型進行瞭理論分析和求解,建立瞭錯誤概率和計算複雜度的關繫錶達式,論證瞭GBF的幾何分佈特性.倣真結果錶明:與NCBF相比,GBF具有較低錯誤概率和計算複雜度的同時,也能保持較高的空間利用率.
침대경전계수형포로모과려기( NCBF)존저화사순성능교저적결함,제출료궤하포로모과려기결구GBF.해결구통과인입“합희지문”、포로모과려기량차분할、기우통부재존방적방법,실현료집합원소적간길존저、쾌속사순.기우“미분방정”화“개솔론”적상관지식,대GBF모형진행료이론분석화구해,건립료착오개솔화계산복잡도적관계표체식,론증료GBF적궤하분포특성.방진결과표명:여NCBF상비,GBF구유교저착오개솔화계산복잡도적동시,야능보지교고적공간이용솔.
