張 楊: カーディナリティ推定アルゴリズムの概要

繰り返し項目を含む巨大なデータセットがあり、それが大きすぎてメモリに収まらないとします。ここで、このデータセットに一意の要素がいくつあるかを知りたいのですが、データセットはソートされておらず、このような大規模なデータセットをソートしてカウントすることはほぼ不可能です。データセット内に固有のアイテムがいくつあるかをどのように推定しますか?データベース クエリ戦略の設計など、多くのアプリケーション シナリオでこの問題が関係します。適切なデータベース クエリ戦略は、データの合計量に関係するだけでなく、データ内の異なるデータ項目の数にも依存します。

この記事を読み進める前に、この質問について少し考えてみることをお勧めします。なぜなら、次に説明するアルゴリズムは非常に創造的で、あまり直感的ではないからです。

カーディナリティ推定のためのシンプルで直感的な方法

シンプルで直感的な例から始めましょう。以下の手順に従ってデータセットを生成したとします。

1. 一様分布に従うn個の数字をランダムに生成する

2. 不確定な回数と回数で、いくつかの数字をランダムに繰り返す

3. これらの数字の順序をシャッフルしてデータセットを作成します

このデータセットには一意の数字がいくつあるかをどのように推定できますか?これらの数字は均一分布に従う乱数であることがわかっているので、比較的単純で実行可能な解決策は、データ セット内の最小の数字を見つけることです。 m が数値の上限で、x が見つかった最小の数値である場合、m/x は基数の推定値になります。たとえば、0 から 1 までの数字で構成されるデータ セットをスキャンし、最小の数字が 0.01 である場合、データ セットには約 100 個の異なる要素があると合理的に推測できます。それ以外の場合は、より小さい数字が見つかると予想されます。この推定値は繰り返し回数とは無関係であることに注意してください。最小値の値は、最小値が繰り返される回数以上変化しないのと同じです。

この推定方法の利点は非常に直感的であることです。ただし、その精度は平均的です。たとえば、非常に少数の異なる値を持つデータ セットでは、最小値が小さくなる可能性があります。同様に、多数の異なる値を持つデータ セットでは、最小値が小さくならない可能性があります。最後に、ランダム均一分布の前提を実際に満たすデータセットはごくわずかです。ただし、このプロトタイプ アルゴリズムは、基数推定の考え方を理解するための 1 つの方法です。後ほど、より洗練されたアルゴリズムをいくつか見ていきます。

[[104049]]

濃度推定のための確率的アルゴリズム

高精度の基数推定に関する最も初期の論文は、Flajolet と Martin による「データベース アプリケーションのための確率的カウント アルゴリズム」です。その後、Flajolet は、アルゴリズムをさらに改良するために、「LogLog counting of large cardinality」と「HyperLogLog: The analysis of a near-optimal cardinality Estimation algorithm」という 2 つの論文を発表しました。これらの論文を一つずつ読んでアルゴリズムの開発と詳細を理解することは確かに興味深いことですが、この記事ではアルゴリズムの理論的な詳細の一部を無視し、論文のアルゴリズムを使用して問題を解決する方法に主に焦点を当てます。興味のある読者は、これら 3 つの論文を読むことをお勧めします。数学的な詳細についてはこの記事では紹介しません。

Flajolet 氏と Martin 氏は、優れたハッシュ関数が任意のデータ セットを均一分布に従う (疑似) ランダム値にマッピングできることを初めて発見しました。この事実に基づいて、任意のデータセットを均一に分布した乱数のセットに変換し、上記の方法を使用して推定することができますが、これでは十分ではありません。

