COMP5270 Week 9 总结：Streaming and Sketching II（题解 + 知识点）

Posted on 2026-06-01 Edited on 2026-06-14 In Course Notes , COMP5270 Word count in article: 6.5k Reading time ≈ 23 mins.

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 9 - Streaming and Sketching II, Week 9 - Tutorial 9 (Solutions)

Part 1: Tutorial 9 详细题解

Tutorial 9 开头说明：还应补做 Week 8 tutorial 的 Problems 3 和 4（上周未覆盖）。各题难度/要求如下：

Problem 1（Warm-up）：Discussion，理解概念类。
Problem 2（⋆ 选做）：ℓ_p 范数单调性证明，有用的数学事实，可跳过后看答案。
Problems 3, 4：需看过讲义，但应自行尝试；对于理解算法很重要。
Problem 5：有时间则做，否则可跳过后看答案。
Problem 6：难度较高（⋆），值得做以理解 Misra-Gries 为何是 sketching 算法。
Problem 7：有时间则做，否则可跳过。

Problem 1（Warm-up）：Bloom Filter vs Count-Min-Sketch 的类比

题目：讨论 Bloom Filter 和 Count-Min-Sketch 之间的相似性。

解答：

可以把 Count-Min-Sketch 看作 Bloom Filter 的"计数版本"：

特征	Bloom Filter	Count-Min-Sketch
数据结构	张哈希表，每格存 bit	张哈希表，每格存 count
更新操作	将个位置置为 1	将个位置加上
查询操作	报告个位置的 AND	报告个位置的 MIN
性质	AND(bits) = MIN(bits)，即 Bloom Filter 也是在报告 MIN（但将计数 cap 在 1）

因此，Bloom Filter 可以看作把 count cap 在 1 之后的 Count-Min-Sketch。两者都利用了"多个独立哈希函数+最小/AND操作"来消减噪声、提升准确率。

Problem 2（⋆ 选做）：ℓ_p 范数的单调性

题目：设，证明：

并证明。指出等号成立的条件。更一般地（⋆）：若，则。

解答：

第一步：证明

取平方根即得。等号成立当且仅当只有一个非零分量。

第二步：证明

（因为，所以对每个，，对求和即得。）

取平方根得。等号成立当且仅当只有一个非零分量。

第三步：证明

由 Cauchy-Schwarz 不等式（令）：

故。等号成立当且仅当对所有相等（即是常量向量）。

Problem 3：Misra-Gries vs Count-Min-Sketch 的比较

题目：在 cash register 模型下，比较 Misra-Gries（MG）和 Count-Min-Sketch（CMS）在速度、内存、近似质量上的优缺点。什么情况下 CMS 的高估比 MG 的低估更有用？

解答：

空间：两者空间都是（忽略依赖），但 CMS 多了因子来控制失败概率；MG 是确定性算法。

更新速度： - MG：每次更新需要先在计数器集合中查找（哈希表期望），但有时需要将所有个计数器全部减 1，最坏。 - CMS：每次更新只需更新个位置，每次，总计，通常快得多。

近似质量： - MG 给出低估：（误差以范数量级计）。 - CMS 给出高估：，保证总是高估。 - CMS 还是一个线性 sketch（可合并），MG 通过扩展也可以成为 sketching 算法（见 Problem 6）。

高估更有用的场景：Heavy Hitters 问题——找出所有满足的频繁元素。若使用高估（CMS），只需检查估计值的元素，这保证真正的 heavy hitters 不会被遗漏（）；与此同时，由于阈值设为而非更小的值，假阳性数量也相对可控。

Problem 4：等空间下 Count-Sketch vs Count-Min-Sketch 的理论保证比较

题目：在相同空间预算下，Count-Sketch（CS）和 Count-Min-Sketch（CMS）的理论保证哪个更好？

解答：

忽略常数因子和依赖，两者的保证分别为：

CS（Count-Sketch）：
CMS（Count-Min-Sketch）：

固定空间 （即），则对 CMS，，即在相同空间下 CMS 的参数变成：

比较误差：利用，

更精确地：

两种极端情形：

