Hyperloglog基数统计

发布于 2019-10-15  35 次阅读


转载自:https://www.jianshu.com/p/0cf5f8bc1079

数据量一大,连统计基数也成了一个麻烦事。在使用kylin的时候,遇到对度量值进行基数统计,使用的是Hyperloglog算法,占用内存小,误差小,实乃不错的方法,但查阅网上的资料与内容,感觉未能理解的太明白。经过一番折腾,自己给整理出一个版本出来。

算法的论文是《HyperLogLog the analysis of a near-optimal cardinality estimation algorithm》,可以在谷歌学术上下载下来看看。具体论文的理论推导不详细介绍,简述下其思想核心。

在理想状态下,将一堆数据hash至[0,1],每两点距离相等,1/间距 即可得出这堆数据的基数。然而实际情况往往不能如愿,只能通过一些修正不断的逼近这个实际的基数。实际采用的方式一是分桶,二是取kmax。分桶将数据分为m组,每组取第k个位置的值,所有组中得到最大的kmax,(k-1)/kmax得到估计的基数。

HLL算法的另一个主观上的理解可以用抛硬币的方式来理解。以当硬币抛出反面为一次过程,当你抛n次硬币全为正面的概率为1/2^n。当你经历过k(k很大时)次这样的过程,硬币不出现反面的概率基本为0。假设反面为1,正面为0,每抛一次记录1或者0,当记录上显示为0000000...001时,这种可以归结为小概率事件,基本不会发生。转换到基数的想法就是,可以通过第一个1出现前0的个数n来统计基数,基数大致为2^(n+1)时。硬币当中可以统计为(1/2*1+1/4*2+1/8*3...),大致可以这么去想。

论文当中对于算法的具体实现过程如下:

1.hash成32位的值

2.初始化m个登记表

3.计算得出每组最大的leadingzeros

4.计算基数并做调整。

国外友人实现的一个页面demo  http://content.research.neustar.biz/blog/hll.html

java代码的实现可参考 https://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/cardinality/HyperLogLog.java

 


公交车司机终于在众人的指责中将座位让给了老太太