database - HyperLogLog 算法如何工作？

Question

我最近在业余时间学习了不同的算法，我遇到了一个看起来非常有趣的算法，它被称为 HyperLogLog 算法 - 它估计列表中有多少个独特的项目。

这对我来说特别有趣，因为它让我回到了 MySQL 时代，当时我看到了“基数”值(直到最近我一直认为它是计算出来的，而不是估计的)。

所以我知道如何在 O(n) 中编写一个算法来计算数组中有多少个唯一项。我用 JavaScript 写了这个:

function countUniqueAlgo1(arr) {
    var Table = {};
    var numUnique = 0;
    var numDataPoints = arr.length;
    for (var j = 0; j < numDataPoints; j++) {
        var val = arr[j];
        if (Table[val] != null) {
            continue;
        }
        Table[val] = 1;
        numUnique++;
    }
    return numUnique;
}

但问题是我的算法虽然 O(n)，但使用了大量内存(将值存储在 Table 中)。

我一直在阅读 this paper关于如何在 O(n) 时间内使用最少的内存计算列表中的重复项。

它解释了通过对位​​进行散列和计数或某种可以在一定概率内(假设列表均匀分布)估计列表中唯一项的数量。

我读过这篇论文，但我似乎无法理解它。有人可以给出更外行的解释吗？我知道哈希是什么，但我不明白他们是如何在这个 HyperLogLog 算法中使用的。

Answer 1

此算法背后的主要技巧是，如果您观察随机整数流，看到一个二进制表示以某个已知前缀开头的整数，则该流的基数更有可能是 2^(大小前缀)。

也就是说，在随机整数流中，约 50% 的数字(二进制​​)以“1”开头，25% 以“01”开头，12.5% 以“001”开头。这意味着，如果您观察一个随机流并看到“001”，则该流的基数为 8 的可能性更高。

(前缀“00..1”没有特殊含义。它的存在只是因为在大多数处理器中很容易找到二进制数中的最高有效位)

当然，如果你只观察一个整数，这个值错误的可能性就很高。这就是为什么该算法将流分成“m”个独立子流并保持每个子流的可见“00...1”前缀的最大长度。然后，通过取每个子流的平均值来估计最终值。

这就是这个算法的主要思想。有一些遗漏的细节(例如，对低估计值的更正)，但在论文中都写得很好。对不起，糟糕的英语。