时：，CMS 更好。
为常数且接近均匀分布时：，故，此时，CS 更好。

结论：两者各有适用场景，不可比。很小时 CMS 更优；较大且数据近均匀时 CS 更优。

Problem 5（选做）：Count-Min-Sketch 在 strict turnstile 模型下的推广

题目：将 CMS 的分析推广到 strict turnstile 模型（更新可以是负数，但任意时刻）。给出保证。分析能推广到 general turnstile 模型（可为负）吗？

解答：

Strict turnstile 模型：由于任意时刻，Theorem 46 的证明中用到的 Markov 不等式（要求随机变量非负）仍然成立——因为是始终保证的。因此整个分析可以直接推广：

$（以高概率）$

General turnstile 模型：若可以为负，则 Markov 不等式不再适用（它要求非负随机变量），分析无法推广。

Problem 6（⋆）：Misra-Gries 是 Sketching 算法

题目：设对流分别运行 MG（参数），得到输出向量。按以下步骤合并：

令
若的非零项超过个，设为非递增排序后第个值
令（对所有）

论证至多有个非零项。
证明对合并流满足 MG 的原始保证。
这个 sketch 是线性 sketch 吗？

解答：

(a)：第 3 步中，我们对所有项减去（即第个最大值）并取非负部分。减去后，原来排名第及之后的项全部变为，取后为 0。故至多剩下前个非零项。

(b)：回顾 MG 算法的更强保证：设（resp. ）为对（resp. ）运行 MG 后数组中所有计数之和，则

其中。合并后（步骤 1）误差上界为。

步骤 3 中减去（增加额外误差）。设为步骤 3 后数组计数之和，由于从个位置各减（其余可能更多）：

总误差上界：

这正是对合并流（总长度）的 MG 保证。

(c)：不是线性 sketch。线性 sketch 要求合并操作是线性的（直接相加），但 MG 的合并还需要额外的非线性后处理（减去并取非负部分），所以 MG 的合并操作不是线性的。

Problem 7（选做）：用 Count-Min-Sketch 找 Heavy Hitters

题目：修改 CMS 算法，使其在 strict turnstile 模型下输出 Heavy Hitters：即给定参数，输出集合使得

其中。

解答（思路）：

在 CMS 之上，再维护一个附加结构来追踪候选 heavy hitters：

估计：在 cash register 模型下直接累计所有更新量之和；在 strict turnstile 模型下，可用单独计数器维护当前（因为始终成立，故随时间单调）。
候选集构造：对每个，用 CMS 查询。由 Theorem 46，（恒成立）且（高概率）。
输出：令。
- 若，则，故（无遗漏）。
- 若，则高概率（高概率不入）。
但这仍需枚举所有。更高效的做法：附加一个 Count-Sketch 结构或 -heavy hitter 数据结构（如 summary 结构），直接返回候选集。

Part 2: Week 9 讲义知识点——Streaming and Sketching II

§0 背景回顾

Week 8 介绍了流算法的基本模型（cash register 和 turnstile）以及若干经典算法：Misra-Gries（Heavy Hitters/频率估计）、Morris Counter（近似计数）、Tidemark/AMS（估计）、BJKST（精确估计，近似）。

Week 9 的核心主题：Sketching——一类特殊的流算法，其数据结构（sketch）可以跨多个流合并（merge/compose）。

§1 Sketching 的定义

直觉：Sketching 算法的核心性质是可组合性（composability）。如果我们对两个数据集分别计算了 sketch，我们可以直接合并这两个 sketch 来得到联合数据集的 sketch，而无需重新扫描原始数据。

Definition（Sketching Algorithm / Mergeable Streaming Algorithm）：

设是一个流算法，是两个流，是它们的拼接。是一个 sketching algorithm（或 mergeable streaming algorithm）当且仅当存在合并函数，使得：

即对合并流的 sketch 可以从两个子流的 sketch 恢复出来。

应用场景： - 分布式计算（每台机器独立处理一部分数据，再合并） - MapReduce / Spark 框架 - 并行流处理

§2 线性 Sketching（Linear Sketching）

Definition（Linear Sketch）：

若 sketch 满足：

