Sketching

从 Fingerprinting 到 Sketching

上一讲中，fingerprinting 通过将大对象映射为短小的「指纹」来高效判断相等性。本讲将这一思想推向更一般的场景：sketching（概要/草图技术）。

Sketching 的核心思想

Sketch 是数据的一种有损压缩表示，使用远小于原始数据的空间，同时支持对数据的近似查询。

在大数据场景下，数据往往以数据流（Data Stream）的形式到达——元素 $x_1, x_2, \ldots, x_n$ 逐个到来，算法只能以有限的内存单遍扫描数据。精确存储所有信息需要 $\Omega(n)$ 空间，但 sketch 只使用亚线性（sublinear）甚至 $O(\log n)$ 的空间，代价是允许近似误差。

本讲将围绕多个经典问题展开：

• 近似计数：用 $O(\log\log n)$ 比特计数到 $n$
• 计数不同元素（$F_0$ 估计）：估计流中不同元素的个数
• 频率估计与 heavy hitters：估计各元素出现的频率
• 第二频率矩（$F_2$ 估计）：度量频率分布的不均匀程度
• 近似集合成员查询：Bloom filter

贯穿始终的技术主线是：如何用有限的随机资源构造无偏估计器，并通过 mean trick 和 median trick 将精度与置信度系统化地提升到任意要求。

近似计数

问题：用极少比特计数

一个自然数 $n$ 的精确表示需要 $\lceil\log_2(n+1)\rceil$ 比特。Morris（1978）提出了一个令人惊讶的问题：能否用远少于 $\log n$ 比特来近似记录 $n$？

答案是肯定的：只需 $O(\log\log n)$ 比特。

Morris 算法

Morris 算法

维护一个计数器 $X$，初始值 $X = 0$。

• 更新：每次事件到达时，以概率 $2^{-X}$ 执行 $X \leftarrow X + 1$，否则不做任何操作
• 查询：返回估计值 $\hat{n} = 2^X - 1$

直觉上，$X$ 大致追踪的是 $\log_2 n$：当 $X$ 越大，递增的概率 $2^{-X}$ 越小，因此 $X$ 增长得越来越慢。存储 $X$ 只需要 $O(\log\log n)$ 比特——相比精确计数的 $O(\log n)$ 比特，这是指数级的改进。

更精确地说：由 Markov 不等式（下面会给出期望计算），$\Pr[\hat{n} \ge 10n] \le 1/10$，因此以概率 $\ge 9/10$，有 $\hat{n} = 2^X - 1 \le 10n$，即 $X \le \log_2(10n + 1)$。存储 $X$ 需要 $\log X \le \log\log(10n + 1) = \log\log n + O(1)$ 比特。

无偏性

令 $X_n$ 为处理 $n$ 个事件后计数器的值。

回顾：无偏估计器

一个随机变量 $\hat{\theta}$ 是参数 $\theta$ 的无偏估计器（Unbiased Estimator），如果 $\mathbb{E}[\hat{\theta}] = \theta$——即估计值的「平均表现」恰好等于真实值。无偏性不意味着单次估计准确，只保证没有系统性偏差。衡量单次估计偏离期望的程度，用的是方差 $\text{Var}(\hat{\theta}) = \mathbb{E}[(\hat{\theta} - \theta)^2]$。

定理：Morris 算法是无偏估计器

对所有 $n \ge 0$，有 $\mathbb{E}[2^{X_n}] = n + 1$，即 $\mathbb{E}[\hat{n}] = n$。

证明（数学归纳法）

基础情形：$n = 0$ 时，$X_0 = 0,\, \mathbb{E}[2^{X_0}] = 2^0 = 1 = 0 + 1$。

归纳步骤：假设 $\mathbb{E}[2^{X_n}] = n + 1$，证明 $\mathbb{E}[2^{X_{n+1}}] = n + 2$。

处理第 $n+1$ 个事件时，以概率 $2^{-X_n}$ 将 $X_n$ 增加 1：

$$\begin{aligned} \mathbb{E}[2^{X_{n+1}} \mid X_n] &= 2^{-X_n} \cdot 2^{X_n + 1} + (1 - 2^{-X_n}) \cdot 2^{X_n} \\ &= 2 + 2^{X_n} - 1 \\ &= 2^{X_n} + 1 \end{aligned}$$

两边取期望：$\mathbb{E}[2^{X_{n+1}}] = \mathbb{E}[2^{X_n}] + 1 = (n+1) + 1 = n + 2$。

虽然估计器是无偏的，但单次运行的方差很大——$\text{Var}(\hat{n}) \le n^2/2$。直接使用单个 Morris 计数器的估计值可能偏离真实值很远。

方差推导

类似地用归纳法证明 $\mathbb{E}[2^{2X_n}] \le \dfrac{3}{2}n(n+1) + 1$。

归纳步骤：

$$\begin{aligned} \mathbb{E}[2^{2X_{n+1}} \mid X_n] &= 2^{-X_n} \cdot 2^{2(X_n+1)} + (1 - 2^{-X_n}) \cdot 2^{2X_n} \\ &= 2^{X_n+2} + 2^{2X_n} - 2^{X_n} \\ &= 2^{2X_n} + 3 \cdot 2^{X_n} \end{aligned}$$

取期望：$\mathbb{E}[2^{2X_{n+1}}] = \mathbb{E}[2^{2X_n}] + 3\mathbb{E}[2^{X_n}] = \mathbb{E}[2^{2X_n}] + 3(n+1)$。

由归纳假设：$\mathbb{E}[2^{2X_{n+1}}] \le \frac{3}{2}n(n+1) + 1 + 3(n+1) = \frac{3}{2}(n+1)(n+2) + 1$。

因此：

$$\begin{aligned} \text{Var}(\hat{n}) &= \mathbb{E}[\hat{n}^2] - n^2 = \mathbb{E}[(2^X - 1)^2] - n^2 = \mathbb{E}[2^{2X}] - 2\mathbb{E}[2^X] + 1 - n^2 \\ &\le \frac{3}{2}n(n+1) + 1 - 2(n+1) + 1 - n^2 = \frac{n^2}{2} - \frac{n}{2} \le \frac{n^2}{2} \end{aligned}$$

概率工具箱

在分析 sketch 的精度之前，我们需要几个基本的概率不等式。这些工具将在本讲中反复使用。

Jensen 不等式

若 $\varphi$ 是凸函数，则 $\varphi(\mathbb{E}[X]) \le \mathbb{E}[\varphi(X)]$；若 $\varphi$ 是凹函数，不等号反向。

Jensen 不等式在本讲中的典型应用：$\log$ 是凹函数，因此 $\mathbb{E}[\log X] \le \log \mathbb{E}[X]$——这正是上面分析 Morris 计数器空间时用到的性质。

Markov 不等式

对非负随机变量 $X$ 和任意 $t > 0$：

$$\Pr[X \ge t] \le \frac{\mathbb{E}[X]}{t}$$

Markov 不等式只需要一阶矩信息，因此适用范围广但界很松。直觉上，它说的是「如果一个非负量的平均值很小，那么它取很大值的概率不会太高」——例如，平均收入 1 万元的群体中，收入超过 100 万的人至多占 $1\%$。

Chebyshev 不等式

对随机变量 $X$ 和任意 $t > 0$：

$$\Pr\big[|X - \mathbb{E}[X]| \ge t\big] \le \frac{\text{Var}[X]}{t^2}$$

Chebyshev 利用了二阶矩（方差）信息，给出更紧的界。直觉：方差越小，随机变量越「集中」在期望附近。它本质上是对 $(X - \mathbb{E}[X])^2$ 应用 Markov 不等式。

Chernoff-Hoeffding 界

设 $X_1, \ldots, X_n$ 为独立随机变量，$X_i \in [a_i, b_i],\, X = \sum X_i$。则对任意 $t > 0$：

$$\begin{aligned} \Pr\big[X \ge \mathbb{E}[X] + t\big] &\le \exp\left(-\frac{2t^2}{\sum_{i=1}^{n}(b_i - a_i)^2}\right)\\ \Pr\big[X \le \mathbb{E}[X] - t\big] &\le \exp\left(-\frac{2t^2}{\sum_{i=1}^{n}(b_i - a_i)^2}\right) \end{aligned}$$

Chernoff-Hoeffding 利用了独立性，给出指数衰减的尾概率——这是与 Chebyshev 的多项式衰减的本质区别。代价是需要更强的假设（独立、有界）。直觉：独立随机变量之和的波动远小于最坏情况——大量独立的随机噪声会相互抵消。

