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

Posted on In , Word count in article: 6.3k Reading time ≈ 23 mins.

课程: COMP5270 - Randomness, Probability, and Algorithms 学期: S1 2026 来源: Week 9 Lecture Notes & Tutorial 9 Solutions

Part 1: Tutorial 9 详细题解

本部分按官方 Solutions PDF整理，每题含完整题目和逐步展开的详细解答。 注：Tutorial 9 也要求完成 Week 8 的 Problem 3 和 Problem 4（关于 BJKST）。

Tutorial 难度总览

题目 所属部分 难度 复习建议
Problem 1 Warm-up 需读讲义；Bloom Filter ↔︎ CountMinSketch 类比 概念题：理解 AND(bits) = MIN(bits)
Problem 2 Warm-up 不必读讲义；ℓ_p 范数单调性 理解即可：
Problem 3 Warm-up 需读讲义；MG vs CMS 对比 重点：理解优缺取舍
Problem 4 Problem Solving 重要；CS vs CMS 同空间预算 重点：误差比较
Problem 5 Problem Solving 可选；CMS 在 turnstile 模型 理解 Markov 需要非负
Problem 6 Advanced 重要；证明 MG 是 sketching 重点：如何合并两个 MG sketch
Problem 7 Advanced 扩展；CMS 求 ℓ₁ Heavy Hitters 了解思路即可

Problem 1: Bloom Filter ↔︎ CountMinSketch 类比

题目: 讨论 Bloom Filter 和 CountMinSketch 之间的平行关系。

题解:

可以将 CountMinSketch 视为 Bloom Filter 的「计数版本」：

Bloom Filter CountMinSketch
操作 在 个 hash 表中将对应 bit 设为 在 个 hash 表中将对应计数器
输出 AND（所有 bit 都为 → 可能在集合中） MIN（取所有行中的最小计数）
本质 （bit 值只能为 或 ） 推广到整数计数

关键观察：当 counter 的值只能是 或 时，。所以 CountMinSketch 是 Bloom Filter 在计数场景下的自然推广。

Problem 2: ℓ_p 范数单调性

题目: 证明：若 ，则 。另外证明 。

题解:

（最大值的平方不超过所有平方之和。）

展开平方和：

取平方根得 。

用 Cauchy-Schwarz 不等式（取 ）：

因此 。

等号何时成立： - ：当 只有一个非零分量 - ：当 只有一个非零分量 - ：当 的所有分量绝对值相等（均匀分布）

这为什么重要：CountSketch 提供 ℓ₂ 误差保证，CountMinSketch 提供 ℓ₁ 误差保证。范数之间的关系决定了哪个保证更强。

Problem 3: Misra-Gries vs CountMinSketch 对比

题目: 讨论 cash register 模型下 Misra-Gries 和 CountMinSketch 的优缺点：速度、内存、近似。

题解:

Misra-Gries CountMinSketch
确定性 ✅ 确定性 ❌ 随机化（有失败概率）
Update 时间 期望（但需全体减时 ） （永远只需更新对应 cell）
草图性质 非线性（但仍是 sketching，见 Problem 6） 线性 sketch ✅
近似方向 下估计 上估计
误差界 ： ：
空间

上估计 vs 下估计的使用场景：

对于 Heavy Hitters 问题（找 的元素）：

  • CountMinSketch（上估计）：设阈值 ，直接选出所有 heavy hitters
  • Misra-Gries（下估计）：设阈值 （更低的阈值），因为

上估计可以设更紧的阈值，可能产生更少的 false positives。

Problem 4: CountSketch vs CountMinSketch 同空间预算

题目: 给定相同的空间预算 ，CountSketch 和 CountMinSketch 的理论保证哪个更好？

题解:

两者的关键差异回顾：

为公平比较，忽略常数和 因子，设 。此时：

由 Problem 2 的范数关系：，得：

