简介

HyperLogLog 是一种具有不确定性（模糊数学）的数据结构，用于估计某个集合的基数。例如：某公司需要统计旗下多个产品的 MAU（月活跃用户数）等众多运营指标，但是不希望这些数据占用过多的空间，同时可以容忍很小范围内的统计误差，则可以考虑使用 Redis 中的 HyperLogLog。在 Redis 的实现中，HyperLogLog 的标准误差仅为 0.81%，且单个数据结构仅占用 12 KiB 的内存空间。

前置概念

• 寄存器：可视作总共可用的槽位，一般来说选取 2 的次方个寄存器。下文中假设总共有 $m = 2^n$ 个寄存器，每个寄存器为 $R_i$。
• 散列函数：将添加的元素映射到一个相对均匀分布的空间的函数，且映射后数据的位数是固定的。下文中记作 $h(v)$，$e$ 为元素。
• 首一位置函数：从最低位开始，计算连续 0 的个数，然后加一。下文中记作 $\rho(x)$。
• 调和平均数函数：$H(x_0, \cdots, x_{m-1})=m\left(\sum_{i=0}^{m-1}{x_i^{-1}}\right)^{-1}$。
• 估计常数：根据 $m$ 确定的一个估计常数 $\alpha_m$，此处不展开叙述。

操作与算法

初始化

1. 确定 $n$ 的大小。
2. 将所有寄存器置为 0。

时间复杂度：$O(m)$。

添加元素

1. 计算 $x = h(v)$。
2. 将 $x$ 中的 $n$ 位（例如最低的 $n$ 位）作为索引值 $i$，选取 $R_i$。
3. 将剩余的位数作为值 $w$。
4. 计算 $\rho(w)$。
5. 设置 $R_i \leftarrow \max\left\{R_i, \rho(w)\right\}$。

时间复杂度：$O(1)$。

估计基数

1. 计算 $H(R_0, \cdots, R_{m-1})$。
2. 查表得估计常数 $\alpha_m$。
3. 计算原始估计值 $E=\alpha_m m^2 H$。
4. 应用误差修正，修正后的基数估计值记作 $E^*$：
   • 若 $E < \frac{5}{2}m$，则 $E^*=m\log{\frac{m}{V}}$，其中 $V$ 是值为 0 的寄存器个数。
   • 若 $E > \frac{2^n}{30}$，则 $E^*=-2^n\log{\left(1-\frac{E}{2^n}\right)}$。
   • 否则，无需修正，$E^* = E$。

标准误差：$\sigma = \frac{1.04}{\sqrt{n}}$；时间复杂度：$O(m)$。

合并数据结构

假设有两个数据结构 $hll_1$ 和 $hll_2$，需要合并为 $hll_3$，则 $hll_3$ 中每个寄存器取值两者中较大的一个。

时间复杂度：$O(m)$

估计常数表

基础思想

• 首一位置（或者前导零）实际上和见过的元素数量相关联，因为首一位置大的元素更稀有。
• 分桶思想能有效减少误差，且不会增加添加元素操作的时间复杂度的数量级。
• 通过实验，会发现寄存器特征和实际的基数之间有一些特征，所以能通过一些 workarounds 修正估计的基数，使其更接近实际的基数。

参考文献

• https://arxiv.org/abs/2205.11327
• https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf