Bloom过滤器的替代方案

Question

我已经尝试过使用布卢姆过滤器来执行成员测试。我希望对800亿个项目进行成员资格测试，只允许发生大约100次碰撞，即只有100个项目可以得到假阳性结果。

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

我也看过Cuckoo，但是它的内存需求不符合我的要求。我的要求如下：

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

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

Answer 1

哈希函数数量的问题并不是真正的问题--只需选择一个具有多个输出位的散列函数，并将其分割，就好像它们来自不同的散列函数一样。这里真正的问题是错误阳性率与存储空间的权衡。

你说过

我希望对800亿个项目进行成员资格测试，只允许发生大约100次碰撞，即只有100个项目可以得到假阳性结果。

根据定义，映射中的条目不能是假阳性项。他们是真正的阳性者。

那么问题是：“你打算测试多少个条目时，有100个假阳性？”奇怪的是，如果答案也是800亿，那么你要求的是100/80000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000。

任何近似隶属度数据结构(如Bloom滤波器或布库滤波器)的最小空间为n lg1/ε比特，其中n是结构中的元素数，lg是对数基2，ε是假阳性率。换句话说，每个元素需要超过29位才能达到100 /800亿的假阳性率。每个元素6位将得到1.56%的假阳性率，在最好的。这相当于每800亿人中有12.5亿人，或者说每6400人中有100人。

据我所知，目前还没有接近实现这一目标的实用数据结构。例如，Bloom过滤器不使用，因为它们使用超过lg1/ε位的每一项。布谷鸟过滤器不使用，因为他们使用至少两个额外的元数据比特每项，并有一个比特率与lg n。