分情况讨论：

  1. 非常小（）：，CMS 更优。

  2. 很大、频率均匀分布（）：

    此时 CS 更优（ℓ₂ 误差远小于 ℓ₁ 误差）。

结论：两者各有所长，无法简单地说谁更好——取决于数据分布和参数设置。

Problem 5: CountMinSketch 在 Turnstile 模型

题目: 将 CountMinSketch 分析推广到 strict turnstile 模型（更新可正可负，但 始终成立）。如果是 general turnstile 模型（ 可能变负）呢？

题解:

Strict Turnstile Model

由于 始终成立，每个 row 中的 counter 是 。因此： - （上估计）仍然成立 - Markov 不等式要求随机变量非负 → 仍然可用

分析完全一致，所有保证不变。

General Turnstile Model

当 可能为负时： - 上估计性质 不再成立（counter 可能小于真实频率） - Markov 不等式的非负前提被破坏 → 原分析不适用

结论：CountMinSketch 的原始分析不适用于 general turnstile 模型。

Problem 6: Misra-Gries 是 Sketching Algorithm ⭐

题目: 证明 Misra-Gries 算法是一个 sketching 算法。给出两个流 的 MG 输出 （参数相同 ），合并步骤如下：

  1. （逐元素相加）
  2. 若 有超过 个非零项，设 为第 大的值
  3. （所有项减 ，到 为止）

(a) 证明 至多有 个非零项。 (b) 证明合并后的 sketch 对 提供 MG 的原始估计保证。 (c) 这是线性 sketch 吗？

题解:

(a) 非零项数量的界

合并后先将两个 sketch 逐元素相加。此时可能有超过 个非零项。步骤 2-3 将第 大的值 从所有项中减去（截断到 ）。由于 来自第 大的项，减去 后原先 的项全部归零，超过 个的项被消除。因此最终 至多有 个非零项。

(b) 估计保证

MG 算法的更强保证（讲义未明确写出）：对于流 ，令 ， 为运行结束后 个计数器之和，则：

对于 （）和 （），合并后：

总误差

由于步骤 3 中 是从 个计数器中减去的值（全减 ），需要从 个计数器中至少减去 的总计数：

其中 是合并并减去 后 个计数器的总计数。因此：

代入总误差：

总误差

其中 是总流长度。这与对合并流 直接运行 MG 的误差界一致。

(c) 线性 sketch？

不是。合并步骤不是简单的加法——需要额外的「截断到 个非零项」操作。所以 MG 不是线性 sketch（但仍然是 sketching algorithm）。

Quiz 高频混淆点： - Q2: "Misra-Gries 可看作 sketching 算法吗？" 答案：Yes。MG 可以合并两个流的输出（通过截断），所以是 sketching。 - Q3: "Misra-Gries 可看作 linear sketching 吗？" 答案：No。MG 的合并不是简单加法，需要截断步骤，所以不是线性 sketch。

Problem 7: CountMinSketch 求 ℓ₁ Heavy Hitters

题目: 修改 CountMinSketch，使其输出 ℓ₁ Heavy Hitters：。输出 满足 。

题解思路:

（高级扩展题，了解思路即可。）

CMS 提供上估计 ，且 （调整参数后）。

输出 。

  • 包含性 ：若 ，则 ，所以 。
  • 包含性 ：若 ，即 ，则由 CMS 保证 ... 需要更细致的分析，但核心思想同上估计的特性。

Part 2: 讲义知识点详解

按讲义（Week 9 - Streaming and Sketching II）结构整理，涵盖所有 Algorithm、Theorem、Fact 及其完整证明。

§0 名词与符号速查

符号 含义
Streaming 一趟（或多趟）处理数据流，输出答案
Sketching Streaming 算法的一个子集：允许合并多个 sketch
Linear Sketching 合并操作就是加法的 sketching
Cash Register 只有正的更新（），值只增不减
Turnstile 更新可正可负（）
Strict Turnstile 可正可负，但 始终成立
（频率向量的 ℓ₁ 范数）
（频率向量的 ℓ₂ 范数）
去掉坐标 后的 ℓ₁ 范数
去掉坐标 后的 ℓ₂ 范数

