HLL とは何か、どのように機能するのかを理解するために、antirez.com や Wikipedia、その他の情報源を読んでいましたが、「先行ゼロ」という用語が使用されるたびにつまずきます。HyperLogLog について話すときの意味を説明してください。

mongodb で hyperloglog を書き込もうとしています。mongodbの同等のバージョンのクエリ(Oracleで作成)は何ですか?

data.fu には、ここでカーディナリティを推定するための HyperLogLog の優れた実装があります

ただし、これAccumulatorは、レデューサーでのみ実行され、コンバイナーでは実行されないことを意味するように実装されています (ただし、通常のようにセット全体をメモリにロードすることはありませんEvalFunc)。なぜ data.fu はそれをAlgebraic- として実装できず、すべてのコンバイナーでレジスターを埋めてから、結果をマージして削減できなかったのですか? ここで何か不足していますか？

互換性のある 2 つの HyperLogLog オブジェクト間でユニオンを実行する場合、新しいエラーを発生させないロスレス ユニオンを実行するために最大バケットを使用することができます。

ただし、交差を行う場合は、包含と除外の原則を使用する必要があります。

バケットの最小値を使用しても有効な交差として機能しないのはなぜですか?

大量のデータをリレーショナル DB に格納するシステムを実装しています。

データはカテゴリに分類され、作成者を持つことができます。

日付、カテゴリ、作成者でグループ化されたアイテムの数と、日付でグループ化された各カテゴリのすべてのアイテムの合計を取得したいと考えています。

システムはほぼリアルタイムである必要があります。

例 (3 つのカテゴリ、3 つの著者、2 つの日付)

結果：

約 50 のカテゴリと約 50 の著者があります。

この動作を redis でモデル化するにはどうすればよいでしょうか?

ブルームフィルターやハイパーログログなどの構造を使用して、確率的カウントとメンバーシップを設定しようとしています。このような構造をバイナリデータとして保存できると思いますが、競合が多いため、楽観的ロック (別名update if current ) を使用したくありません。

このようなデータ構造を使用し、ユーザー定義関数などを介してサーバー側でアトミックに操作を実行するためのサポートはありますか? または、そのような機能を備えた拡張機能を追加する方法はありますか?

(別のシステムを介してデータを取り込み、更新をバッチ処理して競合を減らすこともできますが、これらすべてをデータベース サーバーで処理できれば、はるかに簡単になります。)

問題は単純です: Redis の表現に基づいて正確な HyperLogLog ユニオンを実装するための最適な戦略を見つける必要があります。これには、データ構造が他の場所で使用するためにエクスポートされる場合の疎/密表現の処理が含まれます。

2つの戦略

2 つの戦略があり、そのうちの 1 つは非常に単純に見えます。私は実際の Redis ソースを調べましたが、精度と効率の観点から、組み込みの構造/ルーチンを使用するか、独自の構造を開発する方が良いかを判断するのに少し苦労しています (C では大きくありません)。 . その価値のために、非常に大きなセットで効率を追求するために、スペースとある程度の誤差 (stdev +-2%) を喜んで犠牲にします。

1. 包含原則

2 つのうち最も単純な方法は、基本的に、ロスレス ユニオン (PFMERGE) をこの原則と組み合わせて使用​​して、オーバーラップの推定値を計算することです。テストでは、多くの場合、これが確実に実行されていることが示されているようですが、実際の効率と精度を正確に把握するのに苦労しています (場合によっては、この使用例では受け入れられない 20 ～ 40% のエラーが発生する可能性があります)。

基本的：

または、複数セットの場合は...

多くの場合、正確に動作するようですが、信頼できるかどうかはわかりません。Redis には、既知の HLL の問題を回避するために設計された低カーディナリティ修飾子が多数組み込まれていますが、(包含/除外を使用した) 非常に不正確な問題が、サイズの大きな不一致のセットで依然として存在するかどうかはわかりません...

2. Jaccard インデックス交差/MinHash

この方法はより興味深いように思えますが、Redis の既存の最適化の一部と計算上重複する可能性があると感じています (つまり、独自の HLL アルゴリズムを最初から実装していません)。

このアプローチでは、MinHash アルゴリズムを使用したビンのランダム サンプリングを使用します (LSH の実装に問題があるとは思いません)。これは別の構造になりますが、minhash を使用してセットの Jaccard インデックスを取得することにより、ユニオン カーディナリティにそのインデックスを効果的に掛けて、より正確なカウントを得ることができます。

問題は、私は HLL に精通していないことです。Google の論文を掘り下げたいのですが、すぐに実行可能な実装が必要です。おそらく、Redis の既存の最適化の基本的な考慮事項、またはかなり緩い信頼限界で計算コストの低い交差推定を可能にするアルゴリズム自体のいくつかの基本的な考慮事項を見落としている可能性があります。

したがって、私の質問：

スペースを犠牲にしても構わないと思っている場合 (そして、わずかな精度で)、redis を使用して、N 個の巨大な (数十億) セットの計算上安価な交差推定を最も効果的に取得するにはどうすればよいですか?

さまざまな組み合わせ (ユーザーが基準を満たしている) について、月ごとに 1 時間ごとに個別のカウントを維持する必要があるという要件があります。そのために HyperLogLog を使用することを考えています。他の要件の 1 つは、一致条件 (基準) の結合と交差の数を提供することです。

これらの操作を 1 日/1 週間/1 か月かけて行う必要があります。私が読んだ限り、ユニオンはhyperloglogを介してサポートされています。交差点が 2 つを超える場合、hyperloglog はエラー率が高いようです。高いカーディナリティを備えた低スペース要件のみを満たす Intersections や、大きな個別の発生をカウントするための Intersection と Union をサポートするデータ構造は他にありますか?

どんなポインタも役に立ちます。ありがとう！！