Bloom Filters如何帮助确定URL是否已经爬行？

Question

我不断听到Bloom Filter在web爬行中是如何有用的，特别是在确定URL是否已经被爬行时(因为Bloom Filter在测试集成员资格时是内存高效的)。

然而，在web爬行的用例中，如果遇到几乎无限数量的URL，那么位/桶的数量不是需要很多吗？尤其是，如果你是Google或一个搜索引擎，每天都在试图抓取数据。

所以我的问题是，当URL的数量不断增加，而存储桶的数量保持不变时，Bloom过滤器如何帮助确定URL是否已经被爬取？

Answer 1

布隆过滤器基于哈希函数，它会产生有限范围的值。无论遇到多少个URL，每个函数都将返回其范围内的一个值。使用多个散列函数来选择比特可以减少误报的可能性，但这始终是一种可能性。然而，它的概率很小，并且是准确性和效率之间经过计算的折衷。

网址的长度是有实际限制的，参见this question。诚然，这是一个惊人的数字。当创建更多URL时，可能需要升级哈希函数和存储桶大小，但目前可用的这些功能完全能够应对当前可用的URL，错误率可接受的很小。

Answer 2

对于这个用例，除非有大量的存储桶，否则你会遇到很大比例的误报(无论如何都不可能完全消除误报，即使对于一个小的应用程序也是如此)。

一个有趣的解决办法是拥有多级布隆过滤器而不是平面结构，例如，第一层仅基于域名(如cnn.com)，下一层可能包含扩展的urls (如cnn.com/sports/athletics)。但是当涉及到字符串操作和多个哈希函数时，不确定这将执行得有多好。