Count-Min Sketch：片側誤差を受け入れてストリームを数える

データストリームは正確な計数を非現実的にした。考えられるすべての項目にカウンタを保持すると、ストリーム処理装置が持つメモリを超えるコストになり得た。従来の要約手法は空間を改善したが、多くの境界は依然として高コストだった。

Count-Min Sketchはカウンタの小さな行列と複数のハッシュ関数を用いた。更新は定数時間のインクリメントであり、点・範囲・内積のクエリは近似だったが、高速でメモリに対して劣線形だった。

CormodeとMuthukrishnanの公開ページはこの改善を要約している。いくつかのストリーム問題において、空間または時間の境界は通常、1/epsilonの二乗の係数から1/epsilonへと改善された。

すべての誤差を上方向に向かわせる

ハッシュ衝突は防ぐのではなく許容されるため、メモリは固定され予測可能になる。

行をまたいで最小値を取ることで、多くのノイズを含むカウンタが有界の過大推定に変わる。

この構造は単一のヘビーヒッター報告だけでなく、複数のストリームクエリを支える。

小さくマージ可能な形状は、テレメトリ、広告、ネットワーキング、データベースにおいて実用的にした。

近似は、その誤差に方向があるときに運用しやすくなる。片側誤差により、下流のシステムは結果を安全な上限推定として扱える。

Count-Min Sketchは、ストリーミングシステムにおける頻度推定の標準的なスケッチの一つとなった。賢明な動きは、衝突が消えるふりをすることではなく、衝突の損害を測定可能かつ片側になるように配置したことだった。