大数据唯一值总数估计——HyperLogLog 算法

引言


HyperLogLog算法经常在数据库中被用来统计某一字段的Distinct Value(下文简称DV),比如Redis的HyperLogLog结构,出于好奇探索了一下这个算法的原理,无奈中文资料很少,只能直接去阅读论文以及一些英文资料,总结成此文。

介绍


HyperLogLog算法来源于论文《HyperLogLog the analysis of a near-optimal cardinality estimation algorithm》(下载地址见文末的参考文献),可以使用固定大小的字节计算任意大小的DV,本文先介绍该算法的原理,然后通过剖析stream-lib(一个Java实现的实时计算库)对此算法的实现来进一步理解该算法。本文追求直观理解,所以不会太过于纠结一些数学细节,如果关心数学细节的话可以直接去看论文,论文里会有具体的证明。

基数


基数就是指一个集合中不同值的数目,比如[a,b,c,d]的基数就是4,[a,b,c,d,a]的基数还是4,因为a重复了一个,不算。基数也可以称之为Distinct Value,简称DV。下文中可能有时候称呼为基数,有… Read the rest