了解计数草图数据结构和相关算法

Question

正在围绕着CountSketch数据结构及其相关算法进行包装。它似乎是查找流式数据中常见元素的一个很好的工具，而且它的附加特性使得它可以发现频繁变化的一些有趣属性，可能类似于Twitter用于趋势主题的内容。

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

据我了解，计数草图结构类似于布隆过滤器。然而，哈希函数的选择让我感到困惑。该结构是N乘M表，其中N个散列函数具有M个可能的值，以确定要改变的“桶”，以及针对每个N的“成对独立”的另一个散列函数s

散列是否从通用散列族，说h（x）=（（ax + b）％some_prime）％M？

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

Answer 1

他们从桶中减去使其他事件引起的加/减的平均效果为0.如果一半的时间加上'foo'的计数，另一半减去'foo'的计数， ，那么在期望中，'foo'的计数不会影响'bar'计数的估计值。

选择一个像你所描述的通用散列函数确实可行，但它对理论而非实践最为重要。腌制你最喜欢的合理的散列函数也会起作用，你不可能使用一些固定的散列函数来根据期望值写有意义的证据。