algorithm - 逻辑集合运算的基数近似值——(AND/OR/XOR 的 "HyperLogLog")

Question

我们目前面临一个有趣的问题。我们想要估计一个集合的基数而不需要存储每一个项目(通常位图/位集是一个很好的方法)。一个非常好的算法是所谓的 HyperLogLog 随机算法(更多信息请参见此处 http://antirez.com/news/75)。

这里的问题是，您只能将集合合并为UNION，所以基本上它是一个OR 组合。

实际上，我们不仅希望将集合与 OR 组合，而且还希望将其与 AND 组合。我们甚至想结合这些操作。

示例:set1 和(set2 或 set3)或(set4 和 set5)

每个集合的基数可能在数百万范围内。每个值的大小为 128 位。

每个集合都可以用任何方式表示，例如“HLL、布隆过滤器、普通列表或这些的组合”。该算法必须使用可行的空间量在尽可能短的时间内执行。

有什么想法吗？

Answer 1

这个确切的问题是 https://pdfs.semanticscholar.org/5da8/bf81712187712aed159aed62e38fb012872e.pdf 的主题.他们的建议是使用布隆过滤器。

联合的布隆过滤器是布隆过滤器的按位或。交集的布隆过滤器是布隆过滤器的按位与。因此，您可以轻松生成所需操作的布隆过滤器。

他们的定理 1 允许您根据布隆过滤器中设置的位数来估计集合的大小。