三个不等式的关系是：

不等式	所需信息	尾概率衰减
Markov	期望	$O(1/t)$
Chebyshev	期望 + 方差	$O(1/t^2)$
Chernoff-Hoeffding	独立 + 有界	$\exp(-\Omega(t^2))$

$(\varepsilon, \delta)$-估计器

在分析 sketch 算法时，我们关心两个参数：

• 精度 $\varepsilon$：估计值与真实值的相对偏差不超过 $\varepsilon$
• 置信度 $1 - \delta$：以至少 $1 - \delta$ 的概率满足精度要求

$(\varepsilon, \delta)$-估计器

称 $\hat{n}$ 是 $n$ 的 $(\varepsilon, \delta)$-估计器，如果：

$$\Pr\big[|\hat{n} - n| \le \varepsilon n\big] \ge 1 - \delta$$

如何系统化地构造 $(\varepsilon, \delta)$-估计器？这就是 mean trick 和 median trick 的作用。

Mean Trick：Morris+ 算法

Mean trick 的思想很简单：独立运行 $k$ 个估计器，取平均。

Morris+ 算法（Mean Trick）

独立运行 $k$ 个 Morris 计数器 $\hat{n}_1, \ldots, \hat{n}_k$，返回：

$$\hat{n} = \frac{1}{k}\sum_{i=1}^{k}\hat{n}_i$$

取平均保持无偏性，同时方差缩小为原来的 $1/k$：

$$\mathbb{E}[\hat{n}] = n, \qquad \text{Var}(\hat{n}) = \frac{\text{Var}(\hat{n}_1)}{k} \approx \frac{n^2}{2k}$$

由 Chebyshev 不等式：

$$\Pr\big[|\hat{n} - n| \ge \varepsilon n\big] \le \frac{\text{Var}(\hat{n})}{\varepsilon^2 n^2} \le \frac{1}{2k\varepsilon^2}$$

取 $k = \lceil 1/(2\varepsilon^2 \delta) \rceil$ 即可保证这个概率不超过 $\delta$。但注意 $k$ 关于 $\delta$ 是 $O(1/\delta)$——当需要很高的置信度（如 $\delta = 10^{-6}$）时，代价太大。

Median Trick：Morris++ 算法

Median trick 解决了 mean trick 在 $\delta$ 上的低效问题。

Morris++ 算法（Median Trick）

独立运行 $\ell$ 个 Morris+ 实例（每个以常数概率正确，如只需取 $k = O(1/\varepsilon^2)$ 使得单个 Morris+ 以概率 $\ge 9/10$ 正确），取它们的中位数。

关键观察：如果每个 Morris+ 实例以概率 $\ge 2/3$ 给出好的估计，那么 $\ell$ 个实例中，至少一半给出好估计的概率极高。

设 $Y_i = \mathbb{I}[\text{第 } i \text{ 个实例给出坏估计}]$，则 $\mathbb{E}[Y_i] \le 1/3$。中位数出错当且仅当超过一半的实例出错，即 $\sum Y_i > \ell/2$。由 Chernoff-Hoeffding 界：

$$\Pr\left[\sum Y_i \ge \ell/2\right] \le \Pr\left[\sum Y_i \ge \mu + \ell/6\right] \le \exp\left(-\frac{2(\ell/6)^2}{\ell}\right) = \exp\left(-\frac{\ell}{18}\right) \le \delta$$

其中 $\mu = \mathbb{E}[\sum Y_i] \le \ell/3$。取 $\ell = \lceil 18\ln(1/\delta) \rceil$ 即可。

总空间：$k\ell = O(\varepsilon^{-2} \log(1/\delta))$ 个 Morris 计数器，每个 $O(\log\log n)$ 比特。

$$\text{总空间} = O\left(\frac{1}{\varepsilon^2} \log\frac{1}{\delta} \cdot \log\log n\right) \text{ 比特}$$

Mean Trick 与 Median Trick 的配合

这两个技巧构成了一个通用的「精度-置信度提升管线」，在本讲的几乎所有算法中都会用到：

1. Mean trick：取 $O(1/\varepsilon^2)$ 个独立副本的平均，将方差降低到可控范围，使得单次估计以常数概率（如 $\ge 2/3$）正确
2. Median trick：取 $O(\log(1/\delta))$ 个上述估计的中位数，将成功概率指数级提升到 $1 - \delta$

关于 $\delta$ 的依赖从 mean trick 的 $O(1/\delta)$ 改善到了 median trick 的 $O(\log(1/\delta))$——这是 Chernoff 界指数衰减尾概率带来的本质优势。

Median trick 看起来有点像集成学习中的投票机制：多个弱学习器（每个以常数概率正确）通过投票（取中位数）形成一个强学习器（以任意高的概率正确）。这里的「弱学习器」就是单个 Morris+ 实例。

用的是中位数因为连续情形的「正确」往往是一个区间，中位数的性质——若超过一半数据都落在某个区间（正确区间）内，那中位数也一定在这个区间——可以被利用借助这样的「投票」机制来提升置信度。

而离散情形下「正确」是一个点（如分类问题），因此用众数更合适，也是集成学习中常见的多数投票机制。

推广：一般化 Morris 计数器

Morris 算法可以推广到以任意底数 $(1+\alpha)$ 为基础的版本：

一般化 Morris 计数器

参数 $\alpha > 0$。维护计数器 $X = 0$。

• 更新：以概率 $1/(1+\alpha)^X$ 执行 $X \leftarrow X + 1$
• 查询：返回 $\hat{n} = ((1+\alpha)^X - 1)/\alpha$

参数 $\alpha$ 控制了精度与空间的权衡：$\alpha$ 越小，估计越精确（方差越小），但 $X$ 增长越快，需要更多比特存储。

通过精细分析（Flajolet, 1985），取 $\alpha = \Theta(\varepsilon^2\delta)$，可以用单个计数器实现 $(\varepsilon, \delta)$-估计，空间为 $O(\log\log n + \log(1/\varepsilon) + \log(1/\delta))$ 比特。Nelson 和 Yu（2020）进一步改进，将 $\delta$ 依赖优化到 $O(\log\log(1/\delta))$，给出了渐近最优的空间界。

计数不同元素

问题定义

• 数据：一个流 $x_1, x_2, \ldots, x_n \in U = [N]$。
• 查询：估计流中不同元素的个数 $F_0 = |S| = |\{x_1, x_2, \ldots, x_n\}|$。

精确计算 $F_0$ 需要 $\Omega(N)$ 比特（Alon-Matias-Szegedy 证明了即使是近似的确定性算法，在最坏情况下也需要 $\Omega(N)$ 比特），而随机化的 sketch 方法可以用远少于此的空间给出近似估计。

Min Sketch

最简单的思路：用理想均匀哈希函数把元素映射到 $[0,1]$，追踪最小哈希值。

Min Sketch

选取理想均匀哈希函数 $h\colon U \to [0,1]$，维护 $Y = \min\limits_{i} h(x_i)$。

返回估计值 $\hat{F}_0 = 1 / Y - 1$。

直觉：如果有 $z = F_0$ 个不同元素，它们的哈希值在 $[0,1]$ 中均匀独立分布，将区间分成 $z+1$ 段，最小值的期望在 $1/(z+1)$ 附近，因此 $1/Y$ 近似 $z+1$。

方差分析（假设 SUHA）：设 $z = F_0$。$z$ 个不同元素的哈希值是 $[0,1]$ 上的独立均匀随机变量，$Y$ 是它们的最小值。因此对 $0 \le t \le 1$：

$$\Pr[Y > t] = (1-t)^z$$

从而密度为

$$f_Y(t) = z(1-t)^{z-1}$$

于是

$$\mathbb{E}[Y] = \int_0^1 t \cdot z(1-t)^{z-1}\d t = \frac{1}{z+1}\\ \mathbb{E}[Y^2] = \int_0^1 t^2 \cdot z(1-t)^{z-1}\d t = \frac{2}{(z+1)(z+2)}$$

因此

$$\text{Var}(Y) = \mathbb{E}[Y^2] - \mathbb{E}[Y]^2 = \frac{z}{(z+1)^2(z+2)} \le \frac{1}{(z+1)^2}$$

所以最小哈希值的量级稳定在 $1/z$ 附近，进而 $1/Y$ 会落在 $F_0$ 的常数倍范围内。

Min Sketch+：Mean Trick 改进

