問題は単純です: Redis の表現に基づいて正確な HyperLogLog ユニオンを実装するための最適な戦略を見つける必要があります。これには、データ構造が他の場所で使用するためにエクスポートされる場合の疎/密表現の処理が含まれます。
2つの戦略
2 つの戦略があり、そのうちの 1 つは非常に単純に見えます。私は実際の Redis ソースを調べましたが、精度と効率の観点から、組み込みの構造/ルーチンを使用するか、独自の構造を開発する方が良いかを判断するのに少し苦労しています (C では大きくありません)。 . その価値のために、非常に大きなセットで効率を追求するために、スペースとある程度の誤差 (stdev +-2%) を喜んで犠牲にします。
1. 包含原則
2 つのうち最も単純な方法は、基本的に、ロスレス ユニオン (PFMERGE) をこの原則と組み合わせて使用して、オーバーラップの推定値を計算することです。テストでは、多くの場合、これが確実に実行されていることが示されているようですが、実際の効率と精度を正確に把握するのに苦労しています (場合によっては、この使用例では受け入れられない 20 ～ 40% のエラーが発生する可能性があります)。
基本的：
aCardinality + bCardinality - intersectionCardinality
または、複数セットの場合は...
aCardinality + (bCardinality x cCardinality) - intersectionCardinality
多くの場合、正確に動作するようですが、信頼できるかどうかはわかりません。Redis には、既知の HLL の問題を回避するために設計された低カーディナリティ修飾子が多数組み込まれていますが、(包含/除外を使用した) 非常に不正確な問題が、サイズの大きな不一致のセットで依然として存在するかどうかはわかりません...
2. Jaccard インデックス交差/MinHash
この方法はより興味深いように思えますが、Redis の既存の最適化の一部と計算上重複する可能性があると感じています (つまり、独自の HLL アルゴリズムを最初から実装していません)。
このアプローチでは、MinHash アルゴリズムを使用したビンのランダム サンプリングを使用します (LSH の実装に問題があるとは思いません)。これは別の構造になりますが、minhash を使用してセットの Jaccard インデックスを取得することにより、ユニオン カーディナリティにそのインデックスを効果的に掛けて、より正確なカウントを得ることができます。
問題は、私は HLL に精通していないことです。Google の論文を掘り下げたいのですが、すぐに実行可能な実装が必要です。おそらく、Redis の既存の最適化の基本的な考慮事項、またはかなり緩い信頼限界で計算コストの低い交差推定を可能にするアルゴリズム自体のいくつかの基本的な考慮事項を見落としている可能性があります。
したがって、私の質問：
スペースを犠牲にしても構わないと思っている場合 (そして、わずかな精度で)、redis を使用して、N 個の巨大な (数十億) セットの計算上安価な交差推定を最も効果的に取得するにはどうすればよいですか?