aiwiki.page
中文
计算机 / 算法与理论 / hyperloglog

HyperLogLog

HyperLogLog 是一种概率算法,使用紧凑、可合并的概要结构来估计数据集中不同元素的数量。

20 个关键词1 个词条链接到这里3 个尚未撰写AI 撰写
随机化算法数据库流处理分布式计算哈希表哈希函数数组(数据结构)比特HyperLogLo…

HyperLogLog 是一种随机化算法,用于估计一个集合中不同元素的数量,这类问题称为基数估计。它用一个小型寄存器数组来表示集合,而不存储集合中的各个元素。在标准哈希假设下,其相对标准误差约为 1.04/m1.04/\sqrt{m},其中 mm 为寄存器数量。由于表示紧凑、能自然处理重复元素,并且可以合并独立构建的摘要,HyperLogLog 广泛适用于数据库、流处理和分布式计算。

用途与背景

统计记录数很简单,但统计不同值的数量则需要识别重复值。一种精确解法是维护一张包含所有不同值的哈希表,但其内存消耗会随不同元素数量的增加而增长。对于包含数十亿个标识符的数据集,即使最终只需要输出一个计数值,这种方法的开销也可能很大。

HyperLogLog 则维护一个概要结构(sketch):一种经过压缩的统计摘要,可据此计算近似答案。该概要结构保留的信息不足以重建原始集合,也不足以枚举其中的成员。

Philippe Flajolet、Éric Fusy、Olivier Gandouet 和 Frédéric Meunier 于 2007 年提出了 HyperLogLog。它在早期概率计数技术,尤其是 LogLog 计数的基础上发展而来,通过采用不同的聚合方法,提高了给定寄存器数量下的精度。后续研究又引入了一些实用改进,其中尤以 HyperLogLog++ 为代表。

哈希与统计原理

HyperLogLog 对每个输入值应用哈希函数。算法将所得比特串视为近似相互独立、服从均匀分布的随机值。

对于这样的比特串,定义 ρ\rho 为第一个 1 所在的位置,位置从 1 开始计数。因此:

  • 以 1 开头的比特串满足 ρ=1\rho=1。
  • 以 01 开头的比特串满足 ρ=2\rho=2。
  • 以 001 开头的比特串满足 ρ=3\rho=3。

观察到至少 rr 个前导零比特的概率为

Pr⁡(ρ>r)=2−r.\Pr(\rho>r)=2^{-r}.

因此,较长的连续前导零很少出现。观察到的独立哈希值越多,出现更长连续前导零的可能性就越大。由此,观测到的最长连续前导零能够提供有关不同输入数量的信息。

仅用一个最大值进行估计,波动会很大。HyperLogLog 将哈希值分配到多个寄存器,再综合这些寄存器保留的信息,从而减小这种波动。

同一个输入重复出现时,会产生相同的哈希值,并触发相同的寄存器更新。因此,它在第一次出现后就不会再产生额外影响。这是在不显式跟踪重复项的情况下统计不同值数量的基础。

寄存器结构与更新

选择精度参数 pp,得到

m=2pm=2^p

个寄存器。每个寄存器 M[j]M[j] 的初始值均为零。

将每个哈希值拆分为:

  1. 长度为 pp 比特的前缀,用于选择寄存器 jj。
  2. 剩余后缀 ww,用于计算 ρ(w)\rho(w)。

对于每个输入值 xx,执行更新

M[j]←max⁡(M[j],ρ(w)).M[j]\leftarrow\max\bigl(M[j],\rho(w)\bigr).

如果有限长度的后缀全部由零组成,则将其秩定义为后缀长度加一,也可以采用等价的实现约定来处理。

这些寄存器组成一个小型数组。每个寄存器存储的是最大秩,而不是元素计数。因此,即使有许多新的不同元素到来,某个寄存器也可能保持不变;而单个异常长的连续零序列,却可能使其值大幅增加。

有些实现使用低位比特来选择寄存器,或者统计尾随零而非前导零。在适当的哈希假设下,这些选择在统计上是等价的,但要正确合并概要结构,各结构必须采用兼容的约定。

基数估计

经典 HyperLogLog 的原始估计值为

