HyperLogLogメモ
何かのデータベースソフトウェアでカーディナリティを計算するためにHyperLogLog使ってる、という記述があり、 HyperLogLogがわからん。ということで調べた時のメモ。
まずは、Wikipedia様。
HyperLogLog - Wikipedia, the free encyclopedia
HyperLogLogはデータのカーディナリティを推定する手法の１つ。 詳細は全然わかっていないが、バイナリにおけるLeading Zeros（先頭から0が続く数）の最大値をnとした場合、 2のn乗をカーディナリティの推定値とするアルゴリズム。
調べていくと、以下のスライドを発見。計算例も記載されている。
www.slideshare.net
これを読むと、カーディナリティの値が低いと（1000以下ぐらい？）、HyperLogLogの推定誤差が大きくなり、使えないらしいことがわかる。 そして、それを改善するために、Historic Inverse Probability Estimator(HIP Estimator)という手法が最近、提案されている。 資料後半には手法による誤差を比較したグラフがあり、HIP Estimatorが優れていることを示している。
使い道
データベースのテーブル定義にはカーディナリティいくつと設定しないので、データベースがカーディナリティを把握するのに使える。
データ分析においてはどうか。
カーディナリティが10以下など小さい場合、そもそも、設計者が正確にカーディナリティを把握している可能性が高いので、推定する必要がない。 サービス全体のユーザ数はわかっているが、ある期間のアクセスログから、アクティブユーザ数をざっくりでいいから、とにかく早く計算したい場合に使えるかもしれない。