即合并操作是向量加法，则称为线性 sketch。

等价表述：线性 sketch 本质上是将频率向量映射为，其中是某个（通常随机的）矩阵，。

重要性： - 线性 sketch 天然支持 turnstile 模型（负数更新） - 线性 sketch 是最通用的 sketch 形式 - 许多重要算法（Count-Sketch、Count-Min-Sketch 等）都是线性 sketch

§3 Count-Sketch 算法

动机：我们希望估计频率向量中每个元素的值，误差以（除以外所有频率的范数）为单位。

Algorithm 19（Count-Sketch）：

参数： - （计数器数量） - （独立重复次数，用于 median 操作）

数据结构：个大小为的数组；对哈希函数： - ，强全域（strongly universal，即 2-wise independent） - ，强全域

更新操作（处理元素）：

对每个：

查询操作（估计）：

对每个，计算局部估计：

最终估计（取中值以提升置信度）：

空间复杂度：（哈希函数存储 + 计数器数组）

§4 Count-Sketch 的正确性分析

Fact 44.1：Count-Sketch 是一个线性 sketching 算法。

证明：每次更新是线性操作；合并时将对应数组相加即可。故满足线性 sketch 的定义。

Theorem 45（Count-Sketch 的保证）：

设。对任意，以概率（对于单个哈希对）：

其中是将中第项置为 0 后的向量，。

经过次独立重复并取中值，以概率：

空间。

证明（分析单个对，省略下标）：

展开估计量：

期望：

对：，，贡献。

对：由的 2-wise independence，（因为等概率）。故贡献为 0。

$（无偏估计量）$

方差：

展开平方：对，由的 2-wise independence 和期望为 0，交叉项期望为 0。故：

（用到的 2-wise independence：对。）

Chebyshev 不等式：

取则失败概率。

Median 技巧：对个独立估计量取中值，失败概率降至（标准 amplification，见 Week 8 Theorem 41）。

Corollary 45.1：

即对所有同时以高概率成立（Union Bound 后空间只多一个因子）。

证明：由，对每个失败概率，Union Bound 后总失败概率。

§5 Count-Min-Sketch 算法

动机：在 cash register 模型（只有正数更新）下，我们希望以误差估计，并且估计总是高估（恒成立）。相比 Count-Sketch 的误差，这里的误差更宽松但数据结构更简单。

Algorithm 20（Count-Min-Sketch）：

参数： - （每行计数器数量） - （独立哈希函数数量）

数据结构：的计数器数组；个独立哈希函数（pairwise independent）

更新操作（处理元素，）：

对每个：

查询操作（估计）：

关键区别： - Count-Sketch 使用来"去噪"，可用于 turnstile 模型 - Count-Min-Sketch 不使用符号函数，直接累计正数，取最小值；只适用于 cash register 模型（）

空间复杂度：

§6 Count-Min-Sketch 的正确性分析

Fact 45.1：Count-Min-Sketch 是一个线性 sketching 算法。

证明：每次更新是线性操作；合并时将两个数组对应位置相加。查询时取 min。故满足 linear sketch 的定义。

Theorem 46（Count-Min-Sketch 的保证）：

设，。在 cash register 模型（恒成立）下，对任意，恒成立（非概率性！）：

（以概率，所有行中至少一行满足右侧不等式，从而 min 操作给出好的上界。）

证明：

下界（恒成立）：

对任意，（因为所有更新均为正数，总和只会更大）。故。

上界（以高概率）：对固定，

其中是碰撞带来的噪声。

$取$

由 Markov 不等式（，在 cash register 模型下成立）：

更精确地，取（常见做法），可得。

对个独立行，每行"坏"的概率，所有行都"坏"的概率（取）。

因此以概率，至少有一行使得，从而：

注：Count-Min-Sketch 不使用 median 技巧，而是直接用 min 操作来提升置信度。这是因为：每行的估计总是高估（恒成立），所以取 min 只会减小估计值，不会低于真实值，是安全的。而 Count-Sketch 中若取 min，可能因为符号函数导致某些行严重低估（），故用 median。

§7 Count-Sketch vs Count-Min-Sketch 对比

