Bloom搜索过滤器的优化设计与实现

《Bloom搜索过滤器的优化设计与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第35卷V01．35第7期I、『D．7计算机工程ComputerEngineering2009年4月April2009·开发研究与设计技术·文章编号，loo岫428(2∞9J07珈2罅棚3文献标识码tA中圈分类号。TP391Bloom搜索过滤器的优化设计与实现高家利1，廖晓嶂2(1．重庆工学院工程训练中心，重庆400054；2．重庆大学计算机学院，重庆400044)捕耍：基于Bloom搜索过滤器的搜索过滤机制会发生误判，且在查询目标进入过滤器后，查询整个关键字的步骤会耗费太多成本。该文提出一套新的搜索过滤器架构。经实验验证，该过滤器能减少误判率的发生，降低

2、整个过滤器的搜索成本，提高搜索过滤器的整体性能。关蝴：Bloom搜索过滤器；关键字集合；误判；查表目录OptimizedDesignandImplementationofBloomFilterGAOJia-lil．LIAOXiao-fen矿(1．EngineeringTrainingCenter,ChongqingInstituteofTechnology,Chongqing400054；2．ComputerCollege，ChongqingUniversity,Chongqing400044)[Abst耐!Bloomfilterbasedfilteringmec

3、hanismshaveonemajordrawback，thatis，afteraqueryitempassesthroughthefilter,theentirekeysethastobesearchedeverforfalsepositives．Thesearchcostisthereforeboundtobehigherthannecessary．ThispaperdevelopesanewsearchfilterwhichCalllowerthepossiblyoffalsepositives，andsignificantlyreducetheoveral

4、lsearchcost，sincealargeamountofunnecessarysearchoperationscanbeavoided．[KeywordsIBloomfilter；keyset；falsepositive；lookuptableBloom搜索过滤器使用的核心方法是哈希编码，其特点是能够利用少量的储存空间存放关键字集合，利用哈希函数的转换求得所要搜索的对象‘卜引。由于使用了较少的储存空间，无法避免误判(falsepositive)的情况，而误判率的高低会影响搜索过滤器的搜索成本，因此如何减少误判率并且降低搜索成本是蘑要的课题Hj。本文以Bloo

5、m搜索过滤器为基础提出一个新的搜索过滤器。l改进的Bloom搜索过滤器1．1Bloom搜索过滤器算法15面l考虑到一个拥有_r1个元素的关键字集合A={口l，a2，⋯，a。l，BloomFilter使用一含有m个一位元(bits)元数的向量y来描述A集合的成员信息，并以k个哈希卤数hhh2，⋯，ht来做运算，其中，hi：n{1。2，⋯，ml。PhaseI建立过滤器ProcedureBloomFilter(setA，hash_functions．integerm，V)returnsfilterInitializeVto0(mbits)ForeachaiinA：For

6、eachhashfunctionhi：VIhi(aj)l=IEndforeachEudforeachReturnfilterPhasel以哈希函数hl，h2，⋯，k建立一个对应到关键字集合A且包含m个一位元元数的向量V。如果af是集合A的成员之一，则BloomFilter执行后相对应的V元素应该全部设为l。Phase2关键字比对阶段ProcedureMembershipTest(elm，filter,hash—functions，V)—吧64一retumsYes／NoForeachhashfunctionhj：IfV【hj(elm)】l-lreturnsNoEnd

7、foreachreturnsYesPhase2测试elm是否为关键字集合A的成员之一。测试值elm进入搜索过滤器做检验，如果elm的特征值不符合则回传No，表示elm不属于这个关键字集合。如果符合则回传Yes，然后进入存取阶段继续做搜索，直到找到符合的值为止，如果没有找到则表示这是一个误判。1．2改进的算诸本文提出的新算法以Bloom搜索过滤器为基础，在比对步骤中以关键字的特征来建立一个查表目录，此查表目录以每个关键字特征的最小值来做归纳区分，当误判发生时，只须以其关键字最小值所分配的位置做查询并判别是否正确，能减少搜索时间与成本，并且提高搜索过滤器的整体性能。算

8、法步骤说明