如何确定布谷鸟过滤器的大小？

Question

我需要使用布谷鸟过滤器，但我不知道如何确定它的大小。我找到了一个用于布鲁姆过滤器(https://hur.st/bloomfilter/)的计算器，我可以用几种方法进行计算。我可以指定项目的大致数量和期望的假阳性率，它将告诉我哈希函数的大小和数量。我正在寻找类似的布谷鸟过滤器，但我还没有找到一个或其他关于如何找到这些数字的说明。

我正在查看Node或Python实现。定义过滤器的参数似乎是：

• 过滤器的大小或容量
• 水桶尺寸
• 指纹尺寸

我想指定元素的数量(例如100 k)和一个FPR (例如.1%)来找出所需的参数。

Answer 1

根据https://brilliant.org/wiki/cuckoo-filter/ (向下滚动到“空间复杂性”)，每个条目的位数取决于：

bitsPerEntry = (log(1/fpp)+2)/load

fpp是你的假阳性概率。load是你想要的桌子是多满。

因此，只需计算出要在表中放入多少项，乘以bitsPerEntry，再除以8，这将告诉您要为表分配多少字节。通过应用一些简单的代数，你可以构造一个方程来求解任何一个未知数。

文章说，在负载为95.5%的情况下，您可以保持一个稳定的假阳性率，每项7位。

Answer 2

指纹的大小在很大程度上决定了你的错误率。如图3所示，在布谷纸中，桶大小对准确性没有很大影响。桶大小可以大大减少插入时间，因为它减少了占用桶中现有指纹的重定位次数。

我建议指纹7，15，23，31‘，这将最大限度地提高准确性和速度。(8 * n) -1的原因是，由于0是合法的，所以使用一个位来判断单元格是否被占用。

为了回答你的问题，我建议

• 容量-你需要的加5-10%
• FingerPrint - 15位
• 水桶大小-4