hadoop - MapReduce 上的 HyperLogLog 正确性

Question

关于 HyperLogLog 算法一直困扰我的一点是它对 key 散列的依赖。我遇到的问题是，这篇论文似乎假设我们在每个分区上都有一个完全随机的数据分布，但是在它经常使用的上下文中(MapReduce 风格的作业)，东西通常是按它们的哈希值分布的，所以所有重复的键都会在同一个分区上。对我来说，这意味着我们实际上应该添加 HyperLogLog 生成的基数，而不是使用某种平均技术(在我们通过散列与 HyperLogLog 散列相同的东西来分区的情况下)。

所以我的问题是:这是 HyperLogLog 的真正问题还是我没有足够详细地阅读论文

Answer 1

如果您对两个任务都使用非独立的哈希函数，这将是一个真正的问题。

假设分区根据散列值的前 b 位决定节点。如果分区和 HyperLogLog 使用相同的哈希函数，算法仍然可以正常工作，但会牺牲精度。实际上，它等同于使用 m/2^b 桶 (log2m' = log2m-b)，因为第一个 b 位总是相同的，因此只有 log2m-b 位将用于选择 HLL 桶。