特征	Count-Sketch	Count-Min-Sketch
流模型	Turnstile（含负数）	Cash register（仅正数）
哈希函数	（strongly universal）+ （strongly universal）	（pairwise independent），个
更新		（行）
查询	，取 median
误差保证
方向	双侧误差（可高估可低估）	单侧（总是高估）
空间
amplification	Median-of-means	min 操作（内置）
线性 sketch	是	是

误差类型的关系：由（Problem 2 的结论），Count-Sketch 的保证总是比 Count-Min-Sketch 的保证更强（但前者用了更多空间 vs ）。

§8 Sketching 的更广背景

为什么 sketching 很重要：

分布式计算：数据分布在多台机器上，每台机器独立计算 sketch，最后聚合。线性 sketch 的合并只需要向量加法，通信开销小。
MapReduce/Spark：Map 阶段计算局部 sketch，Reduce 阶段合并。
数据库查询优化：用 sketch 作为近似 synopsis，快速回答聚合查询。
信号处理 / 压缩感知（Compressed Sensing）：线性 sketch 是压缩感知的核心操作。若满足 RIP（Restricted Isometry Property），可从恢复稀疏向量。

线性 sketch 的下界：可以证明，任何能以近似的线性 sketch 需要空间（通信复杂性下界），与 AMS sketch 的上界匹配。

§9 重要不等式汇总（Week 9 常用）

本周证明中用到的核心工具：

范数单调性（Problem 2 / §2.2）：对，

更一般地，。

Chebyshev 不等式（Count-Sketch 分析）：

Markov 不等式（Count-Min-Sketch 分析，要求）：

Pairwise independence 的性质（两个哈希函数的分析核心）：

pairwise independent：，
pairwise independent：，，

Cauchy-Schwarz 不等式：

§10 本周知识点总览

概念	关键内容
Sketching	可合并的流算法；
Linear Sketch	合并 = 向量加法；本质是矩阵-向量乘积
Count-Sketch（Algorithm 19）	Turnstile 模型；误差；strongly universal ；median
Theorem 45	；空间
Corollary 45.1	（Union Bound）
Fact 44.1	Count-Sketch 是线性 sketch
Count-Min-Sketch（Algorithm 20）	Cash register 模型；误差；总是高估；min 操作
Theorem 46	（高概率）；空间
Fact 45.1	Count-Min-Sketch 是线性 sketch
MG 作为 sketch	通过加法合并 + 减去第大值后处理，可实现 mergeability（Problem 6）

Part 3: Week 9 Quiz 回顾

来源：Canvas Quiz，整理自 5270-questions-organized.md。每题含中英文题目、正确答案及知识点解析。

Question 1

[EN] A sketching algorithm is a streaming algorithm which allows you to _____ results from ____ streams.

[CN] Sketching 算法是一种数据流算法，允许你_来自_流的结果。

选项	答案
multiply/different	❌
combine/reverse	❌
draw/different	❌
combine/different	✅

知识点：Sketching 的核心定义：streaming 算法满足，即可以"合并"（combine）来自不同流片段的 sketch 结果。

Question 2

[EN] The Misra-Gries algorithm can be seen as a sketching algorithm.

[CN] Misra-Gries 可看作 sketching 算法。

选项	答案
No	❌
Yes	✅

知识点：Misra-Gries 的合并操作（将两个计数器表合并后删除绝对值小的元素）是合法的 sketch 合并，因此是 sketching 算法（虽然不是线性 sketch）。

Question 3

[EN] The Misra-Gries algorithm can be seen as a linear sketching algorithm.

[CN] Misra-Gries 可看作 linear sketching 算法。

选项	答案
No	✅
Yes	❌

知识点：Linear sketch 要求合并操作等价于向量加法（）。Misra-Gries 的合并包含删除步骤，不能表示为线性运算，故不是 linear sketch。

Question 4

[EN] A linear sketch is a subset of sketches where the "combine" operation is _______.

[CN] Linear sketch 中 "combine" 操作是____。

选项	答案
（Vector）addition	✅
Matrix multiplication	❌
Linear-time	❌
(Vector) inner product	❌

