HyperLogLog
HyperLogLog はハッシュ値の先頭ゼロの個数から濃度（ユニーク数のカウント）を近似する。小さな固定メモリで巨大なユニーク数を推定できる。
目的
固定メモリ（〜KB 程度）で数十億件のユニーク要素を近似的に数える。ユニーク訪問者統計などに使われる。
メカニズム
各要素をハッシュし、先頭 k ビットでバケット分けし、各バケットに残りビットの先頭ゼロの最大個数を記録する。濃度の推定値 ≈ α·m²·∑2^M[i]。相対誤差は約 1.04/√m。Redis の PFCOUNT がこれを使う。
ユースケース
- ユニーク訪問者統計
- 濃度（カーディナリティ）の推定
- ストリームのユニーク数カウント