对 Min Sketch 应用 mean trick：使用 $k$ 个独立的均匀哈希函数 $h_1, \ldots, h_k\colon U \to [0,1]$，分别维护各自的最小值 $Y_j = \min\limits_i h_j(x_i)$，取平均后反转：

Min Sketch+

返回估计值

$$\hat{F}_0 = \frac{1}{\bar{Y}} - 1, \qquad \bar{Y} = \frac{1}{k}\sum_{j=1}^{k} Y_j$$

由于 $k$ 个 $Y_j$ 是独立同分布的，$\mathbb{E}[\bar{Y}] = 1/(z+1)$，方差缩小为 $\text{Var}(\bar{Y}) \le 1/(k(z+1)^2)$。假设 $\varepsilon \le 1/2$，由 Chebyshev 不等式：

$$\Pr\left[\left|\bar{Y} - \frac{1}{z+1}\right| > \frac{\varepsilon/2}{z+1}\right] \le \frac{\text{Var}(\bar{Y})}{(\varepsilon/(2(z+1)))^2} \le \frac{4}{k\varepsilon^2} \le \delta$$

取 $k = \lceil 4/(\varepsilon^2\delta) \rceil$ 即可。空间为 $O(k)$ 个 $[0,1]$ 中的实数。

SUHA 与现实

上述分析假设 $h$ 是完全均匀的随机函数（Simple Uniform Hash Assumption, SUHA），即 $h$ 从所有 $U \to [0,1]$ 的函数中均匀随机选取。

但存储一个完全均匀的哈希函数本身就需要 $\Omega(N \log N)$ 比特——比直接记录哪些元素出现过还大。我们需要用有限随机性就能描述的哈希函数族。

2-Universal 哈希

回顾：哈希函数的作用

哈希函数 $h\colon U \to [m]$ 将大全集 $U$（如所有 IP 地址）映射到小范围 $[m]$（如长度为 $m$ 的数组下标）。数据结构课中的哈希表就是这个思想：用 $h(x)$ 作为 $x$ 的「地址」，以 $O(1)$ 时间存取。

碰撞（$h(x) = h(y),\, x \ne y$）不可避免（鸽巢原理），但好的哈希函数能使碰撞「均匀分散」。问题是：一个「完全随机」的哈希函数需要 $\Omega(|U| \log m)$ 比特存储——太大了。我们需要用少量随机比特就能描述、同时保留关键随机性保证的哈希函数族。

2-universal 哈希（也称成对独立哈希）正是为此设计的。它只保证任意两个不同元素的哈希值表现得像独立均匀随机——这对 sketch 中基于 Chebyshev 不等式的分析已经足够。

2-Universal 哈希函数族

一个哈希函数族 $\mathcal{H} = \{h\colon U \to [m]\}$ 称为 2-universal 的，如果对所有 $x \ne y \in U$：

$$\Pr_{h \sim \mathcal{H}}[h(x) = h(y)] \le \frac{1}{m}$$

等价条件：对任意不同的 $x, y$，随机变量 $h(x)$ 和 $h(y)$ 是（近似）成对独立的。

完全成对独立且均匀（strongly 2-universal/pairwise independent）的哈希函数族满足 $\Pr[h(x) = a, h(y) = b] = 1/m^2$ 对所有 $a, b \in [m]$，但我们只需要弱一些的条件（哈希碰撞不要比理想均匀随机更严重）就足够了。

一个经典的 2-universal 哈希族是线性同余族：

$$\mathcal{H} = \{h_{a,b}(x) = ((ax + b) \bmod p) \bmod m \mid a, b \in \mathbb{Z}_p\}$$

其中 $p$ 是大于 $N$ 的素数。描述一个函数 $h_{a,b}$ 只需存储 $a, b$ 两个参数，共 $O(\log N)$ 比特。

Flajolet-Martin 算法

Flajolet 和 Martin（1984）提出了一个优雅的算法：用哈希值的末尾零（trailing zeros）个数来估计 $F_0$。

定义 $\rho(y)$ 为整数 $y$ 的二进制表示中末尾零的个数，即 $\rho(y) = \max\{i : 2^i \mid y\}$（例如 $\rho(12) = \rho(1100_2) = 2$）。

Flajolet-Martin 算法

设元素 $x_1,\ldots,x_n \in [N] \subseteq [2^w]$。选取 2-universal 哈希函数 $h\colon [2^w] \to [2^w]$，维护：

$$R = \max_{i} \rho(h(x_i))$$

返回估计值 $\hat{F}_0 = 2^R$。

为什么用 $[2^w] \to [2^w]$？

课件中哈希函数的域和值域都取 $[2^w] = \{0, 1, \ldots, 2^w - 1\}$。这一选择使得分析更加干净：在 $[2^w]$ 中，恰好有 $2^{w-r}$ 个元素能被 $2^r$ 整除，因此 $\Pr[\rho(h(x)) \ge r] = 2^{w-r}/2^w = 2^{-r}$（精确等式）。若改用一般的 $[N]$，这个概率就只能近似为 $2^{-r}$，分析中会多出取整和因子 2 的松弛。此外，可以利用有限域 $\mathrm{GF}(2^w)$ 上的线性同余构造 2-universal 哈希 $f(x) = a \cdot x + b$（其中 $a, b \in \mathrm{GF}(2^w)$），存储只需 $O(w)$ 比特。

直觉：$\rho(h(x)) \ge r$ 的概率为 $2^{-r}$（哈希值末尾 $r$ 个比特全为零）。如果有 $z = F_0$ 个不同元素，大约需要 $z \approx 2^r$ 个元素才有可能让某个元素达到 $r$ 个末尾零。因此 $2^R$ 是 $F_0$ 的粗略估计。

令 $S$ 表示流中出现过的不同元素集合，$z = |S| = F_0$。定义

$$Y_r = \sum_{\text{distinct } x \in S} \mathbb{I}[\rho(h(x)) \ge r]$$

由线性期望和成对独立性^[1]：

$$\mathbb{E}[Y_r] = z \cdot 2^{-r}, \qquad \text{Var}(Y_r) \le z \cdot 2^{-r}$$

注意 $R = \max\{r : Y_r > 0\}$，因此 $\hat{F}_0 = 2^R > Cz$ 等价于 $R \ge r^*$（即 $Y_{r^*} > 0$），$\hat{F}_0 = 2^R < z/C$ 等价于 $R < r^{**}$（即 $Y_{r^{**}} = 0$）。

上界分析（不会严重高估）：取 $r^* = \lceil\log_2(Cz)\rceil$，

$$\Pr[\hat{F}_0 > Cz] \le \Pr[Y_{r^*} \ge 1] \le \mathbb{E}[Y_{r^*}] = z/2^{r^*} \le 1/C$$

最后一步用了 Markov 不等式。

下界分析（不会严重低估）：取 $r^{**} = \lceil\log_2(z/C)\rceil$，

$$\Pr[\hat{F}_0 < z/C] \le \Pr[Y_{r^{**}} = 0] \le \frac{\text{Var}(Y_{r^{**}})}{\mathbb{E}[Y_{r^{**}}]^2} \le \frac{2^{r^{**}}}{z} \le \frac{2}{C}$$

最后一步用了 Chebyshev 不等式（$\Pr[Y = 0] \le \Pr[|Y - \mu| \ge \mu] \le \text{Var}/\mu^2$），以及 $\text{Var}/\mathbb{E}^2 = z \cdot 2^{-r}/(z \cdot 2^{-r})^2 = 2^r/z$。

合并两界：

$$\Pr\left[\hat{F}_0 < \frac{z}{C} \text{ 或 } \hat{F}_0 > Cz\right] \le \frac{1}{C} + \frac{2}{C} = \frac{3}{C}$$

因此 $2^R$ 以概率 $\ge 1 - 3/C$ 落在 $[z/C,\, Cz]$ 内。估计值只能落在 $2$ 的幂上，因此精度有限；通过 mean trick（取多个独立实例的均值）或 median trick（取中位数），可以将精度和置信度提升到任意 $(\varepsilon, \delta)$ 的要求。

空间上，维护 $R$ 只需 $O(\log\log N)$ 比特（因为 $R \le w$），存储哈希函数需 $O(\log N)$ 比特。

Bottom-$k$ 算法

Flajolet-Martin 的问题在于估计值过于粗糙，只能落在 $2$ 的幂附近。更自然的改进是保留最小的 $k$ 个哈希值，而不是只保留一个极端统计量。

Bottom-$k$ 算法