知识点：Linear sketch 本质上是矩阵-向量乘积，合并两个流的 sketch 就是，即向量加法。Count-Sketch 和 Count-Min-Sketch 都是线性 sketch。

Question 5

[EN] The CountMin and CountMinSketch both give _______ for the _______ problem [Select the most accurate answer].

[CN] CountMin 和 CountMinSketch 对_问题给出_。

选项	答案
sketches/distinct elements	❌
sketches/frequency estimation	❌
linear sketches/frequency estimation	✅
linear sketches/distinct elements	❌

知识点：Count-Sketch（Algorithm 19）和 Count-Min-Sketch（Algorithm 20）都是线性 sketch（合并 = 向量加法），都用于频率估计（frequency estimation，估计），不是 Distinct Elements 问题（那是 Tidemark/BJKST 解决的）。

Question 6

[EN] CountMinSketch is _______ than the Misra-Gries algorithm, and uses _____ space.

[CN] CountMinSketch 比 Misra-Gries 更_，且使用_空间。

选项	答案
slower/more	❌
slower/less	❌
faster/more	✅
faster/less	❌

知识点：CountMinSketch 是线性 sketch，更新时间（个哈希函数并行），比 Misra-Gries 每步可能需时间删减计数器更快。空间上 CMS 使用，通常多出因子。

Question 7

[EN] CountSketch and CountMinSketch provide qualitatively _______ guarantees for the quality of their output.

[CN] CountSketch 和 CountMinSketch 对输出质量提供____保证。

选项	答案
different	❌
similar	✅
opposite	❌

知识点：两者都对频率估计提供近似保证，质量上相近（Theorem 45 vs Theorem 46）。主要区别：CountSketch 提供误差界（更强），CountMinSketch 提供误差界（稍弱），且 CountMinSketch 只适用于 cash register 模型而 CountSketch 支持 turnstile。

Question 8

[EN] CountSketch works only in the "cash register" model, where updates can only be positive.

[CN] CountSketch 仅在 "cash register" 模型（只增不减）下工作。

选项	答案
True	❌
False	✅

知识点：CountSketch（Algorithm 19）通过符号函数使更新有正有负，从而支持 turnstile 模型（更新量可正可负）。这与只适用于 cash register 的 Count-Min-Sketch 形成对比。

Question 9

[EN] CountMinSketch can be generalised to the general "turnstile" model, where updates can be positive or negative and no assumptions are made on the sequence of updates.

[CN] CountMinSketch 可推广到 "turnstile" 模型（增减均可，无序列假设）。

选项	答案
True	❌
False	✅

知识点：CountMinSketch 的上界证明依赖（碰撞噪声非负），需要 cash register 假设（）。若允许负更新，Markov 不等式不适用，"min 恒高估"的性质也失效。Turnstile 模型应改用 CountSketch。

Question 10

[EN] In the cash register model, CountMinSketch provides an _____ of the true frequencies.

[CN] 在 cash register 模型中，CountMinSketch 提供真实频率的____。

选项	答案
overestimate	✅
underestimate	❌
unbiased estimate	❌

知识点：由 Theorem 46 的下界部分（恒成立，无概率性）：。每个桶包含了所有与碰撞的元素的计数（在 cash register 下均非负），所以总是高估（overestimate）。

Week 9 Quiz 速查表

题号	核心概念	正确答案
1	Sketching 定义	combine/different
2	MG 是 sketch	Yes
3	MG 是 linear sketch	No
4	Linear sketch 操作	向量加法
5	Count-X 的类型与问题	linear sketches/frequency estimation
6	CMS vs MG	faster/more space
7	CS vs CMS 保证	similar
8	CountSketch 模型	False（支持 turnstile）
9	CMS turnstile	False（仅 cash register）
10	CMS 高估	overestimate

高频混淆点： - MG 是 sketch 但不是 linear sketch（Q2 vs Q3）——合并操作有删除步骤，不是线性的 - CountSketch 支持 turnstile，CountMinSketch 不支持（Q8 vs Q9）——符号函数是关键 - CMS 总是高估（overestimate）——cash register 下碰撞噪声非负，min 操作安全（Q10）