bloom filter和weighted bloom filte的比较和研究

《bloom filter和weighted bloom filte的比较和研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、太原理工大学硕士学位论文BloomFilter和WeightedBloomFilte的比较和研究姓名：池静申请学位级别：硕士专业：计算机应用技术指导教师：牛保宁20030101摘要BloomFilter和WeightedBloomFilter的比较和研究摘要随着Internet技术和www服务的发展，Web网络流量的增加和网页访问的延迟曰益引起人们的关注，这两个问题影响了Internet的持续发展。网络缓存技术是解决这两个问题的--7十至关重要的技术，在国际上已经形成一个独立的主流研究领域，并取得了一些研究成果。网

2、络缓存技术是一个复杂的课题，它需要解决替换策略、一致性维护、缓存共享和性能评价等诸多问题。虽然目前已经在这些方面做了很多工作，但许多问题并没有得到圆满解决，影响了网络缓存技术在www服务上的应用。本文的内容属于缓存共享领域。利用Bloomfilter表示共享信息的内容，大大地降低了用于存储索引的空间消耗，减少了访问延迟。Bloomfilter是一个简明的空间效率极高的随机的数据结构，用于判别一个元素是否属于某个集合。用Bloomfilter表示cache内容，可以高效地实现cache协作。因为在代理之间只需传输Bl

3、oomfilter而不是完整的cache目录表。本文首先介绍了Bloomfilter的研究和应用现状，然后，从数学角度对Bloomfilter和WeightedBloomfilter进行比较。结果证明WeightedBloomfilter有较低的错误预测。但是，模拟结果显示，Bloomfilter有较低的错误预测，比WeightedBloomfilter好。主要原因是WeightedBloomfilter需要很强的条件，而这些条件在现实中不能被满足。太原理工大学工学硕士学位论文本文最后指出Bloomfilter应用

4、中存在问题和进一步研究的方向和措施。关键词：网络缓存；代理缓存；缓存共享；Bloomfilter：错误命中2摘要BloomFiltervsWeightedBloomFilterAbstractWiththedevelopmentofInternettechnologiesandWWWservices，moreandmoreattentionispaidtotheWebtrafficandpageaccessdelay，whicharethekeyissuesaffectingthecontinuousgrowing

5、ofInternetProxyCache，aneffectivetechniquetosolvetheseissues，isahotresearcharea．SomeresearchworkshavebeenconductedonthisareaandresultinsomefruitsResearchonProxyCacheisquietcomplicatedbecausetherearealotofproblemssuchasreplacementstrategy，cacheconsistency，caches

6、haringandperformanceanalysisThoughstudyingofProxyCachehasbeenmadeofyears，fewoftheseproblemshavebeensolvedsuccessfully．Thisthesis，concentratesontopicofcache．ThecontentsofsharedmessagearerepresentedbyBloomfilter．Thistechniquegreatlyreducesthespaceneededforpagein

7、dexinganddecreasetheaccessdelay．ABloomfilterisasimplespace—efficientrandomizeddatastructureforrepresentingasetinordertodetermineacertainelementintheset．WeightedBloomfiltersandcountingBloomfiltershavebeensuggestedasnleansforsharingWebcacheinformation．Bloomfilte

8、rsaretransmittedamongsharedproxiesinsteadofsendingthefulllistofcachecontents．Inthisthesis，asummaryaboutthecurrentresearchandapplicationon刁太原理上人学工学硕士学位论文Bloomfilterispresented，andth