解读Cardinality Estimation算法（第三部分：LogLog Counting）

亦凉 2022-06-14 01:44 248阅读 0赞

[上一篇文章][Link 1]介绍的Linear Counting算法相较于直接映射bitmap的方法能大大节省内存（大约只需后者1/10的内存），但毕竟只是一个常系数级的降低，空间复杂度仍然为O(Nmax)O(Nmax)。而本文要介绍的LogLog Counting却只有O(log2(log2(Nmax)))O(log2(log2(Nmax)))。例如，假设基数的上限为1亿，原始bitmap方法需要12.5M内存，而LogLog Counting只需不到1K内存（640字节）就可以在标准误差不超过4%的精度下对基数进行估计，效果可谓十分惊人。

本文将介绍LogLog Counting。

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

# **简介** #

LogLog Counting（以下简称LLC）出自论文“Loglog Counting of Large Cardinalities”。LLC的空间复杂度仅有O(log2(log2(Nmax)))O(log2(log2(Nmax)))，使得通过KB级内存估计数亿级别的基数成为可能，因此目前在处理大数据的基数计算问题时，所采用算法基本为LLC或其几个变种。下面来具体看一下这个算法。

# **基本算法** #

## **均匀随机化** ##

与LC一样，在使用LLC之前需要选取一个哈希函数H应用于所有元素，然后对哈希值进行基数估计。H必须满足如下条件（定性的）：

1、H的结果具有很好的均匀性，也就是说无论原始集合元素的值分布如何，其哈希结果的值几乎服从均匀分布（完全服从均匀分布是不可能的，D. Knuth已经证明不可能通过一个哈希函数将一组不服从均匀分布的数据映射为绝对均匀分布，但是很多哈希函数可以生成几乎服从均匀分布的结果，这里我们忽略这种理论上的差异，认为哈希结果就是服从均匀分布）。

2、H的碰撞几乎可以忽略不计。也就是说我们认为对于不同的原始值，其哈希结果相同的概率非常小以至于可以忽略不计。

3、H的哈希结果是固定长度的。

以上对哈希函数的要求是随机化和后续概率分析的基础。后面的分析均认为是针对哈希后的均匀分布数据进行。

## **思想来源** ##

下面非正式的从直观角度描述LLC算法的思想来源。

设a为待估集合（哈希后）中的一个元素，由上面对H的定义可知，a可以看做一个长度固定的比特串（也就是a的二进制表示），设H哈希后的结果长度为L比特，我们将这L个比特位从左到右分别编号为1、2、…、L：

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

又因为a是从服从均与分布的样本空间中随机抽取的一个样本，因此a每个比特位服从如下分布且相互独立。

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

下面解释为什么可以这样估计。注意如下事实：

由于比特串每个比特都独立且服从0-1分布，因此从左到右扫描上述某个比特串寻找第一个“1”的过程从统计学角度看是一个伯努利过程，例如，可以等价看作不断投掷一个硬币（每次投掷正反面概率皆为0.5），直到得到一个正面的过程。在一次这样的过程中，投掷一次就得到正面的概率为

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

## **分桶平均** ##

上述分析给出了LLC的基本思想，不过如果直接使用上面的单一估计量进行基数估计会由于偶然性而存在较大误差。因此，LLC采用了分桶平均的思想来消减误差。具体来说，就是将哈希空间平均分成m份，每份称之为一个桶（bucket）。对于每一个元素，其哈希值的前k比特作为桶编号，

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

## **偏差修正** ##

上述经过分桶平均后的估计量看似已经很不错了，不过通过数学分析可以知道这并不是基数n的无偏估计。因此需要修正成无偏估计。这部分的具体数学分析在“Loglog Counting of Large Cardinalities”中，过程过于艰涩这里不再具体详述，有兴趣的朋友可以参考原论文。这里只简要提一下分析框架：

首先上文已经得出：

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

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

不加证明给出如下结论：

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

# **算法应用** #

## **误差控制** ##

在应用LLC时，主要需要考虑的是分桶数m，而这个m主要取决于误差。根据上面的误差分析，如果要将误差控制在ϵ之内，则：

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

## **内存使用分析** ##

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

## **合并** ##

与LC不同，LLC的合并是以桶为单位而不是bit为单位，由于LLC只需记录桶的ρmax，因此合并时取相同桶编号数值最大者为合并后此桶的数值即可。

# **小结** #

本文主要介绍了LogLog Counting算法，相比LC其最大的优势就是内存使用极少。不过LLC也有自己的问题，就是当n不是特别大时，其估计误差过大，因此目前实际使用的基数估计算法都是基于LLC改进的算法，这些改进算法通过一定手段抑制原始LLC在n较小时偏差过大的问题。后面要介绍的HyperLogLog Counting和Adaptive Counting就是这类改进算法。

[Link 1]: http://blog.csdn.net/baidu_37107022/article/details/72885628
[SouthEast]: /images/20220614/14a17810433541af8403c315add37b1e.png
[SouthEast 1]: /images/20220614/d32051dae10441a49b6a532884448eda.png
[SouthEast 2]: /images/20220614/871d4dffcfd341cba2fb51bf58b35c9f.png
[SouthEast 3]: /images/20220614/b0e8a12695e04952a98722e4175c88e3.png
[SouthEast 4]: /images/20220614/9a6ea0996b394f1dbd632a31b63cfba7.png
[SouthEast 5]: /images/20220614/53e00c093a4c4c5794cb60ae4f95a216.png
[SouthEast 6]: /images/20220614/ccf9c425bd004abe87a779208e450b01.png
[SouthEast 7]: /images/20220614/3eb3f4d31d9f4322a9bfa7e82da2996d.png