エラー確率パラメーターと許容パラメーターに基づいて、ポイントと範囲のクエリに確率的な答えを与える Count-Min Sketch データ構造について読んでいます。たとえば、「アイテム x がデータ ストリームに 10% の確率で何回出現したか」という質問には、CM で答えることができます。
関連するヘビーヒッターの問題も浮上している。HH 問題に最小ヒープを実装しているときに、スケッチ内のアイテムの最小数がしきい値よりも大きい場合にのみ、ヒープに挿入することを指定しているさまざまな研究論文に気付きました。
私の質問は、これは確率論的にヘビーヒッターの問題に答えているということですか? 対応する質問は、「10% の確率で、データ ストリームで 2 番目に頻度が高かった項目はどれですか?」となります。