设 $z = F_0 = |\{x_1,\ldots,x_n\}|$。选取 2-universal 哈希函数 $h\colon [N] \to [M]$，只考虑不同元素的哈希值。

将这些哈希值从小到大排序为

$$Y_1 \le Y_2 \le \cdots \le Y_z$$

记 $Y_k$ 为第 $k$ 小值，返回估计

$$\hat{z} = \frac{kM}{Y_k}$$

如果 $z$ 个不同元素在 $[M]$ 中近似均匀散开，那么第 $k$ 小值大约落在比例 $k/z$ 的位置，即

$$Y_k \approx \frac{kM}{z}$$

因此 $\hat{z}$ 会接近 $z$。

为了给出误差界，假设 $\varepsilon \le 1$，定义

$$V = \sum_{i=1}^{z} \mathbb{I}\left[h(x_i) \le \left(1-\frac{\varepsilon}{2}\right)\frac{kM}{z}\right], \qquad W = \sum_{i=1}^{z} \mathbb{I}\left[h(x_i) \le \left(1+\frac{\varepsilon}{2}\right)\frac{kM}{z}\right]$$

它们分别统计「落在偏小阈值以内」和「落在偏大阈值以内」的元素个数。由均匀性（每个 $h(x_i)$ 在 $[M]$ 中均匀分布），每个指示变量的概率为阈值除以 $M$，对 $z$ 个不同元素求和：

$$\mathbb{E}[V] = \left(1-\frac{\varepsilon}{2}\right)k, \qquad \mathbb{E}[W] = \left(1+\frac{\varepsilon}{2}\right)k$$

又因为只需要成对独立，每个指示变量的方差 $\le$ 期望（0-1 变量性质），交叉协方差为零，因此

$$\operatorname{Var}(V) \le \mathbb{E}[V] = \left(1-\frac{\varepsilon}{2}\right)k \le k,\qquad \operatorname{Var}(W) \le \mathbb{E}[W] = \left(1+\frac{\varepsilon}{2}\right)k \le 2k$$

$V$ 一侧：若 $Y_k < \left(1-\dfrac{\varepsilon}{2}\right)\dfrac{kM}{z}$，说明这个较小阈值以下已经出现至少 $k$ 个哈希值，即 $V \ge k$。而 $V \ge k$ 意味着 $V - \mathbb{E}[V] \ge k - (1-\varepsilon/2)k = (\varepsilon/2)k$。于是

$$\Pr[V \ge k] \le \Pr\left[\left|V-\mathbb{E}[V]\right| \ge \frac{\varepsilon k}{2}\right] \le \frac{\operatorname{Var}(V)}{(\varepsilon k/2)^2} \le \frac{4k}{\varepsilon^2 k^2} = \frac{4}{\varepsilon^2 k}$$

$W$ 一侧：若 $Y_k > \left(1+\dfrac{\varepsilon}{2}\right)\dfrac{kM}{z}$，则阈值以下不足 $k$ 个，即 $W < k$。而 $W < k$ 意味着 $\mathbb{E}[W] - W > (1+\varepsilon/2)k - k = (\varepsilon/2)k$。于是

$$\Pr[W < k] \le \Pr\left[\left|W-\mathbb{E}[W]\right| \ge \frac{\varepsilon k}{2}\right] \le \frac{\operatorname{Var}(W)}{(\varepsilon k/2)^2} \le \frac{4 \cdot 2k}{\varepsilon^2 k^2} = \frac{8}{\varepsilon^2 k}$$

这里 $W$ 一侧的界比 $V$ 更松（$8$ vs $4$），因为 $\operatorname{Var}(W) \le (1+\varepsilon/2)k \le 2k$ 而 $\operatorname{Var}(V) \le k$。

两边合并（联合界），可得

$$\Pr\big[\hat{z} \notin [(1-\varepsilon)z,\, (1+\varepsilon)z]\big] \le \frac{4}{\varepsilon^2 k} + \frac{8}{\varepsilon^2 k} = \frac{12}{\varepsilon^2 k}$$

注意这里先对 $Y_k$ 设阈值为

$$\left(1-\frac{\varepsilon}{2}\right)\frac{kM}{z},\quad \left(1+\frac{\varepsilon}{2}\right)\frac{kM}{z},$$

而最终结论写成

$$\hat z=\frac{kM}{Y_k}\in[(1-\varepsilon)z,(1+\varepsilon)z]$$

两者并不矛盾，因为 $\hat z$ 与 $Y_k$ 互为倒数关系。事实上，

$$\hat z>(1+\varepsilon)z \iff Y_k<\frac{kM}{(1+\varepsilon)z}, \quad \hat z<(1-\varepsilon)z \iff Y_k>\frac{kM}{(1-\varepsilon)z}$$

为便于用对称的偏差量做 Chebyshev 分析，我们用更强但更简洁的条件

$$\frac{1}{1+\varepsilon}\le 1-\frac{\varepsilon}{2},\quad \frac{1}{1-\varepsilon}\ge 1+\frac{\varepsilon}{2}\quad (0<\varepsilon\le 1)$$

于是

$$Y_k\in\left[\left(1-\frac{\varepsilon}{2}\right)\frac{kM}{z},\, \left(1+\frac{\varepsilon}{2}\right)\frac{kM}{z}\right] \;\Longrightarrow\; \hat z\in[(1-\varepsilon)z,(1+\varepsilon)z]$$

因此，前面对 $Y_k$ 使用 $1\pm \varepsilon/2$ 的阈值，是为了在取倒数后得到 $\hat z$ 的 $1\pm \varepsilon$ 相对误差保证。

此外课件中为了统一，两边都放缩到 $8/(\varepsilon^2 k)$，合并得 $16/(\varepsilon^2 k)$，取 $k = \lceil 16/(\varepsilon^2\delta)\rceil$。这里用更紧的分析，只需取

$$k = \left\lceil \frac{12}{\varepsilon^2\delta} \right\rceil$$

就得到一个 $(\varepsilon,\delta)$-估计器。

若进一步取 $M = N^3$，则每个哈希值只需 $O(\log N)$ 比特存储，总空间为

$$O(k \log N) = O\left(\frac{1}{\varepsilon^2\delta}\log N\right)\ \text{比特}.$$

HyperLogLog

HyperLogLog（Flajolet 等，2007）是实践中使用最广泛的 $F_0$ 估计算法。它结合了两个关键改进：

1. 随机平均（Stochastic Averaging）：用哈希值的前 $p$ 位将元素分配到 $m = 2^p$ 个桶中，在每个桶内独立跟踪剩余比特的最大末尾零个数。这等价于用单个哈希函数模拟 $m$ 个独立的 Flajolet-Martin 实例。
2. 调和平均（Harmonic Mean）：用调和平均而非算术平均合并各桶的估计值，对离群值更加稳健。

HyperLogLog 算法

维护数组 $M[m]$（初始化为 $-\infty$）。其中 $h(x_i)$ 确定桶的编号，$\rho(x_i)$ 为末尾零个数。

• 更新：对每个 $x_i$，令 $M[h(x_i)] = \max\{M[h(x_i)],\, \rho(x_i)\}$
• 查询：计算 $Z = 1 \Big/ \displaystyle\sum_{j=1}^{m} 2^{-M[j]}$，返回 $\alpha_m m^2 Z$

其中修正因子 $\alpha_m = \left(m \displaystyle\int_0^\infty \left(\log_2\dfrac{2+u}{1+u}\right)^m \d u\right)^{-1}$。

HyperLogLog 易于实现且计算高效（课件称「hard to analyze」，分析超出本课范围）。它天然支持快速合并——两个 sketch 的合并只需逐桶取最大值：$M_{\text{all}}[j] = \max\{M_1[j],\, M_2[j]\}$。

标准误差为 $1.04/\sqrt{m}$。使用 $m = 2^{14} = 16384$ 个寄存器（每个 5 比特，共约 $\pu{12KB}$），可以在 $2\%$ 的标准误差内估计超过 $10^9$ 量级的基数。

频率矩

定义

给定流 $x_1, \ldots, x_n \in U = [N]$，定义元素 $x$ 的频率 $f_x = |\{i : x_i = x\}|$。

频率矩

第 $k$ 频率矩（$k$-th Frequency Moment）定义为：

$$F_k = \sum_{x \in U} f_x^k$$

几个重要的特殊情形：

