HyperLogLog

概要

HyperLogLog は多重集合 (multiset) における異なりの数問題 (distinct-count problem) を概算するための確率的アルゴリズム。つまり同じ値が複数存在するデータセットから値の種類の数を概算する。異なりの数 (distinct count) とは SQL で COUNT(DISTINCT item) に相当する数であり、例えば集合 \(\{T,\) \(A,\) \(A,\) \(C,\) \(G,\) \(C,\) \(T,\) \(A\}\) の異なりの数は 4 である。

元の Flajolet らの論文[2]では、多重集合における異なりの数を指してカーディナリティ (cardinality) と言葉を使用しているが、多重集合の文脈でのカーディナリティとは重複分を含む要素数を意味している。混乱を避けるためここではカーディナリティという言葉は使用しない。

重複値を持つデータセットから正確な異なりの数 \(n\) を集計するには重複を排除するために \(O(n)\) のメモリ空間が必要となる。しかし追加や削除が頻繁に行われている大規模なデータセットにおいては概算値が得られれば良いことも多く、そのような状況では HyperLogLog を使うことでメモリ量と処理時間を大幅に削減することができる。

HyperLogLog は特に大規模データセットでの集計や分散ストリーミング分析に適していることから、Redis, Spark, Redshift といった分散システムで利用することができる。例えば Redshift では SELECT APPROXIMATE COUNT(item) ... とすることで HyperLogLog を使った集計処理を実行する。

Table of Contents

1. 概要
2. アルゴリズム
   1. Flajolet-Martine アルゴリズム
   2. HyperLogLog アルゴリズム
3. 参考文献

問題設定: ある駅の IC 乗車券の利用記録から利用者数を集計したい。

アルゴリズム

HyperLogLog の考え方は Flajolet-Martine アルゴリズム[1]に基づいている。

Flajolet-Martine アルゴリズム

入力値 \(x\) に対して \(0\) から \(2^m-1\) の範囲で均一に分散されたハッシュ値を生成するハッシュ関数 \(h(x)\) を想定する。ハッシュ値を長さ \(m\) のビット列とみなし、\(\rho(y)\) を \(y\) の最下位ビットから 0 が連続している数を返す関数とする。例えば \(\rho(20)=\rho(10100_2)=2\) であり、\(\rho(11)=\rho(01011_2)=0\) である。

ハッシュ値が均一に分散しているという前提は、ハッシュ値の各ビット列は 0 と 1 が等しい確率で出現するということを意味する。これは \(m\) 回のコインフリップを試行した結果を 1 と 0 で表していると同様に考えることができる。つまり、ハッシュ値が \(\rho(y)=s\) となる確率は、コインフリップで \(s\) 回連続で裏 (または表) が出る確率と等しいと考えられる。

この考えに基づいてアルゴリズムを組み立ててみよう。

1. 長さ \(m\) のビット列 \(z\) を用意する。初期状態はすべてのビットが 0 である。
2. 多重集合 \(M\) に含まれるすべての要素 \(x_i\) に対して、\(z\) の \(\rho(h(x_i))\) 番目のビットを 1 に設定する; つまり \(z[\rho(h(x_i))]=1\)
3. \(r\) を \(z[i]=0\) となる最も小さい \(i\) とする (例えば \(z=101111111_2\) であれば \(r=7\))。このとき \(M\) の異なりの数はおおよそ \(2^r/\phi\) である。ここで \(\phi\simeq 0.77351\) とする。

多重集合 \(M\) の異なりの数を \(n\) 種とすると、ハッシュ値の均一性から \(z\) の最下位ビット \(z[0]\) に 1 を設定するような値は集合内におよそ \(n/2\) 種程度存在する。同様に \(z[1]\) には \(n/4\) 種、\(z[2]\) には \(n/8\) 種、…。つまり \(z[i]\) に 1 を設定する値の数は \(n/2^i\) 種程度と推測される。したがって \(n \ll 2^i\), すなはち \(\log_2 n \ll i\) であれば \(z[i]\) はほぼ確実に 0 であり、また \(\log_2 n \gg i\) であればほぼ確実に 1 である。

たまたま \(\rho(h(x))\) が大きくなるような外れ値が含まれると \(z\) の「大きすぎる位置」のビットに 1 が設定される可能性がある。しかし、すべての値のハッシュ値が \(z\) の「小さすぎる位置」のビットを回避するような値を取ることは考えにくいことから Flajolet-Martine アルゴリズムでは \(z[i]=0\) となる最も小さい \(i\) から異なりの数から概算を行う方針をとっている。

しかしそれでも Flajolet-Martine アルゴリズムは外れ値の影響を受けやすく、実際には結果の分散が大きくなることが問題となる。例えば以下の実装で N を様々な値に変えてみると、誤差 5% 程度となることもあれば 60% や 80% を超えることもある。

import scala.util.hashing.MurmurHash3

// y の k ビット目を返す
def bit(y: Long, k: Int): Int = ((y >> k) & 1).toInt

// 最下位ビットから連続する 0 ビットの数を返す
def ρ(y: Long): Int = (0 to 31).find(i => bit(y, i) == 1).getOrElse(31)

// 31 ビット幅のハッシュ関数
def h(x: Int): Int = MurmurHash3.bytesHash(BigInt(x).toByteArray) & 0x7FFFFFFF

val N = 100000      // 異なりの数
val M = 0 until N   // 重複集合 (実際には重複していないが)

val z = M.foldLeft(0L) { case (z, x) => z | (1 << ρ(h(x))) }
val r = (0 to 31).find(i => bit(z, i) == 0).getOrElse(-1)
val n = math.pow(2, r) / 0.77351
val err = math.abs(n - N) / N
System.out.printf("z=%s, r=%d, n=%f, err=%f\n", z.toBinaryString, r, n, err)

z=1111111111111111, r=16, n=84725.472198, err=0.152745

このような外れ値の影響を軽減するために、異なるハッシュ関数を使用するなどして独立して算出した値の調和平均や中央値を取る方法などが検討される。

HyperLogLog アルゴリズム

HyperLogLog は Flajolet-Martine アルゴリズムと同様に一様に分布するハッシュ値の連続したゼロの最大桁数から異なりの数を確率的に求めている。ただし、Flajolet-Martine アルゴリズムでの外れ値の影響を軽減するために、多重集合を部分集合に分割してそれぞれで得た \(r\) の調和平均を算出することで外れ値の問題を改善している。

〓

HyperLogLog は 1.5kB のメモリーを使用して \(10^9\) を超える異なりの数を通常 2% の精度で概算することができる。

参考文献

1. Philippe Flajolet, G. Nigel Martine. Probabilistic Counting Algorithms for Data Base Applications. Journal of Computer and System Sciences. 31 (2): 182–209. 1985.
2. Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. In AofA 07, 127--146, 2007.