カウントスケッチアルゴリズムがどのように機能するかを誰かが説明できますか？たとえば、ハッシュがどのように使用されているかはまだわかりません。私はこの論文を理解するのに苦労しています。
質問する
17286 次
2 に答える
52
このストリーミング アルゴリズムは、次のフレームワークをインスタンス化します。
出力 (確率変数として) が望ましい期待値を持つが、通常は分散 (つまりノイズ) が高いランダム化されたストリーミング アルゴリズムを見つけます。
分散/ノイズを減らすには、多くの独立したコピーを並行して実行し、それらの出力を結合します。
通常、1 は 2 よりも興味深いものです。このアルゴリズムの 2 は、実際にはやや標準的ではありませんが、1 についてのみ説明します。
入力を処理しているとします
a b c a b a .
3 つのカウンターがあるため、ハッシュする必要はありません。
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。ここで、 はs のY合計の変化であり、は非s の合計です。期待値の線形性により、aZa
E[h(a) X] = E[h(a) Y] + E[h(a) Z] .
E[h(a) Y]は が出現するたびにある項の合計であり、aの出現回数もh(a)^2 = 1同様です。もう 1 つの項はゼロです。が与えられたとしても、他の各ハッシュ値はプラスまたはマイナス 1 である可能性が等しく、期待値がゼロになる可能性があります。E[h(a) Y]aE[h(a) Z]h(a)
実際、ハッシュ関数は一様乱数である必要はありません。良いことに、ハッシュ関数を保存する方法はありません。ハッシュ関数がペアごとに独立していれば十分です (任意の 2 つの特定のハッシュ値は独立しています)。この単純な例では、次の 4 つの関数をランダムに選択するだけで十分です。
abc
+++
+--
-+-
--+
新しい計算はあなたに任せます。
于 2011-07-25T04:20:25.050 に答える
33
Count Sketch は、次の質問に答えることができる確率的データ構造です。
要素a1、a2、a3、...のストリームを読み取ると、an多くの繰り返し要素が存在する可能性があり、次の質問に対する答えがいつでも得られます:これまでにいくつの要素を見てきましたか?ai
aiこれまでに見た要素の数から へのマッピングを維持するだけで、いつでも正確な答えを明確に得ることができます。新しい観測値の記録にはO(1)のコストがかかり、特定の要素の観測数のチェックも同様です。ただし、このマッピングを格納するにはO(n)のスペースが必要です。ここで、 nは個別の要素の数です。
Count Sketch はどのようにあなたを助けますか? すべての確率的データ構造と同様に、スペースのために確実性を犠牲にします。Count Sketch では、結果の精度 (ε) と不適切な推定の確率 (δ) の 2 つのパラメーターを選択できます。
これを行うには、d ペアごとに独立したハッシュ関数のファミリを選択します。これらの複雑な単語は、あまり頻繁に衝突しないことを意味します (実際、両方のハッシュが空間[0, m]に値をマップする場合、衝突の確率は約1/m^2です)。これらの各ハッシュ関数は値を空間[0, w]にマップするため、 d * w行列を作成します。
要素を読み取るときは、この要素の各dハッシュを計算し、スケッチ内の対応する値を更新します。この部分は Count Sketch と Count-min Sketch と同じです。
Insomniac は Count Sketch のアイデア (期待値の計算) をうまく説明したので、Count-min Sketch ではすべてがさらに簡単であることに注意してください。取得したい値のdハッシュを計算し、最小のものを返すだけです。驚くべきことに、これは強力な精度と確率の保証を提供します。
ハッシュ関数の範囲を大きくすると、結果の精度が向上しますが、ハッシュの数を増やすと、不適切な推定の可能性が減少します: ε = e/wおよびδ=1/e^d。もう 1 つの興味深い点は、値が常に過大評価されていることです (値が見つかった場合、実際の値よりも大きい可能性が高いですが、小さくはないことは確かです)。
于 2016-02-12T06:22:35.847 に答える