$k$	$F_k$	含义
$0$	$\sum \mathbb{I}[f_x > 0]$	不同元素个数
$1$	$\sum f_x = n$	流的总长度
$2$	$\sum f_x^2$	频率分布的「不均匀度」，等于自连接大小
$\infty$	$\max\limits_x f_x$	最大频率

空间复杂度全景

把 $\varepsilon,\delta$ 视为常数时，频率矩的空间复杂度呈现出清晰的分界：

• $k \le 2$：可以用 $\operatorname{polylog}N$ 空间估计
• $k > 2$：需要 $\tilde{\Theta}(N^{1-2/k})$ 空间

这说明 $k = 2$ 是一个真正的分水岭：到 $F_2$ 为止，还可以用多对数空间处理；一旦进入 $k > 2$，空间需求就上升为 $N$ 的多项式次幂。

几个熟悉的特例是：

• $F_0$：最优空间为 $O(\varepsilon^{-2} + \log N)$ 比特
• $F_1$：就是流长 $n$，可以精确维护，空间 $O(\log n)$
• $F_2$：可用 Tug-of-War 一类算法在 $\operatorname{polylog}N$ 空间内估计

频率估计与 Heavy Hitters

点查询问题

• 数据：一个流 $x_1, x_2, \ldots, x_n \in U = [N]$。
• 查询：给定元素 $x \in U$，估计其频率 $f_x = |\{i : x_i = x\}|$。

精确回答点查询需要 $\Omega(N)$ 空间（为每个可能的元素维护计数器）。sketch 方法用更少的空间给出近似估计。

Bucket Sketch

最简单的方法：用哈希将元素分到 $m$ 个桶中，每个桶维护一个计数器。

Bucket Sketch

选取 2-universal 哈希函数 $h\colon [N] \to [m]$，维护 $m$ 个计数器 $\text{B}[1], \ldots, \text{B}[m]$，初始化为 $0$。

• 更新：每到达 $x_i$，令 $\text{B}[h(x_i)] \mathrel{+}= 1$
• 查询：返回 $\hat{f}_x = \text{B}[h(x)]$

查询值 $\text{B}[h(x)]$ 等于 $f_x$ 加上与 $x$ 碰撞的其他元素的总频率：

$$\hat{f}_x = f_x + \sum_{y \ne x} f_y \cdot \mathbb{I}[h(y) = h(x)]$$

这是一个单边误差估计器：$\hat{f}_x \ge f_x$ 恒成立（只会高估，不会低估）。

期望误差：

$$\mathbb{E}[\hat{f}_x - f_x] = \sum_{y \ne x} f_y \cdot \Pr[h(y) = h(x)] \le \frac{n}{m}$$

由 Markov 不等式（因单边误差非负而可以运用）：$\Pr[\hat{f}_x - f_x \ge \varepsilon n] \le \frac{1}{\varepsilon m}$。

要让错误概率降到某个小常数，需要 $m = O(1/\varepsilon)$，但这只给出常数级的成功概率。如何在不大幅增加空间的前提下提高置信度？

Count-Min Sketch

Count-Min Sketch（Cormode-Muthukrishnan, 2004）用多行取最小值的策略巧妙解决了这个问题。

Count-Min Sketch

使用 $k$ 个独立的 2-universal 哈希函数 $h_1, \ldots, h_k\colon [N] \to [m]$，维护 $k \times m$ 的计数器数组 $\text{CMS}[k][m]$，初始化为 $0$。

• 更新：每到达 $x_i$，对所有 $1 \le j \le k$，令 $\text{CMS}[j][h_j(x_i)] \mathrel{+}= 1$
• 查询：返回 $\hat{f}_x = \min\limits_{1 \le j \le k} \text{CMS}[j][h_j(x)]$

flowchart LR
    subgraph input["数据流"]
        stream["x₁, x₂, ..., xₙ"]
    end

    subgraph cms["Count-Min Sketch"]
        direction TB
        r1["行 1：h₁ → 计数器数组 [m]"]
        r2["行 2：h₂ → 计数器数组 [m]"]
        rk["行 k：hₖ → 计数器数组 [m]"]
    end

    subgraph query["查询 x"]
        min["取 k 行中的最小值"]
    end

    stream --> r1
    stream --> r2
    stream --> rk
    r1 --> min
    r2 --> min
    rk --> min

    classDef inputStyle fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef cmsStyle fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px
    classDef queryStyle fill:#fff3e0,stroke:#ef6c00,stroke-width:2px

    class stream inputStyle
    class r1,r2,rk cmsStyle
    class min queryStyle

为什么取最小值有效？

每一行都是一个 Bucket Sketch，给出的估计值都 $\ge f_x$（单边高估）。取 $k$ 行中的最小值，相当于选择碰撞最少的那一行。只要任意一行的碰撞噪声足够小，最终估计就是好的。所有 $k$ 行同时碰撞严重的概率随 $k$ 指数下降。

分析：

对第 $j$ 行，设碰撞噪声为 $Z_j = \text{CMS}[j][h_j(x)] - f_x$。由上面的分析：

$$\Pr[Z_j \ge \varepsilon n] \le \frac{1}{\varepsilon m}$$

取 $m = \lceil \mathrm{e}/\varepsilon \rceil$，则 $\Pr[Z_j \ge \varepsilon n] \le 1/\mathrm{e}$。由于 $k$ 个哈希函数独立：

$$\Pr\big[\hat{f}_x - f_x \ge \varepsilon n\big] = \Pr\big[\forall j\colon Z_j \ge \varepsilon n\big] \le \left(\frac{1}{\mathrm{e}}\right)^k \le \delta$$

取 $k = \lceil \ln(1/\delta) \rceil$ 即可。

指标	复杂度
空间（计数器）	$O\left(\dfrac{1}{\varepsilon}\log\dfrac{1}{\delta}\cdot\log n\right)$ 比特
空间（哈希函数）	$O\left(\log\dfrac{1}{\delta}\cdot\log N\right)$ 比特
查询时间	$O\left(\log\dfrac{1}{\delta}\right)$

Count-Min Sketch 是单边误差估计器

Count-Min Sketch 的误差保证是：

$$\Pr\big[f_x \le \hat{f}_x \le f_x + \varepsilon n\big] \ge 1 - \delta$$

只会高估，不会低估。这在许多应用中是有利的——例如 heavy hitter 检测中，真正的 heavy hitter 一定不会被遗漏。

线性 Sketch 与分布式计算

Count-Min Sketch 有一个重要的结构性质：线性可合并。

如果两个流 $S_1, S_2$ 分别在不同机器上维护了 Count-Min Sketch $\text{CMS}_1, \text{CMS}_2$（使用相同的哈希函数），那么合并后的 sketch 就是逐元素相加：

$$\text{CMS}_{\text{all}} = \text{CMS}_1 + \text{CMS}_2$$

这使得 Count-Min Sketch 天然适合分布式计算场景：各节点独立处理本地数据流，最后只需传输并合并 sketch（大小远小于原始数据），即可得到全局的频率估计。

Heavy Hitters 的分治查找

Heavy hitter 定义为出现次数超过 $\varepsilon n$ 的元素。有了点查询的 sketch，如何高效找出所有 heavy hitters？

最直接的方法是枚举全集 $U$ 中的每个 $x$，查询 $\hat{f}_x$ 并输出超过阈值的元素。但当 $N$ 很大时（可能 $N \gg n$），枚举整个全集代价太高。

分治法查找 Heavy Hitters

对全集 $[N]$ 递归二分：维护 $\log N$ 层 Count-Min Sketch，第 $\ell$ 层将 $[N]$ 划分为 $2^\ell$ 个区间，每个区间对应一个虚拟元素（相应的频率就是 $f_I = |\left\lbrace i\colon x_i \in I \right\rbrace|$）。

从根节点开始，只在子区间的 sketch 估计值超过阈值时才继续向下递归。由于 heavy hitter 至多 $1/\varepsilon$ 个，每层只有少量分支被展开（即每层继续递归的重区间至多有 $O(1 / \varepsilon)$ 个），总查询次数为 $O((1/\varepsilon) \log N)$。

Tug-of-War 与第二频率矩

从流位置集合 $[n]$ 中独立均匀随机选取两个下标 $i, j$。则

$$\begin{aligned} \Pr_{i, j}[x_i=x_j] &= \sum_{x\in U}\Pr[x_i=x \text{ 且 } x_j=x]\\ &= \sum_{x\in U}\left(\frac{f_x}{n}\right)^2\\ &= \frac{1}{n^2}\sum_{x\in U} f_x^2\\ &= \frac{F_2}{n^2} \end{aligned}$$

