カウントスケッチアルゴリズムの説明

Question

カウントスケッチアルゴリズムの仕組みを説明できる人はいますか？私はまだ、どのようにハッシュが使用されているか把握できません。 this paperを理解するのは苦労します。

Answer 1

このストリーミングアルゴリズムは、次のフレームワークをインスタンス化します。

1. その出力（ランダム変数として）所望の期待が、通常、高分散（すなわち、ノイズ）を有するランダム化ストリーミングアルゴリズムを探します。

2. 分散/ノイズを低減するには、多くの独立したコピーを並列に実行し、出力を結合します。

通常、1は2よりも面白いです。このアルゴリズム2は実際には多少非標準ですが、私は1つしか話しません。

たちは入力に3つのカウンタで

a b c a b a . 

を処理しているとし、ハッシュする必要はありません。

a: 3, b: 2, c: 1 

ただし、1つしかないとします。可能な関数は8つある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を分解することができます。aの合計の変更はYであり、Zは、aの合計です。期待の直線性により、私たちは

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

E[h(a) Y]を持ってh(a)^2 = 1ので、E[h(a) Y]はaの出現回数であるaの各発生のための用語との和です。その他の用語E[h(a) Z]はゼロです。 h(a)と指定されていても、お互いのハッシュ値は等しいか正である可能性が高いため、期待通りにゼロに貢献します。

実際、ハッシュ関数は均一でランダムである必要はなく、良いこと：格納する方法はありません。ハッシュ関数はペアごとに独立していれば十分です（任意の2つの特定のハッシュ値は独立しています）。私たちの簡単な例では、次の4つの関数のランダムな選択で十分です。

abc 

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

私は新しい計算をあなたに任せます。任意の時間で、それはあなたの次のように答えを与える、繰り返し要素がたくさんあることができる要素a1, a2, a3, ..., anの流れを読む

：

Answer 2

カウントスケッチでは、次の質問に答えることができますprobabilistic data structureです質問：あなたは今まで何度もあなたが見たことがあるai要素。あなたは明らかにちょうどキーがあなたのaiと値であり、ハッシュを維持することにより、各時点での正確な値を得ることができます

---

は、あなたがこれまで見てきたどのように多くの要素です。それは速いですO(1)追加、O(1)チェックとそれはあなたに正確なカウントを与える。それは、nが異なる要素の数があるO(n)スペースを取る唯一の問題は、（それだけでthisよりway more space to store this big string as a keyがかかるため、各要素の大きさは大きな違いがあることに注意してください。スケッチを数えるどのように

---

カウントスケッチは、2つのパラメータ、結果の精度とイプシロンの確率、および悪い見積もりの​​確率を選択することを可能にします。δ

これを行うには、次のいずれかを選択します。これらの複雑な言葉は、それらがn実際には両方のハッシュが値をスペース[0, m]にマッピングすると、衝突確率は約1/m^2になります。これらのハッシュ関数のそれぞれは、値をスペース[0, w]にマップします。したがって、d * w行列を作成します。

要素を読み込むと、この要素の各dハッシュが計算され、スケッチの対応する値が更新されます。この部分は、「カウントスケッチ」と「カウント分スケッチ」で同じです。

不眠症はうまくカウントスケッチのための（期待値を計算する）考えを説明したので、私はちょうど数分すべてとさらに簡単であることを教えてくれます。取得したい値のdハッシュを計算し、最小値を返します。驚いたことに、これは強力な精度と確率の保証を提供します。find hereです。

ハッシュ関数の範囲を広げ、結果の精度を高め、ハッシュの数を増やすと、不正推定の確率が減少します。 ε = e/wおよびδ = 1/e^dである。もう一つ興味深いのは、値が常に過大評価されていることです（値を見つけた場合は、実際の値よりも大きい可能性がありますが、必ずしも小さくはありません）。