hadoop - mapreduce 上的 HyperLogLog 正确性

Question

HyperLogLog 算法一直困扰着我的是它对密钥哈希的依赖。我遇到的问题是该论文似乎假设我们在每个分区上都有完全随机的数据分布，但是在经常使用它的上下文中（MapReduce 样式作业），事物通常按其哈希值分布，因此所有重复的键都会在同一个分区上。对我来说，这意味着我们实际上应该添加由 HyperLogLog 生成的基数，而不是使用某种平均技术（在我们通过散列与 HyperLogLog 散列相同的东西进行分区的情况下）。

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

Answer 1

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

假设分区通过b散列值的第一位决定节点。如果分区和 HyperLogLog 使用相同的哈希函数，算法仍然可以正常工作，但会牺牲精度。在实践中，它相当于使用m/2^b存储桶 (log2m' = log2m-b)，因为第一位b将始终相同，因此只有log2m-b位将用于选择 HLL 存储桶。