hyperloglog算法一直困扰着我的是它对密钥散列的依赖。我的问题是，本文似乎假设每个分区上的数据都是完全随机分布的，但是在经常使用的上下文（mapreduce样式的作业）中，事情通常是按它们的哈希值分布的，因此所有重复的键都将在同一个分区上。对我来说，这意味着我们实际上应该添加hyperloglog生成的基数，而不是使用某种平均技术（在这种情况下，我们通过散列hyperloglog散列的相同内容进行分区）。
所以我的问题是：这是hyperloglog的真正问题还是我没有足够详细地阅读这篇文章
1条答案
按热度按时间n3h0vuf21#
如果对这两个任务都使用非独立的哈希函数，这将是一个真正的问题。
假设分区通过第一个
b散列值的位。如果对分区和hyperloglog使用相同的哈希函数，算法仍能正常工作，但会牺牲精度。实际上，这相当于m/2^b桶（log2m'=log2m-b），因为b位总是一样的，所以log2m-b位将用于选择hll桶。