私たちは現在、興味深い問題に直面しています。すべてのアイテムを保存する必要なく、セットのカーディナリティを推定したいと考えています (通常、ビットマップ/ビットセットは優れたアプローチです)。非常に優れたアルゴリズムは、いわゆる HyperLogLog ランダム化アルゴリズムです (詳細については、 http://antirez.com/news/75 を参照してください)。
ここでの問題は、セットをUNIONとしてのみマージできるため、基本的にはORの組み合わせです。
実際には、セットを OR だけでなく AND と組み合わせたいと考えています。これらの操作を組み合わせたいとさえ思っています。
例: set1 AND (set2 OR set3) OR (set4 AND set5)
各セットには、数百万の範囲のカーディナリティがある場合があります。各値のサイズは 128 ビットです。
各セットは、「HLL、ブルーム フィルター、単純なリスト、またはこれらの組み合わせ」など、任意の方法で表すことができます。アルゴリズムは、実行可能なスペースを使用して、可能な限り短い時間で実行する必要があります。
何か案は？