布隆过滤器的替代方案

Question

我尝试过使用布隆过滤器来执行成员资格测试。我希望对 800 亿个条目执行成员资格测试，只允许发生大约 100 次冲突，即只有 100 个条目可以给出误报结果。

我知道这可以通过布隆过滤器来实现，但使用确定每个条目所需的位数以及给定允许的误报率的哈希函数数量的公式。我认为我最终会使用 270 GB 内存和 19 个哈希函数。

我还查看了 Cuckoo 过滤器，但它的内存要求与我的要求不符。我的要求如下：

1. 每个元素最多使用 6 位
2. 使用不超过 7-8 个哈希函数。

除了上面提到的之外，有人可以建议我使用一种概率数据结构来帮助实现我的要求吗？

Answer 1

哈希函数数量的问题并不是真正的问题 - 只需选择一个具有许多输出位的哈希函数并将这些位分开，就好像它们来自单独的哈希函数一样。这里真正的问题是误报率与存储空间的权衡。

\n\n

你说过

\n\n

\n

我希望对 800 亿个条目执行成员资格测试，只允许发生大约 100 次冲突，即只有 100 个条目可以给出误报结果。

\n

\n\n

根据定义，地图中的条目不会是误报。它们是真正的积极因素。

\n\n

接下来的问题是“您打算测试多少个条目，\n出现了 100 个误报？” 奇怪的是，如果答案也是 800 亿，那么您要求的误报率约为 100/80,000,000,000 = 1/800,000,000，小于 2^-29。

\n\n

任何近似成员数据结构（如布隆过滤器或布谷鸟过滤器）的最小空间为 n lg 1/\xce\xb5 位，其中 n 是结构中的元素数量，lg 是对数以 2 为底，\xce\xb5 是误报率。换句话说，每个元素需要超过 29 位才能达到每 800 亿个 100 个这样的误报率。每个元素 6 位最多只能得到 1.56% 的误报率。也就是说，每 800 亿人中有 12.5 亿人，或者每 6400 人中有 100 人。

\n\n

据我所知，还没有已知的实用数据结构可以接近实现这一目标。例如，布隆过滤器不会这样做，因为它们每个项目使用超过 lg 1/\xce\xb5 位。Cuckoo 过滤器不会这样做，因为它们每个项目至少使用两个额外的元数据位，并且每个项目的位速率随 lg n 缩放。

\n