HyperLogLog

つまり、ユニークな要素の個数を推定する

例えば、1億件のデータの中から、ユニークなデータの個数を調べる場合、

愚直にやると、1億種類のデータを保持しながら、ループで比較する必要があり、メモリが膨大になる

一方で、HyperLogLogを使うと、数千程度の値 (高々数kb)を記憶するだけで、ユニークな個数を推定できる

正確な値は得られないが、1%前後の誤差で推定できる

rustで実装

HyperLogLog を“直感的に”理解するための具体例

シナリオ

あるサービスに 10,000 行のログがあるとする。

code:_

user_id = ??? が 10,000 行

知りたいのは：

これって何人のユニークユーザがいるんだろう？

正確に知りたければ HashSet や辞書に全 user_id を入れればよいが、

データが増えるとメモリが O(N) で爆発する

分散処理にも向かない

そこで HyperLogLog が生まれる。

1.「データ全部は保存しない。観測値だけ保存する。」という発想

やりたいのは ユニーク数（個数）だけ。

値そのもの（"user_12345" など）を保存する必要はない。

そこで各 user_id を

code:_

ハッシュ値 (ランダムな 0/1 の列)

に変換する。

例：

code:_

user_ABC → 0001 0101 1001 ...

user_DEF → 0100 1101 0110 ...

user_XYZ → 0000 0001 1010 ...

...

2. leading zero count（先頭の連続ゼロ個数）を見る

ランダムなビット列では、

先頭ゼロが 1 個続く確率：1/2

2 個続く確率：1/4

3 個：1/8

5 個：1/32

10 個：1/1024

というように、

長いゼロ列はめったに出ない。

つまり…

多くのデータがあれば、まれに「長いゼロ列のハッシュ」が出る

→ これを観測すれば、集合の大きさを推測できる

3. でも最大値 1 個だけではブレすぎる

10,000 行からハッシュを拾っていくと：

code:_

1 行目：ρ = 2

2 行目：ρ = 1

3 行目：ρ = 4

4 行目：ρ = 3

...

最終的に最大 ρ が 10 が出たとする。

code:_

最大 ρ = 10 → ユニーク ≈ 2^10 = 1024？

しかし本当は 8,000 ユーザかもしれない。

1 個の観測値だけだと分散が大きくて使えない。

4. そこで「ハッシュの上位ビットでグループ分け（レジスタ）」を作る

ハッシュ値の最初の数ビットを「レジスタ番号」として使い、

データを複数のグループに分ける。

例：レジスタ数 M=4 の場合（2bit で振り分け）

code:_

00xxxx → レジスタ0

01xxxx → レジスタ1

10xxxx → レジスタ2

11xxxx → レジスタ3

そして 各レジスタごとに最大 ρ を記録する。

5. 10,000 行を処理するとレジスタはこんな感じになる

イメージ：

code:_

つまり最終的に残るのは「レジスタ配列」だけ：

code:_

データ（user_id）は1つも保持していない。

6. この R をまとめて全体のユニーク数を推定する

レジスタの値は「小さな部分集合の観測値」。

これらを統計式でまとめると

code:_

ユニーク数 ≈ 9,800 ± 1%

のような推定値になる。

ポイント：

各レジスタはランダムなサンプルを担当

最大 ρ はそのサンプル内の希少イベント

希少イベントの分布から母集団の大きさを推定

レジスタが多いほど平均化されて精度が安定