次に、彼らは他の基数推定方法をいくつか発見しました。そのうちのいくつかは、前述の方法よりも優れたパフォーマンスを発揮しました。 Flajolet と Martin は、ハッシュ値のバイナリ表現の 0 プレフィックスを計算し、乱数セットにおいて、各要素のバイナリ表現の 0 プレフィックスを計算し、最長の 0 プレフィックスの長さを k に設定すると、セット内に平均約 2k 個の異なる要素が存在することを発見しました。この方法を使用して、基数を推定できます。ただし、最小値ベースの推定と同様に、この方法には大きな分散があるため、これは依然として最適ではない推定方法です。一方、この推定方法はリソース効率がより高く、32 ビットのハッシュ値の場合、0 プレフィックスの長さを格納するのに必要なのは 5 ビットだけです。

オリジナルの論文では、Flajolet-Martin がビットマップベースのプロセスを使用して推定アルゴリズムの精度を向上させたことは注目に値します。このアプローチはその後の論文でより優れた方法に置き換えられたため、この点については詳しく説明しません。詳細に興味のある読者は、元の論文を参照してください。

これまでのところ、ビットパターンベースの推定アルゴリズムは最適ではない結果をもたらしました。どうすれば改善できるでしょうか?直感的な改善方法は、複数の独立したハッシュ関数を使用することです。各ハッシュ関数によって生成された最長の 0 プレフィックスを計算し、平均値を取ることで、アルゴリズムの精度を向上させることができます。

実践では、この方法は統計的な観点から推定値の精度を確かに向上できることが示されていますが、ハッシュ値を計算するコストは比較的高くなります。もう 1 つのより効率的な方法は、確率的平均化です。この方式は、複数のハッシュ関数を使用するのではなく、1つのハッシュ関数を使用しながら、ハッシュ値間隔をビットごとに複数のバケットに分割します。たとえば、平均化のために 1024 個の数値を取得する場合は、ハッシュ値の最初の 10 ビットをバケット番号として取得し、残りの部分の 0 プレフィックスの長さを計算できます。この方法は、複数のハッシュ関数を使用する方法と同じくらい正確ですが、複数のハッシュを計算するよりもはるかに効率的です。

上記の分析に基づいて、簡単なアルゴリズムの実装を提供できます。この実装は、Durand-Flajolet の論文で提案された LogLog アルゴリズムと同等です。ただし、便宜上、この実装では 0 個のプレフィックスではなく 0 個のサフィックスをカウントします。効果は同等です。

 def trailing_zeroes(数値):
 "" "num 内の末尾の 0 ビットの数をカウントします。" ""  
 num == 0 の場合:
戻る  32 # 32ビット整数入力を想定します。
  0の場合 
 while (num >> p) & 1 == 0 の場合:
    1 + = 1  
戻るp 
   
 def estimate_cardinality(値、k):
 "" "入力セット値内の一意の要素の数を推定します。 
   
  引数:
    values: カーディナリティを推定するハッシュ可能な要素の反復子。
    k: バケット番号として使用するハッシュのビット数。バケットは2 **k 個になります。
 「」 「 」
  num_buckets = 2 **k
  最大ゼロ = [ 0 ] * バケット数
値内の値:
    h = ハッシュ(値)
    bucket = h & (num_buckets - 1 ) # 最下位kビットをバケットIDとしてマスクします
    バケットハッシュ = h >> k
    max_zeroes[バケット] = max(max_zeroes[バケット]、trailing_zeroes(bucket_hash))
戻る  2 ** ( float (sum(max_zeroes)) / num_buckets) * num_buckets * 0.79402  

このコードは、上で説明した推定アルゴリズムを実装します。各バケットの 0 プレフィックス (またはサフィックス) の最長の長さを計算し、次にこれらの長さの平均を計算します。平均が x でバケット数が m であると仮定すると、最終的な推定値は 2x×m になります。言及されなかったことの一つは、魔法の数字 0.79402 でした。統計分析により、この予測方法には予測可能な偏りがあることが示されており、マジックナンバーはこの偏りを修正します。実際の経験から、計算値はバケットの数によって変化しますが、バケットの数がそれほど小さくない場合（64 より大きい場合）、計算値は推定値に収束することが分かっています。この結論の導出プロセスは原著論文に記載されています。

