解釋計數草圖算法

Question

有人可以解釋計數草圖算法的工作原理嗎？例如，我仍然無法弄清楚哈希如何被使用。我很難理解this paper。

Answer 1

此流式算法實例化以下框架。

1. 查找隨機流算法，它的輸出（作爲隨機變量）具有所需的期望，但通常高方差（即，噪聲）。

2. 爲了減少方差/噪音，請並行運行多個獨立副本併合並它們的輸出。

通常1更有趣大於2這個算法的2實際上是有點不標準，但我會約1只談。

假設我們正在處理的輸入

a b c a b a . 

有三個櫃檯，就沒有必要湊。

a: 3, b: 2, c: 1 

然而，讓我們假設我們只有一個。有八種可能的功能h : {a, b, c} -> {+1, -1}。這是一個結果表格。

h | 
abc | X = counter 
----+-------------- 
+++ | +3 +2 +1 = 6 
++- | +3 +2 -1 = 4 
+-- | +3 -2 -1 = 0 
+-+ | +3 -2 +1 = 2 
--+ | -3 -2 +1 = -4 
--- | -3 -2 -1 = -6 
-+- | -3 +2 -1 = -2 
-++ | -3 +2 +1 = 0 

現在，我們可以計算出預期

  (6 + 4 + 0 + 2) - (-4 + -6 + -2 + 0) 
E[h(a) X] = ------------------------------------ = 24/8 = 3 
          8 

      (6 + 4 + -2 + 0) - (0 + 2 + -4 + -6) 
E[h(b) X] = ------------------------------------ = 16/8 = 2 
          8 

      (6 + 2 + -4 + 0) - (4 + 0 + -6 + -2) 
E[h(c) X] = ------------------------------------ = 8/8 = 1 . 
          8 

這是怎麼回事？對於a，比方說，我們可以分解X = Y + Z，其中Y是a s的總和變化，而Z是非a的總和。通過預期的線性度，我們有

E[h(a) X] = E[h(a) Y] + E[h(a) Z] . 

E[h(a) Y]是與的a每次出現是h(a)^2 = 1期限的總和，所以E[h(a) Y]是a出現的次數。另一個術語E[h(a) Z]爲零;即使給出h(a)，每個其他哈希值也可能是正數或負數，因此在期望中貢獻爲零。

實際上，散列函數並不需要是統一的隨機，而是好東西：將不可能存儲它。只要散列函數是成對獨立的（任何兩個特定的散列值都是獨立的）就足夠了。對於我們這個簡單的例子，隨機選擇下面四個函數就足夠了。

abc 

+++ 
+-- 
-+- 
--+ 

我會把新的計算留給你。

Answer 2

計數草圖是probabilistic data structure它允許你回答以下問題：

讀取元件a1, a2, a3, ..., an那裏可以有很多重複的元素的流，在任何時候它會給你答案以下問題：到目前爲止您看到了多少個ai元素。

---

您只需通過維護地方鍵是你的ai和價值觀哈希清楚地得到各時刻的準確值是多少元素，你迄今所看到的。這是快速O(1)加，O(1)檢查，它會給你一個確切的數字。它需要O(n)空間，其中n是不同元素的個數唯一的問題（記住，每個元素的大小有着很大的區別，因爲它需要way more space to store this big string as a key不僅僅是this。

---

所以怎麼算草圖你可以選擇2個參數：結果的準確性和錯誤的估計的可能性δ

要做到這一點，你需要選擇一個參數dpairwise independent hash functions這些複雜的詞意味着他們做n經常碰撞（事實上，如果兩者都將空間圖值映射到空間[0, m]上，碰撞概率大約爲1/m^2）。每個散列函數都將這些值映射到空間[0, w]。所以你創建一個d * w矩陣。

現在，當您讀取元素時，計算此元素的各個d哈希值並更新草圖中的相應值。這部分對於計數草圖和計數分鐘草圖是相同的。

Insomniac的解釋很好的想法（計算期望值）的算草圖，所以我只會讓與計數分鐘一切就更簡單了。你只需計算你想得到的值的哈希值並返回其中最小的值。令人驚訝的是這提供了一個強大的準確性和概率保證，你可以find here。

增加散列函數的範圍，增加結果的準確性，增加散列數減少錯誤估計的概率： ＆epsilon; = e/w並且δ = 1/e^d。另一個有趣的事情是價值總是被高估（如果你發現這個價值，它的價值可能大於實際價值，但肯定不會更小）。