地图推理中的HyperLogLog正确性

Question

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

所以我的问题是:这是HyperLogLog的一个真正的问题，还是我没有足够详细地阅读报纸？

Answer 1

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

假设分区通过哈希值的第一个b位来决定节点。如果在分区和HyperLogLog中使用相同的哈希函数，算法仍将正常工作，但精度将被牺牲。实际上，这相当于使用m/2^b桶(log2m‘= log2m-b)，因为第一个b位总是相同的，所以只有log2m-b位才能选择HLL桶。