RedisのHyperLogLogの誤差について
HyperLogLogは集合のcardinalityを近似する確率的アルゴリズムです。
RedisにもPFxxxというcommandで実装されており、標準誤差は0.81%です。
The returned cardinality of the observed set is not exact, but approximated with a standard error of 0.81%.
HyperLogLogは確率的アルゴリズムなので、精度は統計の手法で評価します。
HyperLogLogは期待値がcardinalityとなる確率変数で、標準偏差を真のcardinalityで割って得た相対誤差が0.81%であるということです。
ということは、誤差が0.81%を大きくはみ出すこともあるのでしょうか？
もちろんあります。
以下のデータをRedis 4.0.9にPFADDすると、真のcardinality 10000に対しPFCOUNTの値は1で、相対誤差-99.99%です。
誤差が大きくなるような入力とは
HyperLogLogでは、ハッシュ関数(Redisの場合murmurhash2)を使ってランダムな試行をシミュレートします。
つまりハッシュ値が衝突するとき誤差が大きくなるのは自明ですが、一般にハッシュのpre imageを探すことは困難です。
いっぽう、HyperLogLogが保持するのはハッシュ値のバケットの振り分けと、先頭で連続する0のbit数のみです。（くわしい話はぜひbuilderscon tokyo 2019で！）
つまり完全に衝突せずとも、同じバケットで同じ先頭の0 bit数のハッシュ値になる入力をさがせばよいことになります。
まとめ
builderscon tokyo 2019ではこういった誤差の話や動作原理も含め、HyperLogLogの色々な話をします。
ビルコンにお越しの予定の方はぜひ聴きに来てみてください！
