邏輯集操作的基數近似 - （「與/或/異或」的「HyperLogLog」）

Question

我們目前正面臨一個有趣的問題。我們想估計集的基數，而不需要存儲每一個項目（通常位圖/位集是一個不錯的方法）。一個非常好的算法就是所謂的HyperLogLog隨機算法（更多在這裏查看http://antirez.com/news/75）。

這裏的問題是，你只能合併集作爲的UNION，所以基本上這是一個或組合。

我們實際上不僅需要將集合與OR結合，而且還要與AND結合使用。我們甚至想要結合這些操作。

實施例： SET1 AND（SET2 OR SET3）OR（AND SET4 SET5）

每一組可以具有數百萬範圍內的基數。每個值都有128位的大小。

每組可以以任何方式表示，例如， 「HLL，布隆過濾器，普通列表或這些的組合」。該算法必須使用可行的空間量在儘可能短的時間內執行。

任何想法？

Answer 1

這個確切的問題是https://pdfs.semanticscholar.org/5da8/bf81712187712aed159aed62e38fb012872e.pdf的主題。他們的建議是使用bloom濾鏡。

聯合布隆過濾器是布隆過濾器的按位或。用於交集的布隆過濾器是布隆過濾器的按位與。因此，您可以輕鬆地生成所需操作的布隆過濾器。

它們的定理1允許您根據布隆過濾器中設置的位數來估計集合的大小。