致力于研究 CountSketch 数据结构及其相关算法。它似乎是一个在流数据中查找常见元素的好工具，它的附加性质使得它具有一些有趣的属性，可以发现频率的巨大变化，也许类似于 Twitter 用于趋势主题的功能。
paper对于已经远离学术方法一段时间的人来说有点难以理解，并且 previous post这里确实帮助了一些，至少对我来说仍然留下了很多问题。
据我了解，Count Sketch 结构类似于布隆过滤器。然而，哈希函数的选择让我感到困惑。该结构是一个 N × M 表，其中包含 N 个哈希函数，其中 M 个可能的值确定要更改的“存储桶”，以及每个 N 的另一个“成对独立”的哈希函数 s
哈希值是从通用哈希家族中选择的吗，比如 h(x) = ((ax+b) % some_prime) % M？
如果是这样，返回 +1 或 -1 的 s 哈希值是从哪里选择的？从其中一个桶中减去的原因是什么？
最佳答案
它们从存储桶中减去，以使由其他事件引起的加法/减法的平均效果为0。如果一半的时间我添加“foo”的计数，一半的时间我减去“foo”的计数，那么按照预期，“foo”的计数不会影响“bar”计数的估计。
选择像您描述的那样的通用哈希函数确实可行，但它对于理论而不是实践来说最重要。对您最喜欢的合理哈希函数加盐也可以，您只是无法使用一些固定哈希函数根据预期值有意义地编写证明。
关于data-structures - 了解 Count Sketch 数据结构和相关算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8733783/