HyperLogLog —— データのサイズを統計と確率原理を利用して推定する

HyperLogLog アルゴリズムの概要#

ビッグデータ処理では、独立した要素の数を統計する必要がある場面がよくあります。例えば、大規模なウェブサイトの毎日の独立ユーザーの訪問数を知りたいとします。簡単な方法は、ユーザーごとにハッシュテーブルを使用して追跡することです。しかし、巨大なユーザー数の場合、この方法は大量のメモリを必要とします。各ユーザーにテーブル上で場所を確保する必要があるため、ビッグデータの場面では適用できません。また、ほとんどの場合、ユーザーのおおよその規模を知るだけで十分なので、HyperLogLog はこのような場合に適しています。

1. HyperLogLog とは何ですか？#

HyperLogLog（HLL）は、Philippe Flajolet と他の人々によって 2007 年に提案された、大規模なデータセットの独立した要素の数を推定するためのアルゴリズムです。直接数える方法と比較して、HLL の素晴らしい点は、非常に小さな固定サイズのメモリ（通常数 KB）しか必要としないことです。

2. HyperLogLog の原理#

HLL の基礎は、ランダムデータのハッシュ値の特性を観察することです。要素をハッシュすると、均一なハッシュ関数は均一な分布の結果を返すはずであり、その結果はランダムと見なすことができます。

HLL の核心アイデアは、ハッシュ値の先頭に連続する 0 の数を数えることです。例えば、ハッシュ値 "001010..." の先頭の 0 の数は 2 です。ハッシュ値はランダムなので、先頭の 0 の平均数は推定基数の指標となります。単純に言えば、先頭の 0 の数を数えることで、その値が大きいほど、異なるユーザーを **「見る」** 必要がある確率が高くなります。

例を挙げると、コインを連続して投げ続けると、連続して 5 回表が出るよりも連続して 10 回表が出る確率は低くなります。一般的に、連続して 10 回表が出るためには、より多くのコイン投げが必要です。

HLL は確率的な統計手法であるため、次のいくつかの要素が推定の精度に影響を与えます：

1. ハッシュ関数の均一な分布#

データをハッシュする際に均一な分布のハッシュ関数を使用すると、生成されるバイナリハッシュ値はランダムな数と見なすことができます。ハッシュ値の各ビットが 0 または 1 である確率は 50％です。

2. ハッシュ関数のパフォーマンス#

HLL のパフォーマンスは、ハッシュ関数のパフォーマンスに大きく依存します。ハッシュ関数は、入力データを出力空間に均等に分布させ、各バケットがほぼ同じ数のデータを取得することを保証する必要があります。また、速度も考慮する必要があります。

3. 先頭のゼロ（Leading Zeros）#

ランダムなバイナリ数字を考えてみましょう。最上位ビットが 0 である確率は 50％です。連続する 2 つの最上位ビットが 0 である確率は 25％です。このように、連続する k 個の最上位ビットが 0 であるイベントは非常に稀であり、多くの一意の要素の存在を表すために使用できます。

4. バケットまたはカウンター（Buckets）#

単一のデータのランダム性による推定の不安定性を解決するために、HLL は複数のバケットを使用します。ハッシュ値の最初のいくつかのビットは、要素がどのバケットに入るかを決定し、残りの部分は先頭のゼロを計算するために使用されます。

例えば、16 個のバケット（0-15）を使用する場合、ハッシュ値の最初の 4 ビットがバケットの番号を決定します。各バケットは、そのバケット内のハッシュ値の先頭ゼロの最大数を保持します。

5. カウンター値のマージ#

全体の基数推定を得るために、すべてのバケットの値を単純に合計するわけではありません。調和平均を使用する必要があります： $\frac{m}{\sum_{j=1}^{m} 2^{-M[j]}}$ 、ここで m はバケットの数であり、M [j] は j 番目のバケットが記録した先頭ゼロの数です。
バケットは互いに独立ではないためです。1 つのバケットが 5 つの先頭ゼロを観測するかもしれず、別のバケットが 3 つの先頭ゼロを観測するかもしれません。これらの数値を単純に合計する（例えば $2^5 + 2^3$ ）と、これらのバケットが一部同じ要素を観測したことによる重複カウントが発生します。重要なのは、全体の基数を推定していることであり、各バケットの個別の推定を累積しているわけではありません。

