Bob*_*r02 17 algorithm bloom-filter data-structures
我正在努力理解布隆过滤器的用处.我得到了它的基础逻辑,空间压缩,快速查找,误报等.我只是不能将这个概念置于现实生活中,因为它是有益的.一个常见的应用是在Web缓存中使用bloom过滤器.我们使用bloom过滤器来确定给定的URL是否在缓存中.为什么我们不直接访问缓存来确定？如果我们得到肯定的话,我们仍然需要去缓存来检索网页(可能不存在),但是如果没有,我们可以使用缓存得到相同的答案(这可能是为了快速查找而优化的)无论如何？).
tem*_*def 31
Bloom过滤器适用于假阴性是非常糟糕的情况并且可以接受假阳性的情况.
例如,假设您正在制作Web浏览器并拥有已知的诈骗网站黑名单.你的黑名单很庞大 - 数百GB - 所以你不能用浏览器发送它.但是,您可以将其存储在自己的服务器上.在这种情况下,您可以使用适当大小的Bloom过滤器运送浏览器,该过滤器包含所有URL.在访问网站之前,您可以在过滤器中查找它.然后,如果您收到"否"回答,则可以保证该URL不会被列入黑名单,只能访问该网站.如果您得到"是"答案,该网站可能是邪恶的,因此您可以让浏览器调用您的主服务器以获得真正的答案.您可以在不牺牲准确性的情况下将大量呼叫保存到服务器这一事实非常重要.
缓存的想法与此设置类似.您可以查询过滤器以查看该页面是否在缓存中.如果你得到一个"否"的答案,你可以保证它没有被缓存,并且可以通过昂贵的操作从主源获取数据.否则,您可以检查缓存以确定它是否真的存在.在极少数情况下,您可能需要检查缓存,看看它不存在,然后从主源获取,但您永远不会意外遗漏缓存中的某些内容.
希望这可以帮助!
当满足以下两个条件时，布隆过滤器可能会很有用：
第一点非常简单。当布隆过滤器可以存储在主内存中但实际查找可能需要数据库命中时，第二点通常变得很重要，这相对于对键执行一定数量的哈希然后进行内存中查找（即，布隆过滤器）。
如果仅满足上述标准之一，那么布隆过滤器并不是解决问题的最佳方案。
当人们可以消除昂贵的查找时，就会节省成本，因为知道不可能获得匹配。这是第一点的值 - 布隆过滤器不会生成漏报，因此如果在过滤器中未找到匹配项，则没有必要执行下一个成本更高的步骤来检索与密钥关联的数据。
当过滤器命中时，需要进行昂贵的查找来验证命中（消除误报）并检索相关数据。这里有可能由于误报而找不到任何东西，这就是为什么需要调整过滤器以将这种风险降至可接受的水平。功能齐全的布隆过滤器必须具有较低的误报率，以便总体查找成本保持较低。
现在，如果正如您所说，您的缓存已经针对快速查找进行了优化，那么布隆过滤器的实用性可能会受到质疑。