data-structures - 合并 uniq 计数器，概率数据结构

Question

有两套1 2 3和独特的项目。3 432

现在让我们计算合并集中的唯一项目。如果我们只是总结计数器3 + 2 = 5，那将是错误的（应该是uniq(1 2 3 3 4) = 4）。

有没有办法只使用计数器来做到这一点？对于每个计数器，可以使用一些额外的常量内存数据结构来表示原始集合，小错误也可以，假设 95% 的准确度是可以的。

我知道有使用很少内存（HyperLogLog）的概率唯一计数器。但是有没有办法合并两个这样的概率计数器？

Answer 1

是的，HyperLogLog 实际上非常自然地允许合并，并且大多数实现都包括合并。简而言之，要将两个 HyperLogLog 结构 A 和 B 合并为一个新的 C，取每个桶对的最大值 C[i] = max(A[i],B[i])。