data-structures - 布隆过滤器的替代品

Question

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

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

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

每个元素最多使用 6 位

使用不超过 7-8 个哈希函数。

有人可以向我建议一种概率数据结构，而不是上面提到的可以帮助实现我的要求的数据结构吗？

Answer 1

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

你说过

I wish to perform membership tests on 80 billion entries with only allowing around 100 collisions to happen i.e., only 100 entries can be given a false positive result.

根据定义， map 中的条目可能不是 假 积极的一面。他们是 真积极的一面。

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

任何近似隶属度数据结构(如布隆过滤器或布谷鸟过滤器)的最小空间为 n lg 1/ε 位，其中 n 是结构中的元素数，lg 是以 2 为底的对数，ε 是误报率。换句话说，每个元素需要超过 29 位才能实现误报率，例如每 800 亿个中有 100 个。每个元素 6 位将使您获得 1.56% 的误报率 充其量 .即每 800 亿人中有 12.5 亿人，即每 6400 人中有 100 人。

据我所知，没有已知的实用数据结构可以接近实现这一目标。例如，布隆过滤器不会，因为它们每个项目使用超过 lg 1/ε 位。 Cuckoo 过滤器不会，因为它们每个项目至少使用两个额外的元数据位，并且每个项目的比特率与 lg n 成比例。