§1 从 Streaming 到 Sketching

动机

Week 8 的 streaming 算法有一个局限：只能处理单个流。但实际中常见：

  1. 分段处理：跑完 得解 ，又来新流 ，能否更新 而不用重跑？
  2. 分布式：Alice 处理 ，Bob 处理 ，能否合并结果？

Sketching algorithm 就是为了解决这个问题：

其中 是某个预定义的合并函数。

Quiz 知识点：Canvas 原题问 "Sketching 算法允许你 ____ 来自 ____ 流的结果"，答案是 combine/different。这正是上面公式的含义——用合并函数 将不同流的 sketch 合并。

线性 sketching 是更强的子集：合并函数 就是向量加法：

（加法通常在合适的向量空间中进行。）

Quiz 知识点：原题问 "Linear sketch 中 combine 操作是 ____"，答案是 (Vector) addition。这是线性 sketching 的核心定义。

§2 回到 Frequent Elements：从 ℓ₁ 到 ℓ₂

Misra-Gries 的局限

Misra-Gries 提供 ℓ₁ 近似：

（等价于）

两个问题： 1. 只适用于 Cash Register 模型（值只增不减） 2. ℓ₁ 保证可能太弱：当数据不均匀时， 很大但 更精确

§3 CountSketch（Algorithm 19）

Charikar, Chen, and Farach-Colton. 在 turnstile 模型下工作，提供 ℓ₂ 保证。

算法描述

参数 ，设置 。初始化数组 大小为 （全零）。

选两个强 universal 哈希函数： - （索引选择） - （符号选择）

处理每个 item （假设 ）：

查询 ：返回 。

核心思想： 提供随机符号，用来去偏——来自其他元素的碰撞在期望上会相互抵消。

Fact 44.1: 线性 Sketch

CountSketch 是线性 sketching 算法：两个用相同 构建的 sketch 可以直接相加合并。

Theorem 45: CountSketch 保证

定理: CountSketch（加 median trick）是随机一趟 sketching 算法。对参数 ，输出的 满足：对每个

空间复杂度：

Corollary 45.1: 整体 ℓ₂ 保证

（注意这是 ℓ₂ vs ℓ∞ 的混合保证：每个坐标误差 ，最坏坐标的误差 。）

证明（Theorem 45）

空间复杂度分析（常数概率版）：

  • 存 ： bits
  • 存 ： bits
  • 存数组 ： 个值，每个 ，需 （因为 ）

总计：。Median trick 加 因子。

期望（固定 ）：

关键步骤： 1. （因为 ） 2. 独立 3. 由 pairwise independence（强 universal）， 与 独立（且均匀分布 → 期望为 ） 4. （均匀分布）

方差：

注意 （不同元素 → 期望 ，相同 ）。

Chebyshev：

取 ，失败概率 。再用 median trick 降至 。

Quiz 知识点：原题 "CountSketch 仅在 cash register 模型下工作"（True/False），答案是 False。CountSketch 的关键优势就是支持 turnstile 模型（更新可正可负）。它通过 的随机符号去偏，使得正负更新都能在期望上正确抵消。

§4 CountMinSketch（Algorithm 20）

Cormode and Muthukrishnan. 在 cash register 模型下工作，提供 ℓ₁ 保证（上估计）。

算法描述

参数 。设置 ，。初始化二维数组 大小 （全零）。

选 个独立的强 universal hash 。

处理每个 item （假设 ）： 对每个 ：

查询 ：返回 。

Fact 45.1: 线性 Sketch

CountMinSketch 也是线性 sketching 算法。

Theorem 46: CountMinSketch 保证

定理: CountMinSketch 是随机一趟 sketching 算法。对参数 ，输出的 满足：对每个

