196

私は最近、空き時間にさまざまなアルゴリズムについて学んでおり、非常に興味深いと思われるアルゴリズムに出くわしたのは、HyperLogLog アルゴリズムと呼ばれるもので、リスト内の一意のアイテムの数を推定します。

「カーディナリティ」の値 (これは最近まで、計算されたものであり、推定されたものではないと常に想定していました) を見たときに、MySQL の時代に戻ったので、これは特に興味深いものでした。

だから私は、配列内の一意のアイテムの数を計算するアルゴリズムをO ( n )に記述する方法を知っています。私はこれをJavaScriptで書きました：

function countUniqueAlgo1(arr) {
    var Table = {};
    var numUnique = 0;
    var numDataPoints = arr.length;
    for (var j = 0; j < numDataPoints; j++) {
        var val = arr[j];
        if (Table[val] != null) {
            continue;
        }
        Table[val] = 1;
        numUnique++;
    }
    return numUnique;
}

しかし、問題は、私のアルゴリズムがO ( n ) であるのに対し、大量のメモリを使用する (値を に格納するTable) ことです。

O ( n ) 時間でリスト内の重複をカウントし、最小限のメモリを使用する方法について、この論文を読んでいます。

ビットまたは何かをハッシュしてカウントすることにより、特定の確率（リストが均等に分散されていると仮定）内でリスト内の一意のアイテムの数を推定できることを説明しています。

論文を読んだのですが、理解できないようです。誰かがより素人の説明をすることができますか？ハッシュとは何かは知っていますが、この HyperLogLog アルゴリズムでハッシュがどのように使用されているかわかりません。

4

3 に答える 3

182

このアルゴリズムの背後にある主なトリックは、ランダムな整数のストリームを観察し、バイナリ表現が既知のプレフィックスで始まる整数を確認した場合、ストリームのカーディナリティが 2^(プレフィックスのサイズ) である可能性が高いことです。 .

つまり、整数のランダムなストリームでは、数字の約 50% (バイナリ) が「1」で始まり、25% が「01」で始まり、12.5% が「001」で始まります。これは、ランダム ストリームを観察して「001」が表示された場合、このストリームのカーディナリティが 8 である可能性が高いことを意味します。

(プレフィックス「00..1」には特別な意味はありません。ほとんどのプロセッサで 2 進数の最上位ビットを簡単に見つけることができるという理由だけで存在します)

もちろん、整数を 1 つだけ観測した場合、この値が間違っている可能性は高くなります。そのため、アルゴリズムはストリームを "m" 個の独立したサブストリームに分割し、各サブストリームのプレフィックス "00...1" の最大長を維持します。次に、各サブストリームの平均値を取得して最終的な値を推定します。

それがこのアルゴリズムの主なアイデアです。いくつかの詳細が欠落しています (たとえば、低い推定値の修正など) が、すべて論文に詳しく書かれています。ひどい英語でごめんなさい。

于 2012-10-04T19:19:54.930 に答える
127

HyperLogLog は確率的データ構造です。リスト内の個別の要素の数をカウントします。しかし、それを行う簡単な方法 (セットを持ち、セットに要素を追加する) と比較すると、これはおおよその方法で行われます。

HyperLogLog アルゴリズムがこれをどのように行うかを見る前に、なぜそれが必要なのかを理解する必要があります。O(distinct elements)簡単な方法の問題は、スペースを消費することです。ここに、個別の要素ではなく、大きな O 表記があるのはなぜですか? これは、要素のサイズが異なる可能性があるためです。1 つの要素を1別の要素にすることができます"is this big string"。したがって、巨大なリスト (または要素の巨大なストリーム) がある場合、多くのメモリが必要になります。

確率的カウント

一意の要素の数を合理的に見積もるにはどうすればよいでしょうか? 等しい確率mで構成される長さの文字列があると仮定します。{0, 1}0、2 つのゼロ、k のゼロから始まる確率は? です1/2、1/4そして1/2^k。これは、kゼロを含む文字列に遭遇した場合、おおよそ2^kの要素を調べたことを意味します。したがって、これは良い出発点です。均等に分散された要素のリストがあり0、2^k - 1バイナリ表現でゼロの最大プレフィックスの最大数を数えることができ、これにより合理的な見積もりが得られます。

0問題は、 tから数値が均等に分散されているという仮定2^k-1を達成するのが難しすぎることです (私たちが遭遇したデータは、ほとんどが数値ではなく、均等に分散されることはほとんどなく、任意の値の間に存在する可能性があります。しかし、優れたハッシュ関数を使用すると、次のように仮定できます。出力ビットは均等に分散され、ほとんどのハッシュ関数は と の間の出力を持ちます( SHA10はとの間の値を返します). したがって、これまでに達成したことは、ビットの最大カーディナリティを持つ一意の要素の数を、格納するだけで推定できることです。サイズビットの 1 つの数. マイナス面は、見積もりに大きなばらつきがあることです. 私たちがほぼ作成したクールなもの2^k - 102^160klog(k)1984 年の確率論的計数論文 (見積もりの​​方が少しスマートですが、それでも近いです)。

ログログ

先に進む前に、最初の見積もりがそれほど大きくない理由を理解する必要があります。その背後にある理由は、高頻度の 0 プレフィックス要素が 1 回ランダムに発生すると、すべてが台無しになる可能性があるためです。それを改善する1つの方法は、多くのハッシュ関数を使用し、各ハッシュ関数の最大値を数え、最終的にそれらを平均化することです. これは優れたアイデアであり、推定値を改善しますが、LogLog の論文では、わずかに異なるアプローチが使用されました (おそらく、ハッシングはコストがかかるためです)。

彼らは 1 つのハッシュを使用しましたが、それを 2 つの部分に分割しました。1 つはバケット (バケットの総数は2^x) と呼ばれ、もう 1 つは基本的にハッシュと同じです。何が起こっているのかわかりにくかったので、例を挙げます。02 つの要素と、生成された 2 つの値に値を与えるハッシュ関数があると仮定します2^10:344と387. 16 個のバケットを持つことにしました。だからあなたは持っています：

0101 011000  bucket 5 will store 1
0110 000011  bucket 6 will store 4

バケットを増やすと、分散が減少します (使用するスペースがわずかに増えますが、それでも小さいです)。数学のスキルを使用して、エラーを定量化することができました (これは です1.3/sqrt(number of buckets))。

ハイパーログログ

HyperLogLogは新しいアイデアを導入するものではありませんが、以前の見積もりを改善するために多くの計算を使用します。研究者は、バケットから最大数の 30% を削除すると、推定値が大幅に改善されることを発見しました。彼らはまた、数値を平均化するために別のアルゴリズムを使用しました。この論文は数学が重いです。

そして、hyperLogLog アルゴリズムの改良版を示す最近の論文で締めくくりたいと思います(これまでは完全に理解する時間がありませんでしたが、後でこの回答を改善する予定です)。

于 2016-02-05T08:42:59.317 に答える
26

直観的には、入力が乱数の大きなセット (ハッシュ値など) である場合、それらは範囲全体に均等に分散するはずです。1024 までの値を表すために、範囲が最大 10 ビットであるとしましょう。次に、最小値を観察しました。10 としましょう。この場合、カーディナリティは約 100 (10 × 100 ≈ 1024) と推定されます。

もちろん、実際のロジックについては論文を読んでください。

サンプル コードを使用した別の適切な説明がここにあります:
Damn Cool Algorithms: Cardinality Estimation - Nick's Blog

于 2012-09-11T17:45:37.737 に答える