逻辑集操作的基数近似 - （“与/或/异或”的“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允许您根据布隆过滤器中设置的位数来估计集合的大小。