論理集合演算のカーディナリティ近似 - （AND/OR/XORの "HyperLogLog"）

Question

我々は現在、興味深い問題に直面している。 すべての単一項目を保存する必要なしにセットのカーディナリティ（一般的にはビットマップ/ビットセットは良いアプローチです）をご希望です。非常に優れたアルゴリズムは、いわゆるHyperLogLogランダムアルゴリズムです（詳細はhttp://antirez.com/news/75を参照してください）。

ここでの問題は、あなたがだけなので基本的にはOR組み合わせだ、のUNIONとしてセットをマージすることができていること、です。

実際には、セットをORで組み合わせるだけでなく、ANDで組み合わせることも望みます。我々はこれらの操作を組み合わせたいと思っています。

例： SET1 AND（SET2 OR SET3）OR（SET4 AND set5）

各セットは、何百万の範囲の基数を有していてもよいです。各値のサイズは128ビットです。

各セットは、任意の方法で表現できます。 "HLL、ブルームフィルタ、プレーンリスト、またはこれらの組み合わせ"。アルゴリズムは、可能な限りのスペースを使用して最短時間で実行する必要があります。

アイデア？

Answer 1

この正確な問題は、https://pdfs.semanticscholar.org/5da8/bf81712187712aed159aed62e38fb012872e.pdfという件名です。その推奨はブルームフィルタを使用することです。

ユニオンのブルームフィルタは、ブルームフィルタのビット単位のORです。交差のブルームフィルタは、ブルームフィルタのビット単位のANDです。したがって、必要な操作のブルームフィルタを簡単に生成できます。

定理1は、ブルームフィルタに設定されているビット数からセットのサイズを推定することを可能にします。