読者です 読者をやめる 読者になる 読者になる

pandazx's blog

Hadoop, データ分析など雑多な技術ブログ

HyperLogLogメモ

何かのデータベースソフトウェアでカーディナリティを計算するためにHyperLogLog使ってる、という記述があり、 HyperLogLogがわからん。ということで調べた時のメモ。

まずは、Wikipedia様。

HyperLogLog - Wikipedia, the free encyclopedia

HyperLogLogはデータのカーディナリティを推定する手法の1つ。 詳細は全然わかっていないが、バイナリにおけるLeading Zeros(先頭から0が続く数)の最大値をnとした場合、 2のn乗をカーディナリティの推定値とするアルゴリズム

調べていくと、以下のスライドを発見。計算例も記載されている。

www.slideshare.net

これを読むと、カーディナリティの値が低いと(1000以下ぐらい?)、HyperLogLogの推定誤差が大きくなり、使えないらしいことがわかる。 そして、それを改善するために、Historic Inverse Probability Estimator(HIP Estimator)という手法が最近、提案されている。 資料後半には手法による誤差を比較したグラフがあり、HIP Estimatorが優れていることを示している。

使い道

データベースのテーブル定義にはカーディナリティいくつと設定しないので、データベースがカーディナリティを把握するのに使える。

データ分析においてはどうか。

カーディナリティが10以下など小さい場合、そもそも、設計者が正確にカーディナリティを把握している可能性が高いので、推定する必要がない。 サービス全体のユーザ数はわかっているが、ある期間のアクセスログから、アクティブユーザ数をざっくりでいいから、とにかく早く計算したい場合に使えるかもしれない。