LogLog 算法
在上一篇 HyperLogLog 算法（一）——Bitmap 与 LinearCounting中介绍了 Linear Counting 的算法，缺点在于从渐进复杂性的角度看，空间复杂度仍为 O(Nmax)，其空间利用效率依旧不高。基于 Linear Counting 算法，LogLog Counting 算法的空间复杂度仅有 O(log2(log2(Nmax)))，使得通过KB级内存估计数亿级别的基数成为可能。
考虑如下伯努利过程 A ：不停抛掷一枚均匀硬币，出现反面则继续抛掷，出现正面则停止抛掷，抛掷出的反面次数为 \( k\) ，那么可以容易得出：
\[ P_A(x=k)=(\frac{1}{2})^k \quad k=0,1,2,3,4,5,…\]
考虑如下问题 1：
进行 \( n\) 次 A 过程，每一次过程的总抛掷次数都不大于某常数 \( k_{max}\) 的概率是多少？容易得出：
\[ P_1(x\leq k_{max}) = [1-(\frac{1}{2})^{k_{max}}]^n\]
进行 \( n\) 次 A 过程，至少有一次过程，其抛掷次数等于常数 \( k_{max}\) 的概率是多少？容易得出：
\[ P_2(x = k_{max}) = 1 – P_1(x\leq k_{max} – 1)=1-[1-(\frac{1}{2})^{k_{max}-1}]^n\]
考虑两种情况：
1.
\[ n >> 2^{k_{max}}, \quad P_1(x \leq k_{max}) \approx 0\]
2.
\[ n << 2^{k_{max}}, \quad P_2(x = k_{max}) \approx 0\]
说明以上两种情况下，上述两种情况的概率都接近于\( 0\)，所以可以考虑 \( 2^{k_{max}}\)为 \( n\) 的一个估计。（当我们划定了一个常数\(k_{max}\)线后，这个线往往是当前所有实验结果的最大值，也就是认为每一次实验的抛掷次数小于或者等于这个线，我们可以断定n不可能大大于\(2^{k_{max}}\)或者n小小于\(2^{k_{max}}\)，尤其是当允许的误差较大时更有说服力。）
在 Hash 的过程中，如果哈希的结果是固定长度，且哈希结果有比较好的均匀性，哈希函数不产生碰撞，可以认为每一个计数的元素进行哈希后的值转化为2进制串的结果是一个伯努利过程。\( k_{max}\) 为2进制串从最高位开始第一个 1 的位置，\( 2^{k_{max}}\) 为总基数\( n\) 的一个估计。
Bucket
只使用单一的估计量会由于偶然性造成比较大的误差，LogLog Counting采用分桶多次试验的方法减少误差。将比特长度为\( L\) 哈希空间分为\( 2^l = m\) 份，每一份被称为一个 bucket。哈希值的前\( l\)位作为 bucket 的编号，后\( L-l\) 位为哈希值，由于伯努利过程 A 前后独立且从试验任何次数开始都是同参数的伯努利过程，所以后\( L-l\)位也可以用于 LogLog Counting 算法进行参数估计。记录在第\( i\)
个 bucket 中最大的第一个 1 的位置\( M_i\)，可以得到分桶平均后的估计为：
\[ \hat{n}=2^{\frac{\sum_i M_i}{m}}\]
Bias
在上面 LogLog 算法以及 Bucket 的误差平均得到的估计值并不是通过严格的数学推导得到的无偏估计，如何得到无偏估计，参见论文：Loglog Counting of Large Cardinalities
数学部分比较复杂，通过运用 Index Generation Function 以及 Poissonization 的方法得到估计量的 Poisson 期望和方差，最后通过 Depoissonization 得到一个渐进无偏估计量。
\[ \hat{n}=\alpha_m 2^{\frac{\sum_i M_i}{m}}\]
其中
\[ \alpha_m =[\Gamma(-\frac{1}{m})\dfrac{1-2^{\frac{1}{m}}}{log2}]^{-m}\]
其标准差为
\[ StdError(\dfrac{\hat{n}}{n}) \approx \dfrac{1.30}{\sqrt{m}}\]
即如果要把误差控制在 \( epsilon\) 之内，那么必须满足
\[ m>(\dfrac{1.3}{\epsilon})^2\]
Evaluation
在性能上主要从内存使用以及合并性能上进行分析。
假设哈希空间长度为 \( L\)，桶空间长度为\( l\)。每个桶需要 \( log_2 L\) 的空间存储\( k_{max}\)，所以需要的字节数为
\[ log_2 L * 2^l / 8\]
误差为：
\[ \dfrac{1.3}{\sqrt{2^l}}\]
在合并时，只需要取相同桶中编号最大值重新合并即可。
Adaptive Counting
从算法的标准差可以知道，当桶空间长度 \( l\)比较小时，算法的误差会比较大，而由于之前讨论中，LC 算法当基数计数量比较大时，渐进复杂度会不理想，但是计数量小时，复杂度可以接受，而 LLC 算法在基数计数量大时，会节省很多内存空间。所以将 LC 与 LLC 结合使用，便是 Adaptive Counting。
LC 的标准差为：
\[ SE_{lc}(\dfrac{\hat{n}}{n})=\dfrac{\sqrt{e^t-t-1}}{t\sqrt{m}}\]
LLC 的标准差为：
\[ SE_{llc}(\dfrac{\hat{n}}{n})=\dfrac{1.30}{\sqrt{m}}\]
二者相等时：
\[ t\approx 2.89\]
空桶率 \( \beta\)满足：
\[ \beta = e^{-t} \approx 0.051\]
所以 Adaptive Counting 的选择如下：
\begin{align*}\hat{n}=\left\{ \begin{matrix} \alpha_m m2^{\frac{\sum{M}}{m}} \quad if \quad 0 \leq \beta < 0.051 \\\\ -mlog(\beta) \quad if \quad 0.051 \leq \beta \leq 1 \end{matrix} \right.\end{align*}
HyperLogLog
HyperLogLog 算法最大的区别在于，由 LLC 中不同的桶取算数平均数改成了取调和平均数。在 LLC 中取算术平均数，再后面进行指数运算后实际上是取了几何平均数。几何平均数对于离群值十分敏感，在基数总数比较小时，可能会存在比较多的空桶，会干扰几何平均数的稳定性。
在HyperLogLog中，\( \hat{n}\)估计公式为
\[ \hat{n}=\dfrac{\alpha_m m^2}{\sum 2^{-M}}\]
其中，\( \alpha_m\) 为最后进行无偏渐进化的参数：
\[ \alpha_m=(m\int _0^\infty (log_2(\frac{2+u}{1+u}))^m du)^{-1}\]
其标准差为：
\[ StdError(\hat{n}/n) \approx \dfrac{1.04}{\sqrt{m}}\]
小于 LLC 算法的标准差