HyperLogLog 交集：为什么不使用 min？
HyperLogLog intersection: why not use min?
在两个兼容的 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])
原因是HyperLogLog统计的两个实例之间的关系不是很直观：
考虑来自单独的 HyperLogLog 结构 A 和 B（它们具有相同数量的桶并使用相同的哈希函数）的两个对应的桶 A[i] 和 B[i]，并且为了简单起见假设 A 中的数据和在 B 中独立地从相同的分布中抽取。假设我们首先为 A 绘制所有元素，然后才为 B 绘制元素。
对于我们观察到的每个到达 B[i] 的元素，它在 A 和 B 的交集中的概率是多少，即它已经在 A[i] 中的概率是多少？好吧，这取决于 - "full" 是 A[i] 的多少？如果 A[i] 完全 "full"（即 A[i] "contains" 分布中所有可以到达 A[i] 的元素），则概率为 1。在这种情况下， A[i] 和 B[i] 的交集的基数确实是 B[i] 的基数。然而，几乎从来没有 A[i] 是 "full" 的情况 - 所以交集比 B[i].
的基数小得多
在两个兼容的 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])
原因是HyperLogLog统计的两个实例之间的关系不是很直观：
考虑来自单独的 HyperLogLog 结构 A 和 B（它们具有相同数量的桶并使用相同的哈希函数）的两个对应的桶 A[i] 和 B[i]，并且为了简单起见假设 A 中的数据和在 B 中独立地从相同的分布中抽取。假设我们首先为 A 绘制所有元素，然后才为 B 绘制元素。
对于我们观察到的每个到达 B[i] 的元素，它在 A 和 B 的交集中的概率是多少，即它已经在 A[i] 中的概率是多少？好吧，这取决于 - "full" 是 A[i] 的多少？如果 A[i] 完全 "full"（即 A[i] "contains" 分布中所有可以到达 A[i] 的元素），则概率为 1。在这种情况下， A[i] 和 B[i] 的交集的基数确实是 B[i] 的基数。然而，几乎从来没有 A[i] 是 "full" 的情况 - 所以交集比 B[i].
的基数小得多