JavaでのHyperLogLogアルゴリズムのガイド

投稿日: 2019-10-19 2022-10-25
タグ: Algorithms, Data

1. 概要

HyperLogLog（HLL）データ構造は、データセットのカーディナリティを推定するために使用される確率的データ構造です。

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

非常に大量のデータを処理する場合、データセットが大量のメモリを消費するため、この方法でカーディナリティをカウントすることは非常に非効率的です。

ただし、数パーセント以内の見積もりで問題がなく、正確なユニーク訪問数が必要ない場合は、 HLL を使用できます。これは、まさにそのようなユースケース向けに設計されているためです– 数百万または数十億の異なる値の数を推定する。

2. Mavenの依存関係

開始するには、hllライブラリのMaven依存関係を追加する必要があります。

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

**3. HLLを使用したカーディナリティの推定**

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

log2m（log base 2）– これは、 HLL によって内部的に使用されるレジスタの数です（注： m を指定しています）
regwidth –これはレジスタごとに使用されるビット数です

より高い精度が必要な場合は、これらをより高い値に設定する必要があります。 HLL がより多くのメモリを占有するため、このような構成では追加のオーバーヘッドが発生します。精度が低くても問題がない場合は、これらのパラメータを下げることができ、HLLが占めるメモリは少なくなります。

HLL を作成して、1億エントリのデータセットの個別の値をカウントしてみましょう。 log2mパラメーターを14に等しく、regwidthを5に等しく設定します。これはこのサイズのデータセットに適した値です。

新しい各要素をHLLに挿入するときは、事前にハッシュする必要があります。 Guavaライブラリ（ hllに含まれています）の 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 ビット（おおよそ[X61X]81000ビットまたは8100バイト）になります。したがって、 HLL を使用して1億のメンバーセットのカーディナリティを推定すると、8100バイトのメモリしか占有しませんでした。

これを素朴集合論の実装と比較してみましょう。このような実装では、Setが1億Longの値である必要があります。これは、 100,000,000 *8バイト=800,000,000を占有します。バイト。

違いが驚くほど大きいことがわかります。 HLL を使用すると、必要なのは8100バイトだけですが、単純な Set 実装を使用すると、約800メガバイトが必要になります。

より大きなデータセットを検討すると、HLLと単純なSetの実装の違いはさらに大きくなります。

5. 2つのHLLの和集合

HLL には、和集合を実行するときに1つの有益な特性があります。個別のデータセットから作成された2つの HLL の和集合を取得し、そのカーディナリティを測定すると、単一のHLLを使用し、最初から両方のデータセットのすべての要素のハッシュ値を計算した場合と同じ和集合のエラーしきい値を取得します。

2つのHLLを結合する場合、適切な結果を得るには、両方が同じlog2mおよびregwidthパラメーターを持つ必要があることに注意してください。

2つのHLL– を作成して、そのプロパティをテストしてみましょう。1つには0から1億の値が入力され、もう1つには1億から2億の値が入力されます。

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 で和集合演算を実行し、和集合が1つのHLLと同じように動作することを確認しました。

これらすべての例とコードスニペットの実装は、GitHubプロジェクトにあります。これはMavenプロジェクトなので、そのままインポートして実行するのは簡単です。

getdocs

13036