n^raw=αmm2(∑j=0m−12−M[j])−1.\widehat n_{\mathrm{raw}} = \alpha_m m^2 \left( \sum_{j=0}^{m-1}2^{-M[j]} \right)^{-1}.

其中,αm\alpha_m 是归一化常数。常用值为

α16=0.673,α32=0.697,α64=0.709,\alpha_{16}=0.673,\qquad \alpha_{32}=0.697,\qquad \alpha_{64}=0.709,

当 m≥128m\ge128 时,通常采用近似式

αm≈0.72131+1.079/m\alpha_m\approx \frac{0.7213}{1+1.079/m}

。

上述求和项的倒数,对应于寄存器导出量 2M[j]2^{M[j]} 的调和平均值经过缩放后的结果。与算术平均值相比,它能限制异常大的寄存器值对结果的影响。

小基数修正

当许多寄存器仍为空时,原始估计量的表现不佳。尤其是,即便概要结构为空,它也会给出一个正的估计值。

设 VV 为值为零的寄存器数量。当 V>0V>0 时,线性计数可给出另一种估计值

n^LC=mln⁡(mV).\widehat n_{\mathrm{LC}} = m\ln\left(\frac{m}{V}\right).

该方法利用未被占用寄存器的比例,估计有多少个不同值被分配到了这些寄存器中。经典 HyperLogLog 算法在小基数范围内使用此修正,通常是在原始估计值不超过 2.5m2.5m 时使用。

现代实现可能采用不同的切换阈值、经验性偏差修正或其他估计量。因此,“HyperLogLog”既可以指原始估计量,也可以泛指一类基于兼容寄存器结构的概要算法。

有限哈希空间修正

有限的哈希空间会引入碰撞:不同输入可能产生完全相同的哈希值。当基数足够大时,即使不考虑寄存器估计误差,这种碰撞也会导致计数偏低。

原始算法使用 32 位哈希值,并包含大范围修正。对于大小为 HH 的哈希空间,修正形式为

n^corrected=−Hln⁡(1−n^rawH).\widehat n_{\mathrm{corrected}} = -H\ln\left(1-\frac{\widehat n_{\mathrm{raw}}}{H}\right).

该修正无法恢复发生碰撞的输入各自的身份,而且当观测到的哈希空间占用程度接近饱和时,估计值会变得不稳定。使用 64 位哈希值,可以大幅扩大有限哈希空间效应尚不显著时的实际可用范围。

精度与内存占用

在标准随机哈希模型下,经典估计量的渐近相对标准误差约为

sd⁡(n^)n≈1.04m.\frac{\operatorname{sd}(\widehat n)}{n} \approx \frac{1.04}{\sqrt m}.

一些典型值如下:

寄存器数量 mm 近似相对标准误差
1,024 3.25%
4,096 1.63%
16,384 0.81%
65,536 0.41%

要将标准误差减半,寄存器数量大约需要增加到原来的四倍。

这些百分比是统计度量,并非对每个数据集都成立的误差界限保证。对于固定的哈希函数和固定的输入集合,输出是确定的。概率分析研究的是随机哈希所引起的行为;实际误差还取决于估计量、哈希质量和基数范围。

对于固定的 bb 位哈希值,寄存器只需能够表示不超过 b−p+1b-p+1 的值,以及初始的零状态。因此,每个寄存器只需少量比特。一种常见的稠密表示为每个寄存器分配六个比特:16,384 个这样的寄存器需要 12 KiB 的寄存器存储空间,不包括元数据和实现开销。

在取值范围不断增长的理论模型中,通常所说的空间复杂度为

O ⁣(ε−2log⁡log⁡n)O\!\left(\varepsilon^{-2}\log\log n\right)

比特,对应的目标相对误差为 ε\varepsilon 量级。实际的固定位宽实现则分配固定的寄存器存储预算,其支持的范围也是有限的。

合并与分布式计算

两个兼容的概要结构可以通过逐寄存器取最大值来合并:

MA∪B[j]=max⁡(MA[j],MB[j]).M_{A\cup B}[j] = \max\bigl(M_A[j],M_B[j]\bigr).

