用于小型集合上的集合成员资格查询的快速空间高效数据结构

Question

我正在尝试为固定大小的集合创建一个数据结构，该数据结构应支持以下操作：

1. 查询某个元素是否在集合中（误报可以，误报不行）
2. 将集合中的一个元素替换为另一个元素

就我而言，集合的大小可能非常小（4-16 个元素），但查找必须尽可能快并读取尽可能少的位。此外，它还需要节省空间。替换（即操作 2）可能很少。我研究了以下选项：

1. 布隆过滤器：这是标准解决方案。但删除元素比较困难，操作2的实现也比较困难。
2. 计算布隆过滤器：空间需求比标准布隆过滤器高得多（约 3-4 倍），但 false +ve 率不会降低。
3. 简单地存储所有元素的哈希列表：对于类似的空间要求，与计算布隆过滤器相比，提供更好的错误率，但查找成本很高（在最坏的情况下，将查找所有位）。
4. 先前关于位置的完美散列的想法：我不知道关于小元素集的快速完美散列。

附加信息：

• 元素是 64 位数字。

关于如何解决这个问题有什么想法吗？

Answer 1

Cuckoo Filter 是一个应该考虑的选项。引用他们的摘要

Cuckoo Filter：实际上比 Bloom 更好

我们提出了一种称为布谷鸟过滤器的新数据结构，它可以替代布隆过滤器进行近似集成员资格测试。Cuckoo 过滤器支持动态添加和删除项目，同时实现比 Bloom 过滤器更高的性能。对于存储许多项目并以较低误报率为目标的应用程序，**布谷鸟过滤器比空间优化的布隆过滤器具有更低的空间开销。我们的实验结果还表明，布谷鸟过滤器的性能优于以前的数据结构，这些数据结构扩展了布隆过滤器以在时间和空间上大幅支持删除。

https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

Answer 2

嗯，请注意以下几点：

1. 使用标准哈希表，带有下降哈希函数（因为它是数字，所以有一堆标准哈希函数）和 4|S| 条目平均需要少于 2 次查找（假设无偏数字作为输入），尽管它可能会恶化到可怕的最坏情况 4|S|。当然，您可以按如下方式限制它：
   
   - 如果搜索的单元格数量超过k- 中止并返回 true （将导致 FP 以某种概率您可以计算，并且将提供更快的最坏情况性能）。

2. 关于计数布隆过滤器 - 这就是这样做的方法，IMO。请注意，布隆过滤器（标准）需要 154 位才能实现 1% 的 FP 概率，或者需要 100 位才能实现 5% 的 FP 概率。(*)
   因此，如果您需要这个数字的 4 倍，您将得到 616 位/400 位，请注意，在大多数现代机器中，这足够小，足以填充几个 CPU 缓存块，这意味着（取决于机器）- 读取在某些机器上，所有这些位实际上可能需要不到 10 个周期。
   在我看来，如果不获得更高的 FP 率，你就无法做任何事情来击败它。

(*)计算依据：

m = n ln(p) / ln(2) ²

PS如果你能保证每个元素最多被删除一次，你可以使用带有双倍空间的布隆过滤器的变体，它具有稍微更好的FP，但也有一些FN，只需使用2个布隆过滤器：1个用于regular和1个用于deleted。regular如果某个元素位于且不在 中，则该元素在集合中deleted。
这提高了 FP 率，但代价是还具有 FN