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).

我一直在阅读这篇论文,关于如何在O(n)时间内使用最少的内存来计算列表中的重复项.

它解释了通过散列和计数比特或某事物,可以在一定概率内(假设列表均匀分布)估计列表中的唯一项目的数量.

我读过这篇论文,但我似乎无法理解它.有人能给出更多非专业人士的解释吗？我知道什么是哈希,但我不明白它们如何在这个HyperLogLog算法中使用.

Answer 1

这个算法背后的主要技巧是,如果你观察一个随机整数流,看到一个二进制表示以某个已知前缀开始的整数,那么流的基数是2 ^(前缀的大小)的可能性更高. .

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

(前缀"00..1"没有特殊含义.只是因为在大多数处理器中很容易找到二进制数中最重要的位)

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

这是该算法的主要思想.有一些缺失的细节(例如,对低估计值的修正),但这一切都写得很好.抱歉可怕的英语.

Answer 2

HyperLogLog是概率数据结构.它计算列表中不同元素的数量.但是与直接的方式相比(有一组和添加元素)它以近似的方式完成.

在了解HyperLogLog算法如何做到这一点之前,必须先了解为什么需要它.直截了当的问题是它消耗O(distinct elements)了空间.为什么这里有一个很大的O符号而不仅仅是不同的元素？这是因为元素可以具有不同的大小.一个元素可以是1另一个元素"is this big string".因此,如果你有一个巨大的列表(或大量的元素),它将需要很多内存.

概率计数

如何才能对一些独特元素进行合理估计？假设您有长度的字符串m它由{0, 1}概率相同.从零开始的概率是多少,有2个零,有k个零？它是1/2,1/4和1/2^k.这意味着如果您遇到了带有k零的字符串,那么您可以近似查看2^k元素.所以这是一个很好的起点.具有之间有均匀分布的元素的列表0和2^k - 1你可以指望零的二进制表示的最大前缀的最大数量,这会给你一个合理的估计.

问题是从0t 中均匀分布数字的假设2^k-1太难实现(我们遇到的数据通常不是数字,几乎从不均匀分布,可以在任何值之间.但是使用良好的散列函数,你可以假设输出位将是均匀分布的,大多数散列函数的输出介于0和之间2^k - 1(SHA1给出介于0和之间的值2^160).所以我们到目前为止所获得的是我们可以k通过仅存储来估计具有最大基数的唯一元素的数量一个大小的log(k)位数.缺点是我们的估计有很大的差异.我们几乎创造了1984年的概率计数纸(这个估算有点聪明,但我们仍然很接近).

双对数

在进一步研究之前,我们必须理解为什么我们的第一次估计并不那么好.其背后的原因是一个随机出现的高频0前缀元素会破坏一切.改进它的一种方法是使用许多散列函数,对每个散列函数计数max,最后将它们平均.这是一个很好的想法,它将改进估计,但LogLog论文使用了稍微不同的方法(可能是因为散列有点贵).

他们使用了一个哈希,但将其分为两部分.一个被称为桶(桶的总数2^x)和另一个 - 基本上与我们的哈希相同.我很难得到正在发生的事情,所以我将举一个例子.假设你有两个元素和你的哈希函数,它给出0了2^10生成2个值的值形式:344和387.你决定有16个水桶.所以你有了:

0101 011000  bucket 5 will store 1
0110 000011  bucket 6 will store 4

通过使用更多桶,可以减少方差(使用稍多的空间,但它仍然很小).使用数学技能,他们能够量化错误(即1.3/sqrt(number of buckets)).

HyperLogLog

HyperLogLog不会引入任何新想法,但主要使用大量数学来改进之前的估计.研究人员发现,如果从桶中删除30%的最大数字,则可以显着提高估算值.他们还使用另一种算法来平均数字.这篇论文很重要.

我想用最近的一篇论文来完成,该论文显示了hyperLogLog算法的改进版本(到目前为止我没有时间完全理解它,但也许以后我会改进这个答案).

Answer 3

直觉是如果你的输入是一组大的随机数(例如散列值),它们应该在一个范围内均匀分布.假设范围最多为10位,表示最大值为1024.然后观察最小值.假设它是10.然后基数估计约为100(10×100×1024).

当然,阅读论文了解真正的逻辑.

关于示例代码的另一个很好的解释可以在这里找到:
该死的算法:基数估计 - 尼克的博客