下面给出五种基数估计算法的估计效果和误差走势。如未特殊说明,实验分桶数均为\(2^{10}\),\(2^{12}\)和\(2^{16}\)。
ccard-lib中当单独使用Linear Counting时,采用bit为单位记录哈希结果。因此实际的精度为分桶数的8倍,例如\(2^{10}\)时,实际的精度为1024*8=8192。
Linear Counting(p=10)
Linear Counting(p=12)
Linear Counting(p=16)
Linear Counting误差(p=10)
Linear Counting误差(p=12)
Linear Counting误差(p=16)
如理论预期,由于Linear Counting的有效性取决于bitmap中存在空位置,当有位置留空时,估计效果还不错,但是当bitmap全满后,Linear Counting完全失效。Linear Counting的有效估计范围线性依赖于bitmap长度。
LogLog Counting(p=10)
LogLog Counting(p=12)
LogLog Counting(p=16)
LogLog Counting误差(p=10)
LogLog Counting误差(p=12)
LogLog Counting误差(p=16)
LogLog Counting的表现基本与理论相符,可以看到当基数不太大的时候,LogLog Counting误差非常大,这是因为LogLog Counting在基数较小的段存在一个很大的偏差。为了明确看到这个偏差,我们截取前十分之一放大,也就是1-100,000这一段的效果图:
LogLog Counting小基数区间(p=10)
LogLog Counting小基数区间(p=12)
LogLog Counting小基数区间(p=16)
可以很明显的看到估计值严重偏离基准,而且分桶数越多这个偏差反而越明显。
Adaptive Counting(p=10)
Adaptive Counting(p=12)
Adaptive Counting(p=16)
Adaptive Counting误差(p=10)
Adaptive Counting误差(p=12)
Adaptive Counting误差(p=16)
由于分别在基数较小和较大时使用Linear Counting和LogLog Counting,Adaptive Counting克服了两者的缺陷,属于比较稳定的基数估计方法。而且随着分桶数的增加,估计的偏差和方差均明显减小。
HyperLogLog Counting(p=10)
HyperLogLog Counting(p=12)
HyperLogLog Counting(p=16)
HyperLogLog Counting误差(p=10)
HyperLogLog Counting误差(p=12)
HyperLogLog Counting误差(p=16)
HyperLogLog Counting采用调和平均数取代LogLog Counting中的几何平均数,旨在减小离群点的影响,并且对Linear Counting转折阈值做了调整。从实验效果看,在分桶数较小时,改进效果并不明显,不过在\(2^{16}\)分桶下,整体偏差和稳定程度优于Adaptive Counting。
但是从误差图中可以看到,在200,000附近出现了一个明显的脉冲。其原因在Google关于HyperLogLog++ Counting的论文中5有分析,其主要是因为在Linear Counting刚转折后的一小段区域内存在一个偏差,HyperLogLog++ Counting的一个改进就是对这个区域的偏差进行了修正。
HyperLogLog++ Counting(p=10)
HyperLogLog++ Counting(p=12)
HyperLogLog++ Counting(p=16)
HyperLogLog++ Counting误差(p=10)
HyperLogLog++ Counting误差(p=12)
HyperLogLog++ Counting误差(p=16)
可以看到HyperLogLog++ Counting的效果非常令人失望,按论文中说法,HyperLogLog++ Counting应该比HyperLogLog Counting更准确,但实际效果不但整体偏差和方差变大,而且偏差修正的阈值明显有问题,导致一个非常明显的误差脉冲。
究其原因,个人认为HyperLogLog++ Counting中的偏差修正和转折阈值均是通过统计方法给出,并不是数学上的解析结果,因此对于不同的数据、不同的哈希可能并不通用。
为了更清楚对比五种算法的误差情况,下面给出五种算法的误差曲线叠加图,仍然是采用三个分桶数。
误差对比(p=10)
误差对比(p=12)
误差对比(p=16)
下面根据实验结果从个人角度给出一些基数估计算法的实践性建议,当然只代表个人意见,不同人对实验结果可能有不同解读。
[1] K.-Y. Whang, B. T. Vander-Zanden, and H. M. Taylor. A Linear-Time Probabilistic Counting Algorithm for Database Applications. ACM Transactions on Database Systems, 15(2):208-229, 1990.
[2] Marianne Durand and Philippe Flajolet. LogLog counting of large cardinalities. In ESA03, volume 2832 of LNCS, pages 605b 617, 2003.
[3] Min Cai, Jianping Pan, Yu K. Kwok, and Kai Hwang. Fast and accurate traffic matrix measurement using adaptive cardinality counting. In MineNet b 05: Proceedings of the 2005 ACM SIGCOMM workshop on Mining network data, pages 205b 206, New York, NY, USA, 2005. ACM.
[4] P. Flajolet, E. Fusy, O. Gandouet, and F. Meunier. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm. Disc. Math. and Theor. Comp. Sci., AH:127-146, 2007.
[5] HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm.
[6] Appendix to HyperLogLog in Practice: Algorithmic Engineering of a State of the Art Cardinality Estimation Algorithm.
来源: