問題タブ [count-min-sketch]

Count-Min スケッチの幅 (バケットの数) と深さ (ハッシュ関数の数) によって、取得される頻度推定の精度が決まります。

Count-Min の元の著者の2005 年の論文から:

パラメーター w と d は、w=⌈e/ε⌉ と d=⌈ln1/δ⌉ を設定することで選択できます。ここで、クエリに答える際のエラーは確率 δ で係数 ε 以内です。

これから、上記のように：

Count-Min の元の著者による2011 年の論文から:

99.9 の確実性で、最大 0.1 (すべての周波数の合計) のエラーが必要であるとします。次に、2/w=1/1000 が必要で、w=2000 と設定し、(1/2)^d=0.001、つまり d=log0.001/log0.5 ≤ 10 とします。

その結果：

それでも、エラーは、スケッチに保存されている要素の総数 N に依存する必要があります。要素が多いほど、エラーとエラーの確率が高くなります。最初のスケッチを作成するための適切な関数は何ですか?

エラー確率パラメーターと許容パラメーターに基づいて、ポイントと範囲のクエリに確率的な答えを与える Count-Min Sketch データ構造について読んでいます。たとえば、「アイテム x がデータ ストリームに 10% の確率で何回出現したか」という質問には、CM で答えることができます。

関連するヘビーヒッターの問題も浮上している。HH 問題に最小ヒープを実装しているときに、スケッチ内のアイテムの最小数がしきい値よりも大きい場合にのみ、ヒープに挿入することを指定しているさまざまな研究論文に気付きました。

私の質問は、これは確率論的にヘビーヒッターの問題に答えているということですか? 対応する質問は、「10% の確率で、データ ストリームで 2 番目に頻度が高かった項目はどれですか?」となります。