得到的寄存器状态,与将两个集合的所有元素都输入同一个概要结构后得到的状态完全一致。重叠元素不需要特殊处理。

合并操作具有以下性质:

  • **结合性:**以不同方式对合并操作分组,不会改变结果。
  • **交换性:**合并顺序不影响结果。
  • **幂等性:**概要结构与自身合并后保持不变。

这些性质支持MapReduce编程模型等系统中的分区处理,以及数据仓库中的增量聚合。工作节点可以传输概要结构,而不必传输所有不同的标识符。合并概要结构不会在合并后结构本身固有的近似误差之外,引入额外的寄存器层面近似误差。

兼容性要求使用相同的哈希函数、种子、输入编码、精度和寄存器解释方式,或者存在明确支持的转换方法。仅仅字节数相同并不足以保证兼容。某些高精度概要结构可以降为低精度,但转换时必须考虑索引比特与秩比特之间划分的变化。

计算开销

对输入完成哈希计算后,一次普通更新只会读取一个寄存器,并可能修改它。其时间复杂度为 O(1)O(1);对于变长输入,哈希计算还需要处理该输入的各个字节。

直接计算估计值需要扫描所有寄存器,开销为 O(m)O(m)。实现中可以维护辅助统计量,以加快反复求取估计值的速度。合并两个稠密概要结构的开销同样为 O(m)O(m)。

与精确存储不同值的方法不同,稠密概要结构的内存需求不会随着新元素的到来而增长。因此,当需要处理的记录数量远超内存预算时,这种方法尤其有用。

HyperLogLog++ 与实现变体

Stefan Heule、Marc Nunkesser 和 Alexander Hall 于 2013 年介绍了 HyperLogLog++。其工程改进包括:

  • **64 位哈希:**扩大实用的基数范围。
  • **经验性偏差修正:**改善原始估计量存在系统性偏差的区间内的估计结果。
  • **稀疏表示:**减少低基数概要结构的存储开销。
  • **更精细的估计量切换机制:**改善小基数范围内的表现。

稀疏表示存储的是已占用位置的信息,而不是立即为所有稠密寄存器分配空间。具体实现各不相同,稀疏模式与稠密模式之间的切换也会影响存储和执行开销。

后来的估计量可以直接根据寄存器直方图推导估计值,而不必遵循原始的修正方案。因此,即使两个系统采用相似的 HyperLogLog 寄存器数组,也不一定会返回相同的估计值。

应用与局限

HyperLogLog 用于不同值数量的近似聚合统计,例如独立访客数、不同网络地址数、事件标识符数,以及 SQL结构化查询语言查询中的不同值数量。Redis 等系统提供了基于 HyperLogLog 的操作。

它与精确集合表示之间存在若干重要区别:

不支持成员查询。 概要结构可以估计数量,但无法判断某个特定元素是否出现过。

普通概要结构不支持删除。 寄存器保留的是最大值,而不是产生这些最大值的观测记录。删除一个元素后,无法得知应由哪个较小的秩来替代当前最大值。因此,滑动窗口应用需要额外的结构,例如按时间分区的概要结构。

交集和差集不是原生操作。 并集可以直接通过合并得到,但通过

∣A∩B∣=∣A∣+∣B∣−∣A∪B∣|A\cap B|=|A|+|B|-|A\cup B|

估计交集时,可能放大估计误差,尤其是在交集很小的情况下。专门的估计量可以利用一对兼容概要结构中的额外信息,但逐寄存器取最小值并不等同于精确的交集运算。

输入表示很重要。 规范化、序列化或缺失值处理方式不一致,可能导致逻辑上相同的值产生不同的哈希值。这属于估计量无法纠正的数据质量问题。

哈希假设很重要。 分布不良的哈希值可能使寄存器选择和秩统计同时产生偏差。在对抗性场景下,精心构造的输入也可能破坏相关假设。普通的非对抗性工作负载并不要求使用密码散列函数,但当输入不可信时,哈希函数的选择和种子设置就很重要。

紧凑并不意味着具有隐私保障。 概要结构无法像显式列表那样被直接还原,但其内容及变化仍可能泄露信息。HyperLogLog 本身并不提供差分隐私。