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

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

最佳答案

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

假设分区由散列值的第一个b位决定节点。如果对分区和HyperLogLog使用相同的哈希函数,该算法仍将正常运行,但会牺牲精度。实际上,这等效于使用m/2^b存储桶(log2m'= log2m-b),因为第一个b位将始终相同,因此仅log2m-b位将用于选择HLL存储桶。

09-27 06:45