瞭解計數草圖數據結構和相關算法

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'計數的估計值。

選擇一個像你所描述的通用散列函數確實可行，但它對理論而非實踐最爲重要。醃製你最喜歡的合理的散列函數也會起作用，你不可能使用一些固定的散列函數來根據期望值寫有意義的證據。