6. 小カウントと大カウントのバイアスの修正#

上記の方法は中程度の基数に対してはうまく機能しますが、非常に小さな基数や非常に大きな基数に対してはバイアスが生じる可能性があります。これらのバイアスを修正するために、HLL には以下の修正が用意されています：

小数の修正: 推定値が 5/2m 未満の場合、多くの空のバケットが存在する可能性を考慮して、推定値を線形カウントで修正します。
大数の修正: 推定値が 2^32（32 ビットハッシュの場合）に近づくと、オーバーフローを考慮して推定値を修正します。

3. データ構造#

HyperLogLog は、バケット配列を使用して情報を格納します。各バケットは、対応するハッシュ値の先頭ゼロの最大数を記録します。アルゴリズムの出力は、すべてのバケットの値に基づく関数です。

4. 精度とメモリ#

HLL の精度は、バケットの数に関連しています。より多くのバケットはより高い精度を意味しますが、同時により多くのメモリを使用します。幸いなことに、数 KB のメモリでも HLL は非常に合理的な推定を提供することができます。

5. マージ#

HLL の強力な機能の 1 つは、マージ操作をサポートしていることです。独立した 2 つの HLL データ構造があり、それぞれが異なるデータセットを追跡している場合、それらを 1 つにマージすることができます。この新しい HLL は、1 つの大規模なデータセットを追跡しているかのように機能します。

これにより、HLL は分散処理を行うために複数のマシンで使用でき、ビッグデータ処理のシナリオに適しています。複数のマシンでデータを処理する場合、単純な「和集合を求める」操作によって、サンプル全体の統計結果を得ることができます。

まとめ#

HyperLogLog は、有限のメモリで大規模なデータセットの基数を推定するための効率的なアルゴリズムです。近似値しか提供しないものの、多くの実際のアプリケーションでは、この近似値は十分であり、メモリの節約の利点が貴重なツールとなっています。

以下に、アルゴリズムの簡単な C 言語実装を示します。このコードは、簡潔で直感的な例を提供することを目的としていますが、実稼働環境では最適化や境界条件の処理など、多くの詳細が省略されています。また、このハッシュ関数は単純化されており、実際のプロダクション環境には適していません。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define BUCKET_COUNT 1024  // 2^10 buckets

typedef struct {
    unsigned char buckets[BUCKET_COUNT];
} HyperLogLog;

// ハッシュ関数の簡単な例。実際のアプリケーションでは、MurmurHashやCityHashなどの高品質なハッシュ関数を使用することをお勧めします。
unsigned int hash_function(const char* data) {
    unsigned int hash = 0;
    while (*data) {
        hash = (hash * 31) + *data++;  // 単純な乗算ハッシュを使用
    }
    return hash;
}

int leading_zeros(unsigned int value) {
    if (value == 0) return 32;
    int count = 0;
    while ((value & 0x80000000) == 0) {
        count++;
        value <<= 1;
    }
    return count;
}

void hll_add(HyperLogLog *hll, const char* data) {
    unsigned int hash = hash_function(data);
    int bucket_idx = hash & (BUCKET_COUNT - 1);
    int zero_count = leading_zeros(hash >> 10);  // bucket_idx以外の部分を使用
    if (zero_count > hll->buckets[bucket_idx]) {
        hll->buckets[bucket_idx] = zero_count;
    }
}

double hll_count(const HyperLogLog *hll) {
    double sum = 0.0;
    for (int i = 0; i < BUCKET_COUNT; i++) {
        sum += pow(2.0, -hll->buckets[i]);
    }
    return BUCKET_COUNT * BUCKET_COUNT / sum;
}

int main() {
    HyperLogLog hll;
    memset(&hll, 0, sizeof(hll));

    const char* samples[] = {
        "user1", "user2", "user3", "user1", "user2", "user4"
    };
    int sample_count = sizeof(samples) / sizeof(samples[0]);
    for (int i = 0; i < sample_count; i++) {
        hll_add(&hll, samples[i]);
    }
    printf("推定ユニーク数: %f\n", hll_count(&hll));
    return 0;
}