且 （总是上估计）。

空间复杂度：

注意：CMS 没有单独的 median trick！参数 直接提供了概率放大—— 操作就是天然的「概率放大」。

证明（Theorem 46 概要）

空间复杂度：

存 个 hash 函数 + 个 counter。总计 。

上估计性质（）：

在 cash register 模型中，所有更新 。对于任意 和 ：

因此 。

误差分析（单个 row）：

固定 ，定义 。

因为 ，可以用 Markov 不等式：

取 。

的概率放大（ 个独立 row）：

（独立性）

取 。

Markov vs Chebyshev：CMS 用 Markov（因为 ），不需要方差分析；CS 用 Chebyshev（因为 可能低估），需要计算方差。

Quiz 高频知识点： - Q5: "CountMin 和 CountMinSketch 对什么问题给出什么？" 答案：linear sketches / frequency estimation。两者都是线性 sketch，目标都是频率估计（不是 Distinct Elements）。 - Q9: "CMS 可推广到 general turnstile 模型吗？" 答案：False。CMS 的上估计性质依赖于所有更新非负。如果 可能变负，counter 可能低于真实值，Markov 分析失效。CMS 只能用于 cash register 或 strict turnstile（ 始终成立）。 - Q10: "CMS 在 cash register 模型中提供真实频率的什么？" 答案：overestimate（上估计）。，所有碰撞项都是非负的，所以 counter 总是大于等于真实值。

§5 三大算法总结对照

Misra-Gries CountSketch CountMinSketch
算法类型 确定性 streaming 随机 sketching 随机 sketching
模型 Cash Register Turnstile Cash Register
线性 sketch 否（但可 sketching） ✅ 是 ✅ 是
近似保证 ℓ∞ ≤ ε∥f∥₁ ℓ∞ ≤ ε∥f∥₂ ℓ∞ ≤ ε∥f∥₁
方向 下估计（≤） 无偏（≈） 上估计（≥）
空间（含 δ）
概率放大方式 不适用（确定性） Median trick Min 操作内建
Update 最快 需全体减 时慢 快 最快

核心权衡： - 精度 vs 空间：CS 用 空间换 ℓ₂ 精度；CMS 用 空间换 ℓ₁ 精度 - 速度 vs 确定性：CMS 最快但随机化；MG 确定但有时慢 - 上估计 vs 无偏：CMS 适合 Heavy Hitters（上估计可直接筛选）；CS 适合需要无偏估计的场景

Quiz 高频知识点： - Q6: "CMS 比 MG 更_且使用_空间？" 答案：faster / more。CMS 每次更新只需 个 cell，而 MG 有时要全体减 个计数器。但 CMS 空间是 ，MG 是 ，所以 CMS 用更多空间。 - Q7: "CS 和 CMS 对输出质量提供____保证？" 答案：similar。两者都提供频率估计，只是误差形式不同（CS 用 ℓ₂ 无偏，CMS 用 ℓ₁ 上估计），但「质量方向」是相似的。

§6 核心记忆卡片

算法/定理 问题 空间 误差/保证
CountSketch（Theorem 45） Frequent Elements（turnstile, ℓ₂） ，概率
CountMinSketch（Theorem 46） Frequent Elements（cash register, ℓ₁） ，概率 ，且
Misra-Gries 是 sketching（Problem 6） — — 合并需要截断，非线性但仍是 sketching
CMS ↔︎ Bloom Filter（Problem 1） — —

