HyperLogLogのシュガーまとめ

HyperLogLogという莫大なユニークカウント(cardinarity)を確率的に推定するアルゴリズムがある。正確にカウントすると数が大きい場合にそれだけ巨大なメモリを必要とするのだが、HyperLogLogでは若干の誤差(数%)を許容することで固定メモリで億を超える数え上げを実現している。そしてHyperLogLogには亜種というかシュガーがやけに多い(たぶん年々増えてる)ので、このスクラップではそれを ~継続的に~ まとめたい。

• HyperLogLog: オリジナル。以下HLLと略することがある
• HLL++ : メモリ使用量を減らし、いくつかのcardinarity範囲における推定精度の向上
  • ハッシュ値を64ビットにした(オリジナルは32ビット)
  • 小さいcardinarityではlinear countを行い、大きくなったらHLLに切り替えるようにした
  • 小さいcardinarityではsparse(疎)なレジスタで、大きくなったらdense(密)に切り替えるようにした
• Sparse : HLL++ のsparseのこと?
• LogLog-Beta : オリジナルではカーディナリティのレンジごとに推定に必要なバイアス・定数が異なっていたが、LogLog-Betaではそれを1つの式で置き換えた (論文)
• TailCut+ : 大きなカーディナリティではレジスタの低位ビット(Tail)を保持する重要度が相対的に小さくなることを利用して、適応的にバイアスかけて低位ビットを捨て(Cut)、メモリ使用量は据え置きでより大きなカーディナリティでの精度を上げた (論文)
• HyperMinHash : ? MinHash(確率的に類似度を示す=Jaccard係数)をHyperLogLog空間でやった。素のMinHashと比べて同じ64KBのメモリ使用量で、9桁くらい大きな母数を扱えるようになった。らしい。(論文)

参考文献:

• https://en.wikipedia.org/wiki/HyperLogLog 英語Wikipedia
• https://github.com/axiomhq/hyperloglog Goの実装。Sparse, LogLog-Beta, TailCut
  • https://github.com/koron/java-hlltc 自前のJava移植
• 【技術解説】集合の類似度(Jaccard係数，Dice係数，Simpson係数)
• https://github.com/LiveRamp/HyperMinHash-java HyperMinHashのJavaの実装