Flajolet–Martin algorithm
Distinct Countの近似を省メモリで行なう手続き
cardinality estimation
いくつかの小さな int 変数を確保する (100 まで入ればいい)
それぞれの変数 V はハッシュ関数 h_v をもつ
ハッシュ関数のinputは user name みたいなもので output は bit string
tail length
ビット列の末尾の長さは、その末尾にある連続した0の数を表す
Vはそれまでに現われた最も長い tail length を記憶する
重複は影響しない
なぜこれがカウントの近似になるのか
Vが最も大きな tail length R をもつ場合 V は 2^R 個のdifferent elements をもつと推定する
末尾が0か1 → 1/2 で起る。 末尾が0が3つなら 1/8 で起こる → 8個の要素はあると推定する
精度をあげるなら V を増やして別のハッシュ関数を使った結果の平均をとる