ハイパーログログ

HyperLogLogは、カウント・ディスティンクト問題のためのアルゴリズムで、多重集合内の異なる要素の数を概算します。^{[1]多重集合の異なる要素の}正確な 濃度を計算するには、濃度に比例した量のメモリが必要ですが、これは非常に大きなデータ セットでは非現実的です。HyperLogLog アルゴリズムなどの確率的濃度推定器は、これよりもはるかに少ないメモリを使用しますが、濃度を概算することしかできません。HyperLogLog アルゴリズムは、1.5 kB のメモリを使用して、10 ⁹を超える濃度を2% の標準精度 (標準誤差) で推定できます。^{[1] HyperLogLog は、以前の LogLog アルゴリズム[2]}の拡張版であり、それ自体は 1984 年のFlajolet–Martin アルゴリズムから派生したものです。^[3]

Flajoletらによる原著論文^[1]およびcount-distinct 問題に関する関連文献では、「カーディナリティ」という用語は、繰り返し要素を含むデータ ストリーム内の異なる要素の数を意味するために使用されています。ただし、多重集合の理論では、この用語は多重集合の各メンバーの多重度の合計を指します。この記事では、ソースとの一貫性を保つために Flajolet の定義を使用することにします。

HyperLogLogアルゴリズムの基礎は、均一に分布する乱数の多重集合の濃度は、集合内の各数値の2進表現における先頭のゼロの最大数を計算することによって推定できるという観察である。観測される先頭のゼロの最大数が nである場合、集合内の異なる要素の数の推定値は2nである^。 [ ^1]

HyperLogLog アルゴリズムでは、元のマルチセットの各要素にハッシュ関数を適用して、元のマルチセットと同じカーディナリティを持つ均一に分散された乱数のマルチセットを取得します。このランダムに分散されたセットのカーディナリティは、上記のアルゴリズムを使用して推定できます。

上記のアルゴリズムを使用して得られた単純な基数推定値には、分散が大きいという欠点があります。HyperLogLogアルゴリズムでは、マルチセットを多数のサブセットに分割し、これらのサブセットのそれぞれに含まれる数値の先頭のゼロの最大数を計算し、調和平均を使用して各サブセットの推定値を組み合わせてセット全体の基数の推定値を生成することで、分散が最小化されます。^[4]

HyperLogLog には、セットに新しい要素を追加するadd 、セットのカーディナリティを取得するcount 、 2 つのセットの結合を取得するmergeという 3 つの主要な操作があります。派生操作の中には、交差のカーディナリティや、 merge 操作と count 操作を組み合わせた 2 つの HyperLogLog 間の差のカーディナリティなど、包含排他原理を使用して計算できるものもあります。

HyperLogLog のデータは、0 に初期化されたm 個のカウンター (または「レジスタ」)の配列Mに格納されます。多重集合Sから初期化された配列M は、S のHyperLogLogスケッチと呼ばれます。

加算演算は、ハッシュ関数hを使用して入力データvのハッシュを計算し、最初のbビット ( bは) を取得し、それに 1 を加えて変更するレジスタのアドレスを取得します。残りのビットを使用して を計算し、左端の 1 の位置を返します。左端の位置は 1 です (つまり、先頭のゼロの数に 1 を加えた値です)。レジスタの新しい値は、レジスタの現在の値と の間の最大値になります。 ${\textstyle \log _{2}(m)}$${\textstyle \rho (w)}$${\textstyle \rho (w)}$

${\displaystyle {\begin{aligned}x&:=h(v)\\j&:=1+\langle x_{1}x_{2}...x_{b}\rangle _{2}\\w&:=x_{b+1}x_{b+2}...\\M[j]&:=\max(M[j],\rho (w))\\\end{aligned}}}$

カウント アルゴリズムは、 m 個のレジスタの調和平均を計算し、定数を使用してカウントの推定値を導出することから構成されます。 ${\textstyle E}$

${\displaystyle Z={\Bigg (}\sum _{j=1}^{m}{2^{-M[j]}}{\Bigg )}^{-1}}$

${\displaystyle \alpha _{m}=\left(m\int _{0}^{\infty }\left(\log _{2}\left({\frac {2+u}{1+u}}\right)\right)^{m}\,du\right)^{-1}}$

${\displaystyle E=\alpha _{m}m^{2}Z}$

直感的には、n はMの未知の基数であり、各サブセットには要素 が含まれます。すると、はに近くなります。これらの量の 2 の調和平均は で、これは に近いはずです。したがって、 は近似的にnになります。 ${\textstyle M_{j}}$${\textstyle n/m}$${\textstyle \max _{x\in M_{j}}\rho (x)}$${\textstyle \log _{2}(n/m)}$${\textstyle mZ}$${\textstyle n/m}$${\textstyle m^{2}Z}$