因此，$F_2$ 可以理解为：从流中独立随机抽取两个位置，它们取值相同的概率，再乘上 $n^2$。

为什么 Count-Min Sketch 不适用

直觉上，能否用 Count-Min Sketch 的计数器来估计 $F_2 = \sum f_x^2$？答案是不行。

考虑两个频率向量：

$$\bm{f}_1 = (\underbrace{1, 1, \ldots, 1}_n) \quad \text{与} \quad \bm{f}_2 = (\underbrace{1, 1, \ldots, 1, \sqrt{n}}_n)$$

它们的 $F_2$ 分别为 $n$ 和 $2n - 1$，差异显著。但在 Count-Min Sketch 中，大量频率为 1 的元素会「淹没」那个频率为 $\sqrt{n}$ 的特殊元素——用 $w = O(\sqrt{n})$ 大小的 sketch 无法区分这两个向量，因为频率为 1 的元素平均每个桶有 $n / w$ 个（即背景噪声为 $n / w = \sqrt{n}$），无法区别出那个频率为 $\sqrt{n}$ 的元素。

核心困难在于 Count-Min Sketch 的碰撞噪声是加性的，而 $F_2$ 需要捕捉频率的平方信息。我们需要一种完全不同的方法。

Tug-of-War：随机符号的对消

Alon-Matias-Szegedy（1996）提出了一个精巧的想法：给每个元素分配一个随机的 $\pm 1$ 符号。频率为 1 的元素由于符号随机，它们的贡献在求和中相互抵消；而频率高的元素的贡献则保留下来。这就像一场拔河比赛——频率越高的元素「拉力」越大。

Count Sketch（基本 Tug-of-War）

选取 2-universal 符号函数 $\sigma\colon [N] \to \{-1, +1\}$，维护计数器 $z$，初始化为 $0$。

• 更新：每到达 $x_i$，令 $z \leftarrow z + \sigma(x_i)$
• 查询：返回 $z^2$

处理完整个流后：

$$z = \sum_{x \in U} \sigma(x) f_x$$

定理：无偏性

$$\mathbb{E}[z^2] = F_2$$

证明

$$\mathbb{E}[z^2] = \mathbb{E}\left[\left(\sum_x \sigma(x) f_x\right)^2\right] = \sum_{x, y} \mathbb{E}[\sigma(x)\sigma(y)] \cdot f_x f_y$$

对于 2-universal 的 $\sigma$：

• $x = y$ 时：$\mathbb{E}[\sigma(x)^2] = 1$
• $x \ne y$ 时：$\mathbb{E}[\sigma(x)\sigma(y)] = \mathbb{E}[\sigma(x)] \cdot \mathbb{E}[\sigma(y)] = 0$（成对独立性）

因此：

$$\mathbb{E}[z^2] = \sum_x f_x^2 = F_2$$

单个计数器的估计 $z^2$ 是无偏的，但方差有多大？

定理：方差分析

$$\text{Var}(z^2) \le 2F_2^2$$

此结论需要 $\sigma$ 满足 4-wise 独立性（即任意四个不同元素的符号相互独立）。

证明

$\text{Var}(z^2) = \mathbb{E}[z^4] - (\mathbb{E}[z^2])^2$。需要计算 $\mathbb{E}[z^4]$：

$$\mathbb{E}[z^4] = \mathbb{E}\left[\left(\sum_x \sigma(x)f_x\right)^4\right] = \sum_{a,b,c,d} f_a f_b f_c f_d \cdot \mathbb{E}[\sigma(a)\sigma(b)\sigma(c)\sigma(d)]$$

在 4-wise 独立下，$\mathbb{E}[\sigma(a)\sigma(b)\sigma(c)\sigma(d)] = 1$ 仅当四个下标的「重复模式」使得每个值都出现偶数次，即：

• 4-0-0-0（四个下标全相同）：$a = b = c = d$
• 2-2-0-0（两对相同）：如 $a = b \ne c = d$

其他模式下，至少有一个下标出现奇数次，其 $\sigma$ 值的期望为零，整个乘积的期望为零。

因此（2-2-0-0 模式有 $\binom{4}{2}/2 = 3$ 种配对方式）：

$$\mathbb{E}[z^4] = \sum_a f_a^4 + 3\sum_{a \ne b} f_a^2 f_b^2$$

计算方差：

$$\begin{aligned} \text{Var}(z^2) &= \sum_a f_a^4 + 3\sum_{a \ne b} f_a^2 f_b^2 - F_2^2 \\ &= \sum_a f_a^4 + 3\left(F_2^2 - \sum_a f_a^4\right) - F_2^2 \\ &= 2F_2^2 - 2\sum_a f_a^4 \\ &\le 2F_2^2 \end{aligned}$$

其中用到了：

$$\sum_{a \ne b} f_a^2 f_b^2 = \left(\sum_a f_a^2\right)^2 - \sum_a f_a^4 = F_2^2 - \sum_a f_a^4$$

无偏性只需 2-wise 独立，但方差界需要 4-wise 独立。这是因为 $\text{Var}(z^2)$ 的计算涉及 $\mathbb{E}[z^4]$，展开后出现四元组 $\mathbb{E}[\sigma(a)\sigma(b)\sigma(c)\sigma(d)]$，需要 4-wise 独立来保证交叉项消失。

精度不足与改进

由 Chebyshev 不等式：

$$\Pr\big[|z^2 - F_2| \ge \varepsilon F_2\big] \le \frac{\text{Var}(z^2)}{\varepsilon^2 F_2^2} \le \frac{2}{\varepsilon^2}$$

当 $\varepsilon < \sqrt{2} \approx 1.41$ 时，这个界大于 1——完全无用。单个 Count Sketch 计数器的方差太大，无法给出有意义的精度保证。

Count Sketch+：Mean Trick

解决方法正是 mean trick：独立运行 $k$ 个 Count Sketch，取平均。

Count Sketch+

使用 $k$ 个独立的 4-wise 独立符号函数 $\sigma_1, \ldots, \sigma_k\colon [N] \to \{-1, +1\}$，维护 $k$ 个计数器 $\text{CS}[1], \ldots, \text{CS}[k]$，初始化为 $0$。

• 更新：每到达 $x_i$，对所有 $j \le k$，令 $\text{CS}[j] \leftarrow \text{CS}[j] + \sigma_j(x_i)$
• 查询：返回 $\hat{z}^2 = \frac{1}{k}\sum_{j=1}^{k} \text{CS}[j]^2$

由独立性，$\text{Var}(\hat{z}^2) \le 2F_2^2 / k$。取 $k = 2/(\varepsilon^2 \delta)$：

$$\Pr\big[|\hat{z}^2 - F_2| \ge \varepsilon F_2\big] \le \frac{\text{Var}(\hat{z}^2)}{\varepsilon^2 F_2^2} \le \frac{2}{k\varepsilon^2} \le \delta$$

空间：$k$ 个计数器加上 $k$ 个符号函数的种子。进一步用 median trick 可以将 $\delta$ 依赖改善到 $O(\log(1/\delta))$。

Count Sketch++：频率估计

Count Sketch 的思想也可以用于频率估计（点查询），并且给出双边误差保证——与 Count-Min Sketch 的单边误差不同。

Count Sketch++

使用 $k$ 个独立的 2-universal 哈希函数 $h_1, \ldots, h_k\colon [N] \to [m]$ 和 $k$ 个独立的 2-universal 符号函数 $\sigma_1, \ldots, \sigma_k\colon [N] \to \{-1, +1\}$。维护 $k \times m$ 的数组 $\text{CS}[k][m]$，初始化为 $0$。

• 更新：每到达 $x_i$，对所有 $j \le k$，令 $\text{CS}[j][h_j(x_i)] \mathrel{+}= \sigma_j(x_i)$
• 查询：返回 $\hat{f}_x = \operatornamewithlimits{median}\limits_{1 \le j \le k}\; \sigma_j(x) \cdot \text{CS}[j][h_j(x)]$

查询时乘以 $\sigma_j(x)$ 的作用是「还原符号」：$\sigma_j(x)$ 作用于 $x$ 自身贡献的那一项恰好还原为 $f_x$。

定义第 $j$ 行的误差：

$$E_j := \sigma_j(x) \cdot \text{CS}[j][h_j(x)] - f_x = \sum_{y \ne x} \sigma_j(x)\sigma_j(y) \cdot \mathbb{I}[h_j(x) = h_j(y)] \cdot f_y$$

这是碰撞元素的带符号贡献之和。由于符号随机，正负贡献倾向于抵消。

误差界

$$(\mathbb{E}[|E_j|])^2 \le \mathbb{E}[E_j^2] \le \frac{F_2}{m}$$

证明

$$\mathbb{E}[E_j^2] = \mathbb{E}\left[\sum_{y,z \ne x} \sigma_j(y)\sigma_j(z) \cdot \mathbb{I}[h_j(x) = h_j(y)] \cdot \mathbb{I}[h_j(x) = h_j(z)] \cdot f_y f_z\right]$$

由于 $\sigma_j$ 和 $h_j$ 是独立的哈希函数，可以分别取期望。将求和按 $y = z$ 和 $y \ne z$ 分开：

• $y = z$ 项：$\mathbb{E}[\sigma_j(y)^2] = 1$，贡献 $\sum_{y \ne x} \Pr[h_j(x) = h_j(y)] \cdot f_y^2 \le \sum_{y \ne x} \frac{f_y^2}{m} \le \frac{F_2}{m}$
• $y \ne z$ 项：$\mathbb{E}[\sigma_j(y)\sigma_j(z)] = 0$（成对独立），贡献为 $0$

因此 $\mathbb{E}[E_j^2] \le F_2/m$。由 Jensen 不等式 $\mathbb{E}[|E_j|] \le \sqrt{F_2/m}$。

因此 $\mathbb{E}[|E_j|] \le \sqrt{F_2/m}$。由 Markov 不等式：

$$\Pr\big[|E_j| \ge 3\sqrt{F_2/m}\big] \le \frac{1}{3}$$

设 $m = 9/\varepsilon^2$，则 $3\sqrt{F_2/m} = \varepsilon\sqrt{F_2}$，即每一行以概率 $\ge 2/3$ 给出误差不超过 $\varepsilon\sqrt{F_2}$ 的估计。

最终，用 median trick 提升置信度：取 $k = 18\ln(1/\delta)$ 行的中位数，由 Chernoff-Hoeffding 界，设 $S = \sum_{i=1}^{k}X_{j}$，其中 $X_j$ 是第 $j$ 行误差超过 $\varepsilon\sqrt{F_2}$ 的指示变量（失败与否），$\mu = \mathbb{E}[S] \le k/3$，则：

$$\begin{aligned} \Pr\big[|\hat{f}_x - f_x| > \varepsilon\sqrt{F_2}\big] &\le \Pr\left[ S \ge \dfrac{k}{2} \right] \\ &\le \Pr\left[ S - \mu \ge \dfrac{k}{2} - \mu \right] \\ &\le \Pr\left[ S - \mu \ge \dfrac{k}{6} \right] \\ &\le \exp\left(-\frac{2(k/6)^2}{k}\right)\\ &= \exp\left(-\frac{k}{18}\right) = \delta \end{aligned}$$

指标	复杂度
空间	$O\left(\varepsilon^{-2}\log(1/\delta)\right)$ 个计数器
误差保证	$\Pr\big[\hat{f}_x = f_x \pm \varepsilon\sqrt{F_2}\big] \ge 1 - \delta$

Count-Min Sketch vs. Count Sketch++ 对比

特性	Count-Min Sketch	Count Sketch++
误差类型	单边（只高估）	双边
误差界	$\varepsilon n = \varepsilon F_1$	$\varepsilon\sqrt{F_2}$
查询方式	$\min$	$\text{median}$
适用场景	heavy hitter 检测	一般频率估计

当频率分布较均匀时，$\sqrt{F_2} \approx \sqrt{n}$，Count Sketch++ 的误差界 $\varepsilon\sqrt{F_2}$ 远优于 Count-Min 的 $\varepsilon n$。当分布严重偏斜时，两者差异缩小。

Bloom Filter

集合成员查询的信息论下界

• 数据：一个集合 $S \subseteq U = [N],\, |S| = n$。
• 查询：给定 $x \in U$，判断 $x \in S$ 是否成立。

精确表示一个 $n$ 元子集的信息量为：

$$\log_2 \binom{N}{n} = \Omega(n \log N) \text{ 比特}$$

当 $N \gg n$ 时，这远大于 $n$。如果允许近似——容忍一定的假阳性（把不在集合中的元素误判为在集合中），就可以大幅节省空间。

简单哈希过滤器

最基本的近似方案：用一个均匀哈希函数和一个比特数组。

选取哈希函数 $h\colon U \to [m]$，维护比特数组 $A \in \{0,1\}^m$，初始为全 $0$。对每个 $x_i \in S$，置 $A[h(x_i)] = 1$。查询 $x$ 时，若 $A[h(x)] = 1$ 则回答「是」，否则回答「否」。

• $x \in S$：一定回答「是」（无假阴性）
• $x \notin S$：假阳性概率为 $\Pr[A[h(x)] = 1] = 1 - (1 - 1/m)^n \approx 1 - \mathrm{e}^{-n/m}$

单个哈希函数的假阳性率有限。提高精度的方法是使用多个哈希函数。

Bloom Filter

Bloom Filter (Bloom, 1970)

使用 $k$ 个独立的均匀哈希函数 $h_1, \ldots, h_k\colon U \to [m]$，维护比特数组 $A \in \{0, 1\}^m$，初始为全 $0$。

• 插入：对每个 $x_i \in S$，置 $A[h_j(x_i)] = 1,\, \forall 1 \le j \le k$
• 查询：回答「是」当且仅当 $A[h_j(x)] = 1,\, \forall 1 \le j \le k$

flowchart LR
    subgraph elements["插入元素"]
        y["y"] --> h1y["h₁(y)"]
        y --> h2y["h₂(y)"]
        y --> h3y["h₃(y)"]
        x["x"] --> h1x["h₁(x)"]
        x --> h2x["h₂(x)"]
        x --> h3x["h₃(x)"]
    end

    h1y & h2y & h3y & h1x & h2x & h3x --> A["比特数组 A[m]"]

    A -->|查询 v| check{"所有 k 位都为 1？"}
    check -->|"是"| yes["回答 YES<br>（可能假阳性）"]
    check -->|"否"| no["回答 NO<br>（一定正确）"]

    classDef elem fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef hash fill:#f3e5f5,stroke:#4a148c,stroke-width:2px
    classDef arr fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px
    classDef result fill:#fff3e0,stroke:#ef6c00,stroke-width:2px
    classDef no fill:#ffebee,stroke:#c62828,stroke-width:2px

    class y,x elem
    class h1y,h2y,h3y,h1x,h2x,h3x hash
    class A arr
    class check result
    class yes result
    class no no

正确性：

• $x \in S$：由于 $x$ 的所有 $k$ 个哈希位都被置为 1，一定回答「是」（无假阴性）
• $x \notin S$：当所有 $k$ 个哈希位恰好都被其他元素置为 1 时，产生假阳性

假阳性分析

启发式分析（假设各位独立）：

插入 $n$ 个元素后，某一位仍为 0 的概率约为 $(1 - 1/m)^{kn} \approx \mathrm{e}^{-kn/m}$。查询一个不在集合中的元素，所有 $k$ 位都为 1 的概率：

$$\Pr[\text{假阳性}] \approx \left(1 - \mathrm{e}^{-kn/m}\right)^k$$

设 $m = cn$（每个元素分配 $c$ 个比特），选择 $k = c \ln 2$ 使假阳性率最小化：

$$\Pr[\text{假阳性}] \approx \left(1 - \mathrm{e}^{-\ln 2}\right)^{c\ln 2} = 2^{-c\ln 2} \le (0.6185)^c$$

最优参数选择

令 $\varepsilon = (0.6185)^c$ 为目标假阳性率，则：

• 比特数组大小：$m = cn = O\left(\log(1/\varepsilon) \cdot n\right)$ 比特
• 哈希函数个数：$k = c\ln 2 = O(\log(1/\varepsilon))$
• 查询时间：$O(k) = O(\log(1/\varepsilon))$

Bloom filter 的空间开销与元素个数 $n$ 成线性，与全集大小 $N$ 无关。

严格分析：Azuma 不等式

上面的分析假设了各比特位相互独立——但实际上它们并不独立（一个元素同时设置了 $k$ 个位）。严格的分析需要用到鞅和 Azuma 不等式。

回顾：鞅

鞅（martingale）是一类「公平赌博」过程。形式地，随机变量序列 $\{Y_0, Y_1, Y_2, \ldots\}$ 是鞅，如果对所有 $n$：

$$\mathbb{E}[Y_{n+1} \mid Y_0, \ldots, Y_n] = Y_n$$

即已知过去所有信息后，下一步的条件期望等于当前值——未来既不会系统性地上升也不会下降。典型例子：公平硬币赌博中累计收益就是一个鞅。

Chernoff-Hoeffding 界要求随机变量独立，而鞅允许变量之间有依赖关系——只要满足「条件期望不变」的结构。Azuma 不等式正是利用这一结构，在非独立的设定下给出类似 Chernoff 的集中不等式。

Azuma 不等式

设 $\{Y_n : n \ge 0\}$ 是一个鞅，满足 $|Y_n - Y_{n-1}| \le c_n,\, \forall n \ge 1$。则对任意 $t > 0$：

$$\Pr\left(|Y_n - Y_0| \ge t\right) \le 2\exp\left(-\frac{2t^2}{\sum_{i=1}^{n} c_i^2}\right)$$

Azuma 不等式是 Chernoff-Hoeffding 界在鞅序列上的推广。当增量有界时，鞅仍然高度集中在其初始值附近。

应用到 Bloom filter：

设 $Z$ 为所有 $n$ 个元素都插入完成后，数组中仍为 $0$ 的 bit 个数。再设 $\mathcal{F}_i$ 表示前 $i$ 次插入所揭示的全部随机信息，定义

$$q_i \coloneqq \mathbb{E}[Z \mid \mathcal{F}_i],\qquad i=0,1,\ldots,n$$

这便是适合 Azuma 不等式的鞅。由条件期望的塔式法则：

$$\mathbb{E}[q_{i+1} \mid \mathcal{F}_i] = \mathbb{E}\big[\mathbb{E}[Z \mid \mathcal{F}_{i+1}] \mid \mathcal{F}_i\big] = \mathbb{E}[Z \mid \mathcal{F}_i] = q_i$$

注意这里跟「当前还剩多少个 0」不是一回事。若把 $Z_i$ 记为前 $i$ 次插入后数组中实际的 0 的个数，那么 $\{Z_i\}$ 会随着插入不断下降，一般不是鞅。

每次插入最多触及 $k$ 个 bit，因此揭示第 $i$ 次插入的具体结果，最多只会让对最终值 $Z$ 的预测改变 $k$：

$$|q_i - q_{i-1}| \le k.$$

另一方面，每个 bit 在 $kn$ 次独立置位尝试后仍为 $0$ 的概率是 $(1-1/m)^{kn}$，所以

$$\mathbb{E}[Z] = m\left(1-\frac{1}{m}\right)^{kn}.$$

又因为 $q_0 = \mathbb{E}[Z]$、$q_n = Z$，Azuma 不等式给出

$$\Pr\left[\left|Z-\mathbb{E}[Z]\right| \ge \lambda\right] = \Pr\left[\left|q_n-q_0\right| \ge \lambda\right] \le 2\exp\left(-\frac{2\lambda^2}{nk^2}\right)$$

因此最终 0 的个数会高度集中在

$$\mathbb{E}[Z] = m\left(1-\frac{1}{m}\right)^{kn}$$

附近，典型偏差 $\lambda$ 量级是 $O(k\sqrt{n})$。

若最终有 $Z=t$ 个 0，则对一个与构造过程独立的查询元素 $x \notin S$，

$$\Pr[\text{假阳性} \mid Z=t] = \left(1-\frac{t}{m}\right)^k.$$

由于 $Z$ 本身高度集中，假阳性概率也就集中在启发式公式

$$\left(1-\left(1-\frac{1}{m}\right)^{kn}\right)^k$$

附近。这说明虽然 bit 之间并不独立，但启发式分析给出的主结论仍然是正确的。

Counting Bloom Filter

标准 Bloom filter 不支持删除操作：将某一位从 1 改回 0 可能影响其他元素的查询结果。

Counting Bloom Filter 用整数计数器替代比特位：

• 插入 $x$：对所有 $j$，$A[h_j(x)] \mathrel{+}= 1$
• 删除 $x$：对所有 $j$，$A[h_j(x)] \mathrel{-}= 1$
• 查询 $x$：回答「是」当且仅当 $A[h_j(x)] > 0,\, \forall j$

代价是空间从每位 1 比特增加到 $O(\log n)$ 比特（需要计数器避免溢出），但换来了动态集合的支持。

用精确结构实现近似查询

Bloom filter 并非唯一的近似成员查询方案。一个有趣的替代思路是：用哈希函数将全集「缩小」到可管理的规模，然后在小全集上使用精确数据结构。

Approximate by Exact

选取 2-universal 哈希 $h\colon U \to [n/\varepsilon]$。在小全集 $[n/\varepsilon]$ 上维护一个精确的集合数据结构。

• 插入 $x$：将 $h(x)$ 插入集合
• 查询 $x$：回答「是」当且仅当 $h(x)$ 在集合中

假阳性率为 $\varepsilon$（因为对于 $x \notin S$，$h(x)$ 与集合中某个 $h(x_i)$ 碰撞的概率约为 $n / (n/\varepsilon) = \varepsilon$）。

方案	空间	查询时间	支持删除
Bloom Filter	$O(\log(1/\varepsilon) \cdot n)$ 比特	$O(\log(1/\varepsilon))$	否
Approximate by Exact	$O(n\log(1/\varepsilon))$ 比特	$O(1)$	是

两种方案在空间上是同阶的，但在查询时间和功能上有不同的权衡。Approximate by Exact 方案可以直接利用任何支持删除的精确集合数据结构（如哈希表），从而天然支持删除操作。

Sketching 的统一视角

回顾本讲所有算法，它们共享一个统一的架构：

问题	Sketch 结构	随机源	误差保证	空间
近似计数	Morris 计数器	概率递增	$(\varepsilon, \delta)$	$O(\varepsilon^{-2}\log\frac{1}{\delta}\cdot\log\log n)$ 比特
$F_0$ 估计	最小哈希 / 末尾零	2-universal 哈希	$(\varepsilon, \delta)$	$O(\varepsilon^{-2}\log\frac{1}{\delta}\cdot\log N)$ 比特
频率估计	Count-Min $k \times m$	2-universal 哈希	$\hat{f}_x \le f_x + \varepsilon n$	$O(\frac{1}{\varepsilon}\log\frac{1}{\delta}\cdot\log n)$ 比特
频率估计	Count Sketch++ $k \times m$	哈希 + 符号	$\lvert\hat{f}_x - f_x\rvert \le \varepsilon\sqrt{F_2}$	$O(\varepsilon^{-2}\log\frac{1}{\delta})$ 计数器
$F_2$ 估计	Count Sketch+	4-wise 独立符号	$(\varepsilon, \delta)$	$O(\varepsilon^{-2}\log\frac{1}{\delta})$ 计数器
成员查询	Bloom filter	$k$ 个均匀哈希	假阳性 $\le \varepsilon$	$O(\log\frac{1}{\varepsilon}\cdot n)$ 比特

贯穿始终的技术主线：

1. 随机化哈希作为空间压缩的基本手段——用 $O(\log N)$ 比特的种子替代对全集的显式存储
2. 无偏性通过哈希的成对独立性保证，方差控制可能需要更高阶独立性
3. Mean trick + Median trick 管线系统化地将精度 $\varepsilon$ 和置信度 $\delta$ 提升到任意要求，总代价为 $O\left(\varepsilon^{-2}\log(1/\delta)\right)$
4. 单边误差 vs. 双边误差的选择取决于应用需求：Count-Min（单边，适合 heavy hitter）vs. Count Sketch（双边，更精确的 $L_2$ 保证）

Sketching 的本质是「用随机性换空间」：通过精心设计的随机压缩，在保留关键统计信息的同时，将空间需求从线性降到亚线性乃至对数级。这一思想是处理大数据和流数据的核心算法范式。

---

1. 由 2-universal 性，各 $h(x)$ 在 $[2^w]$ 上均匀分布且成对独立。因此 $\Pr[\rho(h(x)) \ge r] = 2^{-r}$。成对独立保证了 $\text{Cov}(\mathbb{I}_x, \mathbb{I}_{x'}) = 0$，从而 $\text{Var}(Y_r) = \sum_x \text{Var}(\mathbb{I}_x)$。由于 $\mathbb{I}_x$ 是 0-1 变量，$\text{Var}(\mathbb{I}_x) = 2^{-r}(1 - 2^{-r}) \le 2^{-r}$。 ↩︎