1概要

HYperLogLog(HLL)データ構造は、データセットの濃度を推定するために使用される確率的データ構造です。

何百万ものユーザーがいて、Webページへの個別のアクセス数を計算したいとします。単純な実装では、一意の各ユーザーIDをセットに格納してから、セットのサイズをカーディナリティにします。

非常に大量のデータを扱う場合、このように基数を数えることは非常に非効率的になります。データセットが大量のメモリを占有するためです。

しかし、数パーセント以内の見積もりで問題がなく、正確な訪問数を必要としない場合は、

HLL

を使用することができます。これは、そのようなユースケースに合わせて設計されているためです。何十億もの異なる値** 。


2 Mavenの依存関係

始めるには、https://search.maven.org/classic/#search%7Cgav%7C1%7Cg%3A%22net.agkn%22%20AND%20a%3A%22hllのMaven依存関係を追加する必要があります%22[

hll

]ライブラリ:

<dependency>
    <groupId>net.agkn</groupId>
    <artifactId>hll</artifactId>
    <version>1.6.0</version>
</dependency>


3

HLL


を使用した基数の推定

すぐにジャンプ –

HLL

コンストラクターには、必要に応じて調整できる2つの引数があります。


  • log2m(対数2) –

    これは内部で使用されるレジスタの数です。


HLL

による(注:

m

を指定しています)
**

regwidth –

これはレジスタごとに使用されるビット数です。

より高い精度が必要な場合は、これらをより高い値に設定する必要があります。

このような構成は、

HLL

がより多くのメモリを占有するため、追加のオーバーヘッドが発生します。精度が低くても問題ない場合は、これらのパラメータを低くすると、

HLL

のメモリ使用量が少なくなります。

1億エントリのデータセットの個別の値を数えるための

HLL

を作成しましょう。

log2m

パラメーターを

14

に、

regwidth



5

に等しく設定します。このサイズのデータ​​セットには妥当な値です。

  • それぞれの新しい要素が

    HLL

    に挿入されるとき、それは事前にハッシュされる必要があります。** 正確で速いので、Guavaライブラリから

    Hashing.murmur3

    128()__を使います。

HashFunction hashFunction = Hashing.murmur3__128();
long numberOfElements = 100__000__000;
long toleratedDifference = 1__000__000;
HLL hll = new HLL(14, 5);

これらのパラメータを選択すると、エラー率が1パーセント(1,000,000要素)未満になるはずです。しばらくしてからテストします。

次に、1億の要素を挿入しましょう。

LongStream.range(0, numberOfElements).forEach(element -> {
    long hashedValue = hashFunction.newHasher().putLong(element).hash().asLong();
    hll.addRaw(hashedValue);
  }
);

最後に、

HLL

によって返される基数が、目的のエラーしきい値内にあることをテストできます。

long cardinality = hll.cardinality();
assertThat(cardinality)
  .isCloseTo(numberOfElements, Offset.offset(toleratedDifference));


4

HLL


のメモリサイズ

次の式を使用して、前のセクションの

HLL

に必要なメモリ量を計算できます。

numberOfBits = 2 ^ log2m ** regwidth

この例では、

2 ^ 14 ** 5

ビ​​ット(およそ

81000

ビットまたは

8100

バイト)になります。そのため、

HLL

を使用して1億のメンバーセットの基数を見積もっても、8100バイトのメモリしか占有しませんでした。

これを単純セット実装と比較してみましょう。そのような実装では、1億のLong値の

Set

を持つ必要があります。これは

100,000,000 ** 8

bytes

= 800,000,000

bytes

__.

__を占めます。

違いが驚くほど高いことがわかります。

HLL

を使用すると、8100バイトしか必要としませんが、単純な

Set

実装を使用すると、約800メガバイトが必要になります。

もっと大きなデータセットを考えると、

HLL

と単純な

Set

実装の違いはさらに大きくなります。


5二つの連合

HLLs


別々のデータセットから作成された2つの

HLLを結合してその基数を測定すると、単一の

HLLを使用した場合と同じエラーしきい値が得られます。そして最初から** 両方のデータセットのすべての要素のハッシュ値を計算しました。

2つのHLLを結合するとき、正しい結果を得るためには両方とも同じ

log2m

および

regwidth

パラメーターを持つべきです。

2つの__HLLを作成することによってそのプロパティをテストしましょう。

HashFunction hashFunction = Hashing.murmur3__128();
long numberOfElements = 100__000__000;
long toleratedDifference = 1__000__000;
HLL firstHll = new HLL(15, 5);
HLL secondHLL = new HLL(15, 5);

LongStream.range(0, numberOfElements).forEach(element -> {
    long hashedValue = hashFunction.newHasher()
      .putLong(element)
      .hash()
      .asLong();
    firstHll.addRaw(hashedValue);
    }
);

LongStream.range(numberOfElements, numberOfElements **  2).forEach(element -> {
    long hashedValue = hashFunction.newHasher()
      .putLong(element)
      .hash()
      .asLong();
    secondHLL.addRaw(hashedValue);
    }
);


HLLs

の設定パラメータを調整し、前のセクションで見たように

log2m

パラメータを14からこの例では15に増やしました。結果の

HLL

共用体には2倍の要素が含まれるためです。

次に、

union()メソッドを使用して

firstHll



secondHll

を結合しましょう。ご覧のとおり、推定基数は、2つの要素を持つ1つの

HLL__から基数を取得した場合と同様に、エラーしきい値内にあります。

firstHll.union(secondHLL);
long cardinality = firstHll.cardinality();
assertThat(cardinality)
  .isCloseTo(numberOfElements **  2, Offset.offset(toleratedDifference **  2));


6. 結論

このチュートリアルでは、

HyperLogLog

アルゴリズムを見ました。

集合の基数を推定するために

HLL

を使用する方法を見ました。また、

HLL

は、単純なソリューションと比べてスペース効率が非常に高いこともわかりました。そして、2つの

HLLに対して結合演算を実行し、その結合が単一の

HLLと同じように動作することを検証しました。

これらすべての例とコードスニペットの実装はhttps://github.com/eugenp/tutorials/tree/master/libraries[GitHubプロジェクト]にあります。これはMavenプロジェクトなので、そのままインポートして実行するのは簡単なはずです。