1. 编程圈首页
  2. 文库
  3. 后端开发

基数估计方法


在之前的文章,Cardinality Counting中,我们介绍的方法,都是可以精确统计基数的。但是,在现在动辄TB、PB级数据量的情况下,无论是BTree还是bitmap,都有很多缺陷,并且精确性这一优势也被海量数据的前提所抵消(想象一下,统计uv时,100000000和100000001有区别吗)。

相反的,我们可以采用一些基于概率的方法,在误差可控的前提下,对基数做出合理的估计。

目前,最常用的基数估计方法,是HyperLogLog(HLL)。

算法思想

HLL算法的思想其实是基于LogLog Counting(LLC),论文详见2003年的《Loglog Counting of Large Cardinalities》。下面简单介绍一下其基本思想。

首先,我们对每一个元素用适当的哈希算法进行哈希(结果均匀,碰撞可以忽略不计)得到一个二进制01序列。对每一个元素,统计其由低到高,第一个出现1的bit位置,记为m。遍历所有的元素,得到m的最大值M,则可以用2^M来估计基数n的大小。

直观上讲,如果一个集合中元素的个数越多,则其中元素哈希后得到的01序列,第一个1出现的位置的最大值M也会越大,所以用2^M来估计n似乎是合理的。

但是,为什么是2^M,而不是2xM或者3^M呢?

概率分析

这其中,有一些概率论方面的推理:

由于哈希算法的良好特性,则每一个元素哈希后的01序列都可以看做一次不断抛硬币过程,正面为1,反面为0。不断抛硬币直到得到一个正面的过程,就是一个伯努利过程。

那么考虑如下两个问题:

1. 进行n次伯努利过程,抛硬币的次数均不大于k的概率
2. 进行n次伯努利过程,至少有一个抛硬币次数等于k的概率

分析过程如下:

1. 针对一次伯努利过程,
    p(X<=k) = 1 - p(X>k),p(n>k)表示前k次的结果都是反面,
所以
    p(X<=k) = 1 - p(X>k) = 1 - (1/2)^k
那么对于n次伯努利过程,第一个问题的概率就是
    pn(X<=k) = (1-(1/2)^k)^n
2. 概率论教导我们,“至少”=1-“都不”。
    pn'(X==k) = 1 - pn(X!=k) = 1-(1-P(X==k))^n
    = 1 - (1-(1/2)^k)^n

当n<<2^k时,pn’(X==k)≈0。

当n>>2^k时,pn(X<=k)≈0。

如果我们取k为这n次伯努利过程中抛掷硬币次数的最大值M,那么我们将发现,理应,pn’(X==M) >> 0且pn(X<=M) >> 0。所以n<<2^m和n>>2^M都将不成立。那么,用2^M作为n的一个粗略估计就是恰当。

当然,为了减少偶然因素的影响,LLC还使用了分桶平均的策略;另外,为了实现无偏的估计,还是用了偏差修正系数。不过这些都不影响其最基础的思想来源于上面的伯努利过程。

LLC与HLL

LLC的空间复杂度仅有O(log(logNmax)),并且非常易于合并(分桶比较记录值得大小,去max即可)。

HLL在LLC的基础上做了进一步的改进,使得其估计误差更小更稳定。因此,在海量数据统计领域,HLL获得了广泛的应用。

目前,redis中内置了HLL的实现(PFADD, PFCOUNT, PFMERGE),用12K内存,即可统计接近2^64个不同元素的基数,可以说是非常强大了。此外,postgresql也提供了扩展插件用于支持HLL。

发布者:编程圈,转转请注明出处:https://www.bianchengquan.com/article/68014.html

发表评论

登录后才能评论