Bloom Filter和Weighted Bloom Filte的比较和研究

摘要

随着Internet技术和WWW服务的发展，Web网络流量的增加和网页访问的延迟日益引起人们的关注，这两个问题影响了Internet的持续发展。网络缓存技术是解决这两个问题的一种至关重要的技术，在国际上已经形成一个独立的主流研究领域，并取得了一些研究成果。网络缓存技术是一个复杂的课题，它需要解决替换策略、一致性维护、缓存共享和性能评价等诸多问题。虽然目前已经在这些方面做了很多工作，但许多问题并没有得到圆满解决，影响了网络缓存技术在WWW服务上的应用。本文的内容属于缓存共享领域。利用Bloomfilter表示共享信息的内容，大大地降低了用于存储索引的空间消耗，减少了访问延迟。Bloomfilter是一个简明的空间效率极高的随机的数据结构，用于判别一个元素是否属于某个集合。用Bloomfilter表示cache内容，可以高效地实现cache协作。因为在代理之间只需传输Bloomfilter而不是完整的cache目录表。本文首先介绍了Bloomfilter的研究和应用现状，然后，从数学角度对Bloomfilter和WeightedBloomfilter进行比较。

目录

摘要

Abstract

第1章 引言

第2章 Bloom filter和Weighted Bloom filter

第3章 模拟方案及实现

第4章 有待进一步研究的问题

结论

参考文献

致谢