解读Cardinality Estimation算法（第四部分：HyperLogLog Counting）

骑猪看日落 2022-06-14 01:45 191阅读 0赞

在[前一篇文章][Link 1]中，我们了解了LogLog Counting。LLC算法的空间复杂度为O(log2(log2(Nmax)))，并且具有较高的精度，因此非常适合用于大数据场景的基数估计。不过LLC也有自己的问题，就是当基数不太大时，估计值的误差会比较大。这主要是因为当基数不太大时，可能存在一些空桶，这些空桶的ρmaxρmax为0。由于LLC的估计值依赖于各桶ρmax的几何平均数，而几何平均数对于特殊值（这里就是指0）非常敏感，因此当存在一些空桶时，LLC的估计效果就变得较差。

这一篇文章中将要介绍的HyperLogLog Counting及Adaptive Counting算法均是对LLC算法的改进，可以有效克服LLC对于较小基数估计效果差的缺点。

--------------------

# **评价基数估计算法的精度** #

首先我们来分析一下LLC的问题。一般来说LLC最大问题在于当基数不太大时，估计效果比较差。上文说过，LLC的渐近标准误差为![这里写图片描述][SouthEast]，看起来貌似只和分桶数m有关，那么为什么基数的大小也会导致效果变差呢？这就需要重点研究一下如何评价基数估计算法的精度，以及“渐近标准误差”的意义是什么。

## **标准误差** ##

首先需要明确标准误差的意义。例如标准误差为0.02，到底表示什么意义。

![这里写图片描述][SouthEast 1]  
![这里写图片描述][SouthEast 2]

## **组合计数与渐近分析** ##

![这里写图片描述][SouthEast 3]

# **Adaptive Counting** #

Adaptive Counting（简称AC）在“Fast and accurate traffic matrix measurement using adaptive cardinality counting”一文中被提出。其思想也非常简单直观：实际上AC只是简单将LC和LLC组合使用，根据基数量级决定是使用LC还是LLC。具体是通过分析两者的标准差，给出一个阈值，根据阈值选择使用哪种估计。

## **基本算法** ##

![这里写图片描述][SouthEast 4]  
![这里写图片描述][SouthEast 5]

## **误差分析** ##

因为AC只是LC和LLC的简单组合，所以误差分析可以依照LC和LLC进行。值得注意的是，当β<0.051时，LLC最大的偏差不超过0.17%，因此可以近似认为是无偏的。

# **HyperLogLog Counting** #

HyperLogLog Counting（以下简称HLLC）的基本思想也是在LLC的基础上做改进，不过相对于AC来说改进的比较多，所以相对也要复杂一些。本文不做具体细节分析，具体细节请参考“HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm”这篇论文。

## **基本算法** ##

HLLC的第一个改进是使用调和平均数替代几何平均数。注意LLC是对各个桶取算数平均数，而算数平均数最终被应用到2的指数上，所以总体来看LLC取得是几何平均数。由于几何平均数对于离群值（例如这里的0）特别敏感，因此当存在离群值时，LLC的偏差就会很大，这也从另一个角度解释了为什么n不太大时LLC的效果不太好。这是因为n较小时，可能存在较多空桶，而这些特殊的离群值强烈干扰了几何平均数的稳定性。

因此，HLLC使用调和平均数来代替几何平均数，调和平均数的定义如下：

![这里写图片描述][SouthEast 6]

## **偏差分析** ##

![这里写图片描述][SouthEast 7]

## **分段偏差修正** ##

![这里写图片描述][SouthEast 8]

# **小结** #

本文首先介绍了基数估计算法标准误差的意义，并据此说明了为什么LLC在基数较小时效果不好。然后，以此介绍了两种对LLC的改进算法：HyperLogLog Counting及Adaptive Counting。到此为止，常见的四种基数估计算法就介绍完了。

[Link 1]: http://blog.csdn.net/baidu_37107022/article/details/72885628
[SouthEast]: /images/20220614/d546fee34b0640398a5b64a4aa481bf2.png
[SouthEast 1]: /images/20220614/3e2b7fd1ccc249bbaca6bfae7c9323e8.png
[SouthEast 2]: /images/20220614/ebcedef1856b446bb853eec50812978c.png
[SouthEast 3]: /images/20220614/ec697abbfe5744158eed893824457475.png
[SouthEast 4]: /images/20220614/0fa6446f2e9e4e989104c1551d0b56ff.png
[SouthEast 5]: /images/20220614/a905df732558491f91fcedeb69417df9.png
[SouthEast 6]: /images/20220614/d39e469a513748ca90c7f37475e0801c.png
[SouthEast 7]: /images/20220614/ead50f5f941a45c093de0331b32e20e7.png
[SouthEast 8]: /images/20220614/ab4e1b0ec48a4fc8a33203755101cbb1.png