count-min

複数の見積もりの最小値で出現回数を推定する方式

1本の論文題名に登場

定義

同じ項目を複数の独立なハッシュ表に加算し、問い合わせ時はその中の最小値を返すことで出現回数を推定する方式。衝突による水増しは起きるが取りこぼしは起きないため、推定値は必ず真値以上という片側誤差になる。Count-Min Sketch という構造名の前半として現れる。

Count-Min Sketchの一部