data-structures - 了解 Count Sketch 数据结构和相关算法

Question

致力于围绕 CountSketch 数据结构及其相关算法。它似乎是在流数据中寻找共同元素的一个很好的工具，它的可加性使得一些有趣的特性能够发现频率的巨大变化，这可能类似于 Twitter 用于趋势主题的东西。

paper对于已经有一段时间远离更多学术方法的人来说有点难以理解，并且 previous post这里确实帮助了一些人，至少对我来说它仍然留下了很多问题。

据我了解，Count Sketch 结构类似于布隆过滤器。然而，散列函数的选择让我感到困惑。该结构是一个 N × M 表，具有 N 个散列函数，其中 M 个可能的值确定要更改的“存储桶”，每个 N 的另一个散列函数 s 是“成对独立的”

是否要从通用哈希系列中选择哈希，比如 h(x) = ((ax+b) % some_prime) % M？

如果是这样，从哪里选择返回 +1 或 -1 的 s 散列？从其中一个桶中减去的原因是什么？

Answer 1

他们从桶中减去，以使由其他事件引起的加法/减法的平均效果为 0。如果一半时间我添加 'foo' 的计数，一半时间我减去 'foo' 的计数，那么在预期中, 'foo' 的计数不会影响 'bar' 的计数估计。

选择像您描述的通用哈希函数确实会起作用，但对于理论而不是实践来说最重要。对你最喜欢的合理散列函数加盐也可以，你只是不能使用一些固定的散列函数根据预期值有意义地编写证明。