Countスケッチのデータ構造と関連するアルゴリズムを理解する

Question

CountSketchデータ構造とその関連アルゴリズムの周りに私の頭をラッピングする作業。これは、ストリーミングデータの共通の要素を見つけるための優れたツールであると思われ、その追加的な性質は、頻度の大きな変化を発見していくつかの楽しいプロパティを作成します。おそらく、Twitterがトレンドトピックに使用するものに似ています。

paperは、しばらくの間、より学問的なアプローチから離れている人にとっては少し難解であり、ここではprevious postが助けてくれました。少なくとも、私はまだかなりの質問が残っていました。

私が理解しているように、Count Sketch構造はブルームフィルタに似ています。しかし、ハッシュ関数の選択は私を混乱させる。構造は、変更する "バケット"を決定するM個の可能な値を有するN個のハッシュ関数を有するN×Mテーブルであり、 "ペアごとに独立"である各Nに対する別のハッシュ関数sを有する。

ハッシュをユニバーサルハッシングファミリー、h（x）=（（ax + b）％some_prime）％Mの何かを言う？

もしそうなら、+ 1か-1のどちらかを返すハッシュはどこから選んでいますか？そして、バケツの1つからこれまでに引いた理由は何ですか？

Answer 1

バケツから減算して、他の発生による加算/減算の平均効果を0にします。時間の半分が 'foo'のカウントを追加し、時間の半分が 'foo'のカウントを減算すると、期待どおり、 'foo'のカウントは 'bar'のカウントの推定に影響しません。

説明したような普遍的なハッシュ関数を選択することは実際にはうまくいくでしょうが、実際には理論よりも重要です。あなたの好きな合理的なハッシュ関数をソルトすることもできます、あなたは意味のあるいくつかの固定ハッシュ関数を使用して期待値に基づいて証明を書くことができません。