Bloom滤波器中正匹配的结果

Question

假设：

• 注册用户的用户名存储在一组
• 中，我想使用Bloom筛选器使查找速度更快。
• The Bloom filter作为一定的误报概率(0.1%)

当一个新用户想注册时，在大多数情况下，我的UI告诉他们“这个名字不被使用，你可以去”。

，但是如果找到正匹配，后端需要做什么呢？

结果可能是假阳性。找出真正的答案不会增加时间复杂性，从而使Bloom过滤器在许多情况下效率低下吗？

告诉用户“使用中的名称，选择不同的oe”可能不是那么糟糕，但是对于其他不能出错的用例呢？

Answer 1

使用Bloom过滤器的一般模型如下：

如果determination.过滤器说不，答案肯定是否定的。如果过滤器说是，答案可能是是，所以查询一个更准确的数据结构来得到最终的

1. 。

当步骤(3)的形式为“查询某个服务器以搜索一个巨大的数据库以查看您是否有问题的项目”时，Bloom过滤器就会非常出色。在这种情况下，减少服务器需要点击以进行判断的次数可以在客户机上带来巨大的性能提升，并减少服务器上的负载。

另一方面，如果您在机器上本地存储一个小数据集，那么Bloom过滤器不太可能做那么多工作，因为直接查询数据集可能足够快，满足您的所有需要。

Answer 2

只在要检测传入单词是否已存在于数据库中时，才会使用Bloomfilter。

若要成为特定的bloomfilter输出，请选择

• 是的--这意味着在我们的数据库
• No中可能存在也可能不存在--这意味着100 %肯定该单词不存在

此外，假阳性不应损害您的情况，但是，如果您真的担心，花过滤器的错误率是由公式：

错误率= 1-(1-(1/m))^(k*i)^k

其中我是当前插入的数目，也就是说，如果要在i=20筛选器中插入20字，那么hash k是散列函数的数目m是位数组的大小。

因此，您可以继续并尽量减少它，以满足您的需要。

此外，本文还给出了所使用的哈希函数的最佳数目。

k=(m/n)log 2

其中n是要插入的单词总数。因此，您可以相应地选择散列函数的数量。