最後に、ハッシュ衝突によって 存在する体系的な乗法バイアスを修正するために定数が導入されます。${\textstyle \alpha _{m}}$${\textstyle m^{2}Z}$

この定数は計算が簡単ではないが、次の式で近似できる^[1]。${\textstyle \alpha _{m}}$

${\displaystyle \alpha _{m}\approx {\begin{cases}0.673,&{\text{for }}m=16;\\0.697,&{\text{for }}m=32;\\0.709,&{\text{for }}m=64;\\{\frac {0.7213}{1+1.079/m}},&{\text{for }}m\geq 128.\end{cases}}}$

しかし、HyperLogLog 手法は、しきい値 を下回る小さな基数に対しては偏りがあります。元の論文では、小さな基数に対して、線形カウントと呼ばれる別のアルゴリズムを使用することを提案しています。^[5]上記の推定値がしきい値 より小さい場合は、別の計算を使用できます。 ${\textstyle {\frac {5}{2}}m}$${\textstyle E<{\frac {5}{2}}m}$

1. レジスタのカウントを 0 にします。${\textstyle V}$
2. の場合は、上記の標準 HyperLogLog 推定値を使用します。${\textstyle V=0}$${\textstyle E}$
3. それ以外の場合は、線形カウントを使用します。${\textstyle E^{\star }=m\log \left({\frac {m}{V}}\right)}$

さらに、レジスタのサイズの限界に近づく非常に大きなカーディナリティ（32 ビット レジスタの場合）の場合、カーディナリティは次のように推定できます。 ${\textstyle E>{\frac {2^{32}}{30}}}$

${\displaystyle E^{\star }=-2^{32}\log \left(1-{\frac {E}{2^{32}}}\right)}$

上記の下限と上限の補正により、誤差は次のように推定できます。 ${\textstyle \sigma =1.04/{\sqrt {m}}}$

2つのHLL（）のマージ操作は、レジスタの各ペアの最大値を取得することです。${\textstyle {\mathit {hll}}_{1},{\mathit {hll}}_{2}}$${\textstyle j:1..m}$

${\displaystyle {\mathit {hll}}_{\text{union}}[j]=\max({\mathit {hll}}_{1}[j],{\mathit {hll}}_{2}[j])}$

複雑さを分析するために、データストリーミングモデル^[6]が使用され、これは、固定された成功確率で近似値を得るために必要なスペースを分析する。HLLの相対誤差はであり、必要なスペースは、nがセットの基数、mがレジスタの数（通常は1バイト未満のサイズ）である。 ${\displaystyle (\epsilon ,\delta )}$${\displaystyle 1\pm \epsilon }$${\displaystyle 1-\delta }$${\displaystyle 1.04/{\sqrt {m}}}$${\displaystyle O(\epsilon ^{-2}\log \log n+\log n)}$

追加操作はハッシュ関数の出力のサイズに依存します。このサイズは固定されているため、追加操作の実行時間は と見なすことができます。 ${\displaystyle O(1)}$

カウント操作とマージ操作はレジスタの数mに依存し、理論的なコストはである。いくつかの実装( Redis ) ^[7]ではレジスタの数は固定されており、コストはドキュメントに記載されていると考えられる。 ${\displaystyle O(m)}$${\displaystyle O(1)}$

HyperLogLog++アルゴリズムは、メモリ要件を削減し、いくつかの範囲の基数での精度を向上させるために、HyperLogLogアルゴリズムにいくつかの改良を提案している。^[6]

• 元の論文で使用されていた 32 ビットの代わりに 64 ビットのハッシュ関数が使用されます。これにより、大きな基数でのハッシュ衝突が軽減され、広範囲の補正が不要になります。
• 線形カウントから HLL カウントに切り替えると、基数が小さい場合にバイアスが見つかります。この問題を軽減するために、経験的なバイアス補正が提案されています。
• レジスタのスパース表現は、小さな基数に対するメモリ要件を削減するために提案されており、基数が大きくなった場合には後で密な表現に変換できます。

データが単一のストリームで到着する場合、ヒストリカル逆確率推定器またはマルチンゲール推定器^{[8] [9]は} HLLスケッチの精度を大幅に向上させ、所定のエラーレベルを達成するために36%少ないメモリを使用します。この推定器は、単一のストリーム上の重複を考慮に入れない近似個別カウントスケッチに最適であることが証明されています。

単一ストリームのシナリオでは、HLLスケッチの構築にもバリエーションが生まれます。HLL-TailCut+は、元のHLLスケッチよりもメモリ使用量が45%少なくなりますが、データの挿入順序に依存し、スケッチをマージできないという欠点があります。^[10]

• 「HyperLogLog スケッチの新しいカーディナリティ推定アルゴリズム」(PDF) 。2016年 10 月 29 日閲覧。