如何通过引入其他数据结构来提高布隆过滤器的准确性？

Question

假设我有一个非常大的数据集（例如，10 亿个密钥），并且我想确定某个特定密钥是否在此数据集中。在这种情况下，布隆过滤器是一个不错的选择（时间复杂度为 O(k)，内存使用量相对易于管理）。然而，布隆过滤器的一个问题是可能出现误报，这意味着它可能会错误地指示集合中不存在某个键。我的问题是，是否可以牺牲一些时间复杂度和相对较小的内存使用量，以确保在检查集合中是否存在某个键时，结果不会误报。

例如，我想到的一种粗略方法是将数据集跨多个文件存储在磁盘上。在检查密钥时，我可以逐个加载每个文件块，然后检查密钥是否存在。由于每个文件块不会太大，因此内存使用量将保持在可管理的范围内。

Answer 1

只有一个选择：您可以将布隆过滤器本身缩放到误报概率与其他背景问题具有相同数量级的程度（例如您的计算机硬件自行故障或由于某些事故） /事件 - 或电力供应，或者你今天因任何原因而死亡）。

使用来自 https://en.wikipedia.org/wiki/Bloom_filter

的概率公式

pow(1 - pow(e, -k*n/m), k)

k = 使用的哈希函数的数量，维基百科说 (m / n) ln 2 是最佳的

n = 键的数量，m = 布隆过滤器中的位数

在Python中：

import math
def f(n, m):
    k = (m / n) * math.log(2)
    return (1 - math.e ** (-k * n / m)) ** k

你的 n 值是“例如，10 亿个密钥”，假设我们的目标是相当于 40 岁的人今天死亡的概率（来自 https://www.ssa.gov/oact/STATS/table4c6.html 每年 0.002066，因此每天 5.66E-6。

对 f 的几次调用表明我们跨越了概率阈值：

>>> f(1E9, 3E10)
5.498664438639185e-07
>>> f(1E9, 2E10)
6.711786678855935e-05

因此，3E10 位 = 1E9 密钥的 3.5GB 布隆过滤器，这对于大多数现代工作服务器来说是相当合理的，因为这些服务器可能需要处理这么多密钥和相关数据。 不过，概率下降得很快 - 例如f(1E9, 4E10) ~= 4.5E-9 - 因此您获得 1/3 额外内存的风险为 1/100。

另一个阈值 - 今天人类被小行星消灭：“根据月球陨石坑历史和 NEA 观测，未来十亿年发生巨大撞击的概率在 0.03 到 0.3 之间。” - 0.03 / 1E9 / 365 ~= 8.2E-14，很有趣，因为过滤器误报呈对数减少，我们可以通过以下方式得到很好的结果f(1E9, 7E10) ~= 2.5E-15，仍然只使用8.15GB数据。