HyperLogLog交叉口:为什么不使用min？

Question

在两个兼容的HyperLogLog对象之间进行联合时，只需使用最大桶即可完成不引入任何新错误的无损联合：

Union.Bucket[i] = Max(A.Bucket[i], B.Bucket[i])

但是，在执行交叉时，您必须使用包含排除原则：

IntersectionCountEstimate = A.CountEstimate() + B.CountEstimate() - Union.CountEstimate()

为什么使用最小桶值不能作为有效的交叉口工作？

Intersection.Bucket[i] = Min(A.Bucket[i], B.Bucket[i])

Answer 1

原因是HyperLogLog统计数据的两个实例之间的关系不是很直观：

考虑来自不同的HyperLogLog结构A和B的两个对应的桶Ai和Bi (它们具有相同的桶数并使用相同的散列函数)，为了简单起见，假设A和B中的数据是从相同的分布中独立提取的。让我们假设我们首先绘制A的所有元素，然后再为B绘制元素。

对于我们观察到的到达Bi的每一个元素，A和B的交集中的概率是多少，即它已经在Ai中的概率是多少？那要看情况了--艾有多“饱”？如果Ai是完全“满”的(即，Ai包含“从分布中可以到达Ai的所有元素)，则概率为1。在这种情况下，Ai和Bi的交集的基数确实是Bi的基数。然而，艾是“满”的，所以交集比Bi的基数小得多。