algorithm - 找出((A相交B)并集C)相交D)的基数的有效(恒定空间或次线性空间)方法？

Question

我目前正在使用 hyperloglog 来估计集合的基数(唯一项的数量)

计算 2 个集合的并集的基数和 2 个集合的交集的基数 (|A intersect B| = |A| + |B| - |A union B|) 非常简单

但我没能完全找到一种方法将并集和交集的运算符链接在一起(注意:只允许计算基数而不是交集的 hyperloglog 的方法，也就是说，可以通过 A union B 得到一个新的 hyperloglog但不是 A intersect B )。

是否有替代算法可以估计链式并集和交集结果的基数？

Answer 1

顽固地使用 bool 代数可以达到目的，但如果选择性较低，您可能会对质量不满意。

|((A n B) u C) n D| =
|(A n B) u C| + |D| - |(A n B) u C u D| =
|(A u C) n (B u C)| + |D| - |(A u C u D) n (B u C u D)| =
|A u C| + |B u C| - |A u B u C| + |D| - |A u C u D| - |B u C u D| + |A u B u C u D|

你可能应该仔细检查我的数学。