4

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

  1. 查询一个元素是否在集合中（假阳性可以，假阴性不行）
  2. 用另一个元素替换集合中的一个元素

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

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

附加信息：

  • 元素是 64 位数字。

关于如何解决这个问题的任何想法？

4

3 回答 3

4

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

Cuckoo 过滤器：实际上比 Bloom 更好

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

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

于 2016-10-14T22:08:13.080 回答
3

好吧，请注意以下几点：

  1. 使用标准哈希表，带有下降哈希函数（因为它是数字，所以有一堆标准哈希函数）和 4|S| 条目平均需要少于 2 次查找（假设输入无偏数字），尽管它可能会恶化为 4|S| 的最坏情况。当然，您可以将其绑定如下：

    - 如果搜索的单元格数量超过k- 中止并返回 true（将导致 FP 在您可以计算的某个概率下，并会提供更快的最坏情况下的性能）。

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

(*)计算依据：

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

PS如果您可以保证每个元素最多被删除一次，您可以使用具有双倍空间的布隆过滤器的变体，而不是具有更好的 FP，但也有一些 FN，只需使用 2 个布隆过滤器：1 个 forregular和 1 个 for deleted。一个元素在集合中，如果它是 inregular而不是 in deleted。
这以牺牲 FN 为代价提高了 FP 率

于 2013-10-10T07:00:27.950 回答
1

查看succinct data structures，例如恒定时间和最小空间中的成员资格。

处理从有界宇宙中选择的子集有很多情况，其中子集的大小相对较大但不足以使用位图。

于 2019-08-28T05:31:51.960 回答