关于HyperLogLog算法,一直困扰我的是它对键哈希的依赖。我遇到的问题是,该论文似乎假设我们在每个分区上都有完全随机的数据分布,但是在上下文中,它经常被使用(MapReduce样式作业),它们通常通过其哈希值来分布,因此所有重复的键都将在同一分区上。对我来说,这意味着我们实际上应该添加由HyperLogLog生成的基数,而不是使用某种平均技术(在通过对HyperLogLog哈希散列相同的事物进行分区的情况下)。
所以我的问题是:这是HyperLogLog的真正问题,还是我没有足够详细地阅读本文?
最佳答案
如果您对两个任务都使用非独立的哈希函数,这将是一个实际的问题。
假设分区由散列值的第一个b
位决定节点。如果对分区和HyperLogLog使用相同的哈希函数,该算法仍将正常运行,但会牺牲精度。实际上,这等效于使用m/2^b
存储桶(log2m'= log2m-b),因为第一个b
位将始终相同,因此仅log2m-b
位将用于选择HLL存储桶。