bloom filter改进及其在分布式系统中的应用研究

《bloom filter改进及其在分布式系统中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、南开大学硕士学位论文BloomFilter改进及其在分布式系统中的应用研究姓名：李珺申请学位级别：硕士专业：计算机软件与理论指导教师：刘璟20070501摘要BloomFilter采用一个位向量表示数据集合并且利用Hash函数有效支持查找。它能很好的解决一个问题：判定某个元素是否属于给定集合。在分布式应用环境中，BloomFilter在资源定位、路由查找等各方面都能够得到很好的应用。近年来，针对BloomFilter的基本原理存在多种改进，其中主要包括计数型BloomFilter、压缩型BloomFilter和拆分型BloomFilter。计数型BloomFilter能弥补平凡Blo

2、omFilter的一个缺陷：只能往BloomFilter中增加元素，而不能用于集合中元素的删除；压缩型BloomFilter结合了数据压缩理论，因而在分布式应用中，能有效地降低网络中BloomFilter的数据传输量；而拆分型BloomFilter能较好地缓解分布式环境下集合元素动态增长的问题。经过对BloomFilter及上述改进的分析，本文提出两种新型BloomFilter：一种是K分组合型BloomFilter，和拆分型BloomFilter一样，它针对的也是分布式环境下集合元素动态增长带来的平凡BloomFilter失效问题，本文主要把它与平凡BloomFilter和拆分型B

3、loomFilter作比较并给出指标分析，证明其能在误称率、向量空间和平均判定时间三个指标中得到更好的平衡；第二种改进型BloomFilter是完全组合型BloomFilter，它能完全消除平凡BloomFilter引起的外部冲突，虽然增加了一些空间代价，却比平凡BloomFilter有着更低的误称率，因而能得到更有效的应用。本文还讨论了BloomFilter中使用的hash函数分布概率，给出了一个能对所有分布都进行分析的一般评价指标。最后，讨论了BloomFilter以及本文提出的新改进型BloomFilter的在分布式系统中的一些应用，并针对其在WebCache中的应用给出模拟实

4、验结果并进行分析。关键词：BloomFilter：K分组合型BloomFilter；完全组合型BloomFilter；hash分布AbstracIAbstractUsingavectortopresentadataset，BloomFiltercalleffectivelysupportdatalookingupbyHashfunctions．Itisagoodsolutiontoaproblem：whetheracertainelementbelongstoagivensetornot．IndistributedApplicationEnvironment,BloomFilterw

5、illbeingoodapplicationsuchasresourcessearchingandRouting．Inrecentyears，againsttheordinaryBloomFilter,multipleimprovements，whichwouldincludetheCountingBloomFilter,CompressionBloomFilterandSplitBloomFilter,havebeenintroduced．CountingBloomfiltercansolveadefectofordinaryBloomFilter：BloomFiltercanon

6、lyaddelementsintoaset，andnotforelementsdeleted；Withthecombinationofdatacompressiontheory,soinadistributedapplication，CompressionBloomFiltercanbcveryeffectiveinreducingnetwork’stransmission；andSplitBloomFiltercanbeusedtoalleviatedynamicgrowthofthedatasetinthedistributedenvironment．Basedoutheanal

7、ysisabove，thispaperpresentstwokindsofnewBloomFilter,TheK-combinedBloomFilter,likeSplitBloomFilter,italsoaimsattheproblemofdynamicgrowthinthedistributedenvironment，ComparedwithBloomFilterandSplitBloomFilter,thispaperistogiveindicat