核心技巧汇总：

  1. 线性 sketching 是最强形式的 sketching：合并只是加法。CS 和 CMS 都是线性 sketch，MG 不是。
  2. CountSketch 用 做去偏： 随机符号 → 碰撞项在期望上抵消。方差分析用 Chebyshev。
  3. CountMinSketch 用 做去偏+概率放大：每个 row 上估计（碰撞只会让 counter ≥ 真实值），取 min 最小化过高估计。用 Markov（因为 ）。
  4. CS vs CMS 的关键差异：CS 用 的随机符号 + Chebyshev（需要 空间），CMS 用 min 操作 + Markov（只需 空间）。这是 vs 的根源。
  5. ℓ₁ vs ℓ₂ 范数关系：。当频率均匀时，ℓ₂ 误差远小于 ℓ₁ 误差 → CS 显著优于 CMS。
  6. 从 CS/CMS 到 Heavy Hitters：利用上估计性质（CMS）或 ℓ₂ 保证（CS）设定合适阈值，输出 heavy hitter 集合。

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 的核心定义是「合并（combine）不同流的结果」。合并函数 可以是向量加法（线性 sketch）或更复杂的操作。

Question 2

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

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

选项 答案
No ❌
Yes ✅

知识点：虽然 MG 不是线性 sketching（合并不能简单相加），但它仍然是 sketching 算法——给定两个流的 MG 输出，可以通过截断合并得到合并流的 MG 估计（见 Tutorial 9 Problem 6）。

Question 3

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

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

选项 答案
No ✅
Yes ❌

知识点：MG 的合并需要「截断到 个非零项」的操作，不是简单的向量加法。因此不是线性 sketch。CountSketch 和 CountMinSketch 才是线性 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 ❌

知识点：线性 sketching 的合并操作就是向量加法：。

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 ❌

知识点：两者都是线性 sketch，目标都是频率估计（Frequent Elements / Heavy Hitters），不是 Distinct Elements（那是 Tidemark/BJKST 的问题）。

Question 6

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

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

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

知识点：CMS 每次更新只需 个 cell（独立 hash 行），而 MG 需要 的 BST 操作，且有时要全体减。但 CMS 的空间是 ，MG 是 ，所以 CMS 用更多空间（多了 因子）。

注意：这里选项中 "faster/more" 和 "faster/more" 重复了，可能是排版问题。正确答案应理解为 faster + more space。

Question 7

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

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

选项 答案
different ❌
similar ✅
opposite ❌

知识点：两者都提供频率估计的近似保证，只是误差形式不同：CountSketch 用 ℓ₂ 误差（无偏），CountMinSketch 用 ℓ₁ 误差（上估计）。但「质量方向」是相似的——都是给每个坐标的频率一个近似值。

Question 8

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

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

选项 答案
True ❌
False ✅

知识点：CountSketch 的关键优势就是支持 turnstile 模型（更新可正可负）。它通过 的随机符号去偏，使得正负更新都能在期望上正确抵消。这是 CountSketch 和 CountMinSketch 的核心区别之一。

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 的上估计性质（）依赖于所有更新非负。如果允许负更新，counter 可能低于真实值，上估计性质和 Markov 分析都失效。因此 CMS 只能用于 cash register 或 strict turnstile（ 始终成立）。

Question 10

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

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

选项 答案
overestimate ✅
underestimate ❌
unbiased estimate ❌

知识点：CMS 的 。所有碰撞项都是非负的（cash register），所以 counter 总是大于等于真实值。取 min 后仍然 。这是 CMS 的核心特性，也是它能用于 Heavy Hitters 筛选的原因。

Week 9 Quiz 速查表

题号 核心概念 正确答案
1 Sketching 定义 combine/different
2 MG 是 sketching Yes
3 MG 是 linear sketching No
4 Linear sketch 合并操作 Vector addition
5 CMS 问题类型 linear sketches / frequency estimation
6 CMS vs MG 速度/空间 faster / more
7 CS vs CMS 保证质量 similar
8 CS 只支持 cash register False（支持 turnstile）
9 CMS 支持 general turnstile False
10 CMS 估计方向 overestimate

高频混淆点： - MG 是 sketching 但不是 linear（Q2 vs Q3） - CS 支持 turnstile，CMS 不支持 general turnstile（Q8 vs Q9） - CMS 总是上估计（Q10）——这是它与 CS 和 MG 的关键区别