この方法ではより正確な推定値が得られます。バケット数が m の場合、平均誤差は 1.3/m−−√ です。したがって、バケット サイズが 1024 (必要なメモリ 1024*5 = 5120 ビット、つまり 640 バイト) の場合、平均誤差は約 4% になります。バケットあたり 5 ビットのストレージがあれば、227 のデータ セットを推定するのに十分であり、使用したメモリは 1k 未満です。

テスト結果を見てみましょう:

 >>> [ 100000 /estimate_cardinality([random.random() iが範囲( 100000 )], 10 ) jが範囲( 10 )]
 [ 0.9825616152548807 、 0.9905752876839672 、 0.979241749110407 、 1.050662616357679 、 0.937090578752079 、 0.9878968276629505 、 0.9812323203117748 、 1.0456960262467019 、 0.9415413413873975 、 0.9608567203911741 ]

良い！一部の推定誤差は平均誤差の 4% よりも大きいものの、全体的な効果は良好です。これを自分で試してみることにした場合、注意すべき点が 1 つあります。Python の組み込み hash() メソッドは整数をそれ自体にハッシュします。したがって、estimate_cardinality(range(10000), 10) のようなものは、組み込みの hash() がこのケースに適したハッシュを生成しないため、あまり良い結果は得られません。しかし、上記の例のように乱数を使用する方がはるかに優れています。

精度の向上: SuperLogLog と HyperLogLog

すでに優れた推定アルゴリズムがありますが、アルゴリズムの精度をさらに向上させることができます。 Durand 氏と Flajolet 氏は、外れ値によって推定値の精度が大幅に低下する可能性があることを発見しました。平均を計算する前に特に大きな外れ値をいくつか除外すると、精度が向上する可能性があります。特に、バケット値の最大の 30% を破棄し、バケット値の小さい 70% のみを平均計算に使用することで、平均誤差を 1.3/m−−√ から 1.05/m−−√ に減らすことができます。つまり、上記の例では、640 バイトを使用すると、必要なメモリを増やすことなく、平均エラーが 4% から 3.2% に減少します。

最後に、Flajolet らは HyperLogLog 論文で、幾何平均の代わりに調和平均を使用した異なる種類の平均を提示しています。この改善により、平均誤差は 1.04/m−−√ に減少し、追加のリソースは必要ありません。ただし、このアルゴリズムは、異なる基数のデータ セットに対して異なる修正を行う必要があるため、以前のアルゴリズムよりもはるかに複雑です。興味のある読者は原著論文を読むことができます。

並列化

これらの基数推定アルゴリズムの優れた点の 1 つは、並列化が非常に簡単なことです。同じ数のバケットと同じハッシュ関数の場合、複数のマシン ノードがこのアルゴリズムを独立して並列に実行できます。最後に、各ノードによって計算された同じバケットの最大値を単純にマージして、バケットの最終値を取得できます。さらに、この並列コンピューティングの結果は単一マシン コンピューティングの結果とまったく同じであり、必要な追加消費は異なるノード間での 1k バイト未満の転送のみです。

結論は

カーディナリティ推定アルゴリズムは、非常に少ないリソース (通常は状態を保存するために 1k 未満のスペースを使用) でデータセットのカーディナリティを適切に推定します。この方式はデータ自体の特性とは関係なく、分散並列コンピューティングを効率的に実行できます。推定結果は、トラフィック監視 (サーバーにアクセスした異なる IP アドレスの数) やデータベース クエリの最適化 (並べ替えとマージが必要かどうか、ハッシュ テーブルを構築する必要があるかどうかなど) など、さまざまな側面で使用できます。

すごいアルゴリズム: 基数推定

翻訳リンク: http://www.codinglabs.org/html/cardinality-estimation.html