HyperLogLogについて

TL;DR

名前が良い。推定値であることに注意すれば有用な場面があると思うので、例えば Redshift なら hll_cardinality とかを確認してみるとよいのではないでしょうか。
パラレルに動かしやすいというのも大きなメリットですね。

HyperLogLog

いわゆる Count-distinct Problem^[1] (またの名を cardinatily estimation problem) を効率的に解くアルゴリズムです。

以下のようなSQLってよく書きますよね。

SELECT COUNT(DISTINCT(id)) FROM table;

SQLで書く文にはこれで終わりなのですが、実行計画的には大変です。素朴にPythonで実装するなら以下みたいな感じでしょうか。

data = [ 何やら大量のデータ。例えばユーザID。 ]
l = []
c = 0
for id in data:
    if id not in l:
        l.append(id)
	c += 1
print(c)

まあこれでもある程度は動くと思います。が、大量のデータが本当に大量すぎると、 l がメモリに収まらない可能性だって出てきます。でも、 l を保持しないと、過去に同じ値があったかどうかなんてわからないですよね。これは困りました。

こんなときに使えるのが HyperLogLog^[2] です。 HyperLogLog は、真面目に l を保持せずもっと効率的に保持できないかを考えます。つまり、ある集合の代わりになるデータを作るデータ(これを Sketching と読んだりするそうです)ことを目指します。

HyperLogLogの大雑把な説明

ある人間の集団がいて、その総数を数えたいとします。普通は一列に並べて一人ずつ数えることを考えると思いますが、ここではちょっと変わった数え方をしたいと思います。

皆に一定の回数コイントスをしてもらいます。例えば、以下のような感じになると思います。(以下では、表が o 、裏が x として表記)

人	表裏の出た順番
A	ooxx
B	oxxo
C	xoox
D	xxoo

このとき、最初(左)から数えて、 o の連続して出た数を数え、その最大値に注目します。上記の例では、 Aさんが最も多く、2回ですね。

さて、コイントスの表裏が出る確率がそれぞれ 50% (つまり、完全にランダム)であったと仮定した場合、連続して2回表が出る確率は以下ですよね。

$$(1/2)^2 = 1/4$$

そうすると、どれだけコイントスを試行したか （≒どれだけの人数がいたか） 考えたときに、最も確率が高いのは4回です。つまり総人数は4人！

こう数えることには、大きな利点があります。それは、 ある人が既にカウントされたかどうかを記録しておく必要がない ということです。なぜなら、 o が続いた最大数だけを覚えておけばいいので。これは、特に大きな人数集団であった場合には特に嬉しいですよね。

---

いやいや、大雑把すぎるだろとか、色々聞こえてきそうです。それは次のセクション以降で説明していきます。ただし、 HyperLogLog の特徴だけ知りたい方は、 「確率的に処理することで、めっちゃメモリ効率よくcount distinctが推定できるアルゴリズム」 くらいの理解で十分かなと思います。

HyperLogLog 自体はすでにいろんなプラットフォームに組み込まれています。例えば Amazon Redshift, Presto, Redisなどです。すでにそれらのプラットフォームを使っている方は、ぜひ使ってみてください。

HyperLogLogのより正確なアルゴリズム

さて、上記で説明したアルゴリズムには、色々欠点がありました。その欠点を緩和するために、以下の方法が提案されています。

まずは、 Estimator を増やすことを考えます。 Estimator とは、先程の例ではコイントスですね。 例えばコイントスに加え、追加で6面サイコロを振らせて、偶数が連続して出た回数を記録しておくことなどをイメージしてください。雑に表現すると、ある値を推定したい場合、それぞれ独立した Estimator で推定しても同じような値になってくれると期待されますよね。Stochastic Averagingなどと呼ばれるそうです。

実際にはコイントスや6面サイコロではなく、 Estimator として用いられるのは適当な hash 関数です。

しかしここで更に問題があります。独立した複数のEstimatorで入力をすべてハッシュ化するのはとても重い処理になってしまいます。

そこで、 HyperLogLogでは一つのハッシュ値だけを利用して同じようなことができないかを考えます。ハッシュの一部を使い複数のバケットに分け、残りのハッシュ値を Estimator として使います。

こうすると、各バケットに入っている値から求められる値は本来求めたい値(Count Distinct)から 1/m になります。なので、最後に m をかけてあげると求めたい値が求まります。

実は、統計的には上記の説明は間違っています。そして、 LogLog と HyperLogLog の違いは主にこの統計的なバイアスをどうするかに関わるのですが、 面倒になってきたので説明を省略 詳細を知りたいときは各論文をあたってください。暇になったら書くかも。

アルゴリズムを書き下すと以下のような感じになります。

Input: カーディナリティを求めたい要素の集合を $\mathcal M$ として用意する
Output: $\mathcal M$ のカーディナリティの推定値 $n$ を求める。

1. $m=2^b$ の長さとなる配列 $\mathcal C$ を定義する。それぞれの要素の初期値を $-\infty$ とする。
2. $\mathcal M$ の要素 $v$ 一つずつに対し、以下の操作を行う
   • hash関数を用いて 0, 1のビットのストリームとする
   • 最初の $b$ 個の ビットを用いて、 Cのどのインデックスをアップデートするかを決める
   • 残りのハッシュ値を使って、0が連続して出てくる個数を求め、Cの要素をアップデートする
3. 最終的に出てきた値を使って、 $\mathcal n$ の推定値を求める。

なんでLogLogなの？

$\mathcal M$ の カーディナリティを推定するのに、 カーディナリティ $\mathcal n$ の $\log_2 \log_2 n$ しか保持する必要がないためらしい。

参考文献

• https://engineering.fb.com/2018/12/13/data-infrastructure/hyperloglog/
• https://blog.brainpad.co.jp/entry/2016/06/27/110000
• https://www.slideshare.net/iwiwi/minhash
• https://recruit.gmo.jp/engineer/jisedai/blog/redis_fast_counting/
• http://cscubs.cs.uni-bonn.de/2016/proceedings/paper-03.pdf

脚注

1. https://en.wikipedia.org/wiki/Count-distinct_problem

2. http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf