logo标签列表

小集合成员查询的快速空间有效数据结构

algorithmdata-structureshashlanguage-agnosticset
5
我正在尝试创建一个数据结构，用于支持以下操作的固定大小集合：
  1. 查询元素是否在集合中（假阳性可以接受，假阴性不行）
  2. 将集合中的一个元素替换为另一个元素
在我的情况下，集合的大小可能非常小（4-16个元素），但查找必须尽可能快，并且读取的位数必须尽可能少。此外，它需要具有高效的空间利用率。替换（即操作2）可能很少。我研究了以下选项：
  1. Bloom过滤器：这是标准解决方案。但是，删除元素很困难，因此难以实现操作2。
  2. 计数Bloom过滤器：与标准Bloom过滤器相比，空间要求变得更高（约为3-4倍），而假阳性率没有降低。
  3. 仅存储所有元素哈希列表：与计数布隆过滤器相比，给出了更好的假阳性率，但查找代价昂贵（在最坏情况下，将查找所有位）。
  4. 使用完美哈希的先前想法来确定位置：我没有快速完美哈希小元素集的想法。
附加信息：
  • 元素是64位数字。
有什么解决方法吗？
它们是64位的大数字。 - Subhasis Das
需要注意的是，该数组必须经过排序。 - Wolph
@Wolph Replacement的时间复杂度为O(n)，以保持数组排序。[否则你可以在O(n)内进行排序] - amit
如果这不是微控制器，我会选择哈希。您可以在单个x64指令中检查16个8位哈希的向量。这将具有令人讨厌的高误报率 - 大约65％，但在常见情况下，它将指示恰好一个潜在匹配项，这只是一个更多的比较，这次是64位。对于常见情况，总共需要192位。这太高了吗？ - rici
@amit：没错，你需要运气才能得到更好的排序。也许在这种情况下，列表/数组组合会更好。 - Wolph
显示剩余7条评论
3个回答
4
Cuckoo Filter是值得考虑的选项。引用他们的摘要：
布谷鸟过滤器：实际上比Bloom更好
我们提出了一种称为布谷鸟过滤器的新数据结构，可以替代Bloom过滤器进行近似集合成员测试。 布谷鸟过滤器支持动态添加和删除项目，同时实现甚至比Bloom过滤器更高的性能。 对于存储许多项目并针对适度低误报率的应用程序，布谷鸟过滤器的空间开销比经过空间优化的Bloom过滤器更低。 我们的实验结果还表明，布谷鸟过滤器在时间和空间方面都大大优于先前将Bloom过滤器扩展到支持删除的数据结构。

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

3

注意以下几点：

  1. 使用标准哈希表，使用一个合适的哈希函数（由于是数字，有许多标准哈希函数可供选择），并使用4|S|个条目，平均只需要不到2个查找（假设输入的数字没有偏差），尽管它可能会恶化为最坏情况的4|S|。当然，你可以按照以下方式进行限制：

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

  2. 关于计数布隆过滤器 - 这是我认为应该采用的方法。请注意，为了使FP概率为1％，标准布隆过滤器需要154位，或者为了使FP概率为5％，需要100位。 (*)
    因此，如果你需要4倍于这个数字，你需要616位/400位。请注意，在大多数现代机器上，这足够小，可以填充几个CPU缓存块，这意味着（取决于机器） - 读取所有这些位可能真的需要不到10个周期。
    我认为除非你接受更高的FP率，否则你无法做任何事情来击败它。

(*) 根据计算得出:

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

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

双重布隆计数器的想法也浮现在我的脑海中。我会去查一下。 - Subhasis Das
值得一提的是，16个64位数字总共占用1024位，因此一个616位计数布隆过滤器占据了60%的数据大小。如果缓存行是512字节，那么布隆过滤器和完整数据都需要两次缓存填充，而让数据自己表示在计算上要简单得多。 - rici
1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接