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

Posted on Edited on In , Word count in article: 3.9k Reading time ≈ 14 mins.

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

Part 1: Tutorial 9 详细题解

Warm-up

Problem 1: Bloom filter 与 CountMinSketch 的相似性

题目: 讨论 Bloom filters 和 CountMinSketch 的平行关系。

题解:

CountMinSketch 可以看成 Bloom filter 的“计数版”。

Bloom filter：

  • 有 个 hash functions；
  • 插入元素时，把 个位置的 bit 设为 1；
  • 查询时，看 个位置是否全为 1；
  • 最终输出逻辑 AND。

CountMinSketch：

  • 有 行 hash tables；
  • 每次看到元素 ，在每一行对应 bucket 的 counter 加 1；
  • 查询 时，取 个 counter 的 minimum。

如果 Bloom filter 的 bit 被看成被 cap at 1 的 counter，那么：

所以 Bloom filter 是 membership 版本，CountMinSketch 是 frequency estimation 版本。

二者也共享一个错误方向：

  • Bloom filter 只会 false positive；
  • CountMinSketch 在 cash register model 中只会 overestimate。

本题用到的知识点:

  1. Bloom filter 用 AND，CountMinSketch 用 MIN。
  2. 多 hash tables 降低 collision noise。
  3. Bloom false positive 对应 CMS overestimate。

Problem 2: norm monotonicity

题目: 证明对 ：

并证明：

何时取等号？

题解:

1.

设：

则：

取平方根：

等号在只有一个非零坐标时可取。

2.

因为：

取平方根：

等号同样在至多一个非零坐标时可取。

3.

由 Cauchy-Schwarz：

所以：

等号在所有 相等时可取。

本题用到的知识点:

  1. norm monotonicity。
  2. Cauchy-Schwarz。
  3. 稀疏向量与均匀向量是两类极端情形。

Problem 3: Misra-Gries vs CountMinSketch

题目: 在 cash register model 中比较 Misra-Gries 与 CountMinSketch：速度、内存、近似。什么时候 overestimate 更好？

题解:

Misra-Gries

优点：

  • deterministic；
  • 空间 ；
  • 对所有 给出 underestimate：

缺点：

  • 更新时可能触发“所有 counters 减 1”；
  • 若用简单结构，单次更新 worst-case 可到 ；
  • 不是线性 sketch 的最直接形式，但可以 merge，见 Problem 6。

CountMinSketch

优点：

  • 更新非常简单：每行一个 bucket 加 1；
  • 每次更新时间 ；
  • 是 linear sketch，容易 merge；
  • 可扩展到 strict turnstile model。

缺点：

  • 空间有额外 ；
  • randomized，存在失败概率；
  • 估计是 overestimate：

并且误差按 控制。

Overestimate 什么时候更好?

找 heavy hitters 时，overestimate 方便保证不漏掉真正 heavy hitter。

例如要输出包含所有：

的集合。若 ，则只要真实 ，估计也 ，不会 false negative。

本题用到的知识点:

  1. MG 是 deterministic underestimate。
  2. CMS 是 randomized overestimate。
  3. Linear sketch 便于分布式 merge。
  4. Heavy hitter 任务中 overestimate 有利于 recall。

Problem Solving

Problem 4: 同样空间下 CountSketch 与 CountMinSketch guarantee 比较

题目: 忽略常数和 ，同样空间 budget 下，CountMinSketch 和 CountSketch 的 theoretical guarantee 谁更好？

题解:

CountSketch guarantee：

且：

CountMinSketch guarantee：

且：

现在固定同样空间 。若令 CountSketch 的参数为 ，则：

对于 CMS，在同样空间下可用更小参数 ，得到：

比较：

由于：

二者不可简单排序。

CMS 更好的 regime

若 ，则：

CMS 更好。

CountSketch 更好的 regime

若 很分散，例如均匀频率，则：

当 是常数时：

CountSketch 更好。

结论：同样空间下二者 guarantee incomparable，取决于 frequency vector 的形状和 。

本题用到的知识点:

  1. CountSketch 是 error。
  2. CountMinSketch 是 error。
  3. norm 关系决定比较结果。
  4. 稀疏/集中与分散 frequency vector 的 regime 不同。

Problem 5: CountMinSketch 扩展到 strict turnstile

题目: 把 CountMinSketch 分析推广到 strict turnstile model。更新是 ，其中 可正可负，但任何时刻都保证 。能否推广到 general turnstile？

题解:

在 strict turnstile 中，最终所有频率仍满足：

CountMinSketch 对 的某一行估计可以写为：

因为 strict turnstile 保证 ，所以 collision noise：

是非负随机变量。

其期望：

用 Markov：

取 ，单行失败概率常数。多行取 minimum 放大成功概率。

因此 strict turnstile 下 CMS 仍能给出：

以高概率成立。

为什么 general turnstile 不行?

General turnstile 允许某些 。这时 collision noise 可能为负，不再是非负随机变量，Markov inequality 不能用。

而且估计也不再一定 overestimate：

不一定成立。

所以 CMS 的标准 overestimate analysis 不能直接推广到 general turnstile。

本题用到的知识点:

  1. Strict turnstile 保证 frequencies 非负。
  2. CMS analysis 依赖 Markov inequality。
  3. Markov 需要非负随机变量。
  4. General turnstile 要用 CountSketch 等可处理正负噪声的 sketch。

Problem 6: Misra-Gries 是 sketching algorithm

题目: 对两个 stream 分别运行 Misra-Gries，得到 。说明如何 combine，并证明仍有 MG guarantee。它是 linear sketch 吗？

题解:

合并算法：

  1. 先相加：

  1. 如果非零 entries 超过 ，设 是第 大的值；
  2. 对所有 ：

a) 为什么最多 个非零项?

按定义 是第 大值。所有小于等于 的 entries 在减去 后变成 0。严格大于 的 entries 最多 个，所以剩下非零项最多 个。

b) 误差 guarantee

Misra-Gries 有更精细的形式：若 stream 长度为 ，最终 counters 总和为 ，则：

对 分别有：

相加后，误差至多：

再做 subtract 的 pruning，误差额外增加至多 。

而 pruning 后 counter 总和变为 ，有：

所以：

最终误差：

这正是对拼接 stream 运行 MG 时的同类 guarantee。

c) 是否 linear sketch?

不是 linear sketch。

原因：combine 不是简单向量加法，还需要“减去第 大值并截断为 0”的非线性操作。

所以 Misra-Gries 是 mergeable sketch，但不是 linear sketch。

本题用到的知识点:

  1. Sketching algorithm 的 mergeability。
  2. Misra-Gries 的 stronger invariant。
  3. Pruning step 控制非零项数。
  4. Mergeable 不等于 linear。

Advanced

Problem 7: CountMinSketch 输出 heavy hitters

题目: 修改 CountMinSketch，使其在 strict turnstile model 中输出集合 ，满足：

其中：

题解:

Week 9 PDF 中该题只列出题干，下面给出标准解法。

运行 CountMinSketch，内部误差参数取：

并把失败概率设为：

这样对所有 同时成立的概率至少 ，由 union bound 得到。

在 strict turnstile 中，CMS guarantee：

另外维护 exact total mass：

在 strict turnstile 中每次更新 后， 可同步加 ，因为总频率变化就是 。

最后枚举所有 ，输出：

若 ，即 ，因为 ，所以：

因此 。

若 ，则：

又：

所以：

即 。

空间：

若只要求常数成功概率，可把 简写为 。

本题用到的知识点:

  1. CountMinSketch overestimate + additive error。
  2. Strict turnstile 可维护 exact 。
  3. Threshold sandwich。
  4. 对所有 个 query 同时成立要用 union bound。

Part 2: Week 9 讲义知识点

0. 基础版导读：sketch 到底是什么?

Week 9 继续 streaming，但重点从“为某个问题设计小空间算法”转到 sketching。

可以把 sketch 理解成：

把一个很长的 frequency vector 压缩成一个很短的 summary，同时仍能近似回答某些 query。

如果 universe 有 个元素，完整的 frequency vector 是：

直接保存它需要 空间。Sketch 的目标是用远小于 的空间，例如 polylogarithmic space，估计某个坐标 、某个 norm，或找 heavy hitters。

sketch 和普通 streaming summary 的区别

一个重要性质是 mergeability。如果两个 stream 分别产生 frequency vectors 和 ，合并后的 stream 对应 。好的 sketch 通常满足：

可以由 和 快速合并得到。

最强、最常见的形式是 linear sketch：

其中 是一个随机矩阵。因为线性性：

这就是为什么 CountSketch、CountMinSketch 等结构可以处理 stream updates：每次 update 只是在 sketch 的少数位置加上相应变化。

cash register、strict turnstile、general turnstile

读 Week 9 题目一定要先看更新模型：

  • Cash register / insertion-only：只增加，。
  • Strict turnstile：允许 ， 可正可负，但保证所有真实频率始终非负。
  • General turnstile：允许坐标为负。

CountMinSketch 依赖“噪声非负”来得到 overestimate，因此最自然用于 insertion-only，也可扩展到 strict turnstile 的非负最终频率场景。CountSketch 有随机 signs，可以处理 general turnstile。

CountSketch 的直觉

CountSketch 用多个 hash tables。每一行有：

  • bucket hash ，决定元素 去哪个 bucket。
  • sign hash ，决定加正号还是负号。

当 stream 中对 item 有 update 时，第 行更新：

查询 时，第 行给出估计：

为什么要乘回 ? 因为 item 自己被存进去时带了 ，查询时乘回来就恢复成正的 。

同 bucket 的其他元素会形成噪声：

随机 signs 让噪声期望为 0，方差可以由 控制。所以 CountSketch 的误差通常是 型：

多行取 median 是为了把单行常数成功率放大成高概率。

CountMinSketch 的直觉

CountMinSketch 不使用 signs。每行只把 update 加到 bucket：

在 insertion-only 中，查询 时每一行都是：

其他撞进来的非负频率

所以每一行都不会低估 。取 minimum 可以尽量选择噪声最小的一行：

因此 CMS 的 guarantee 是 one-sided：

with high probability。

这和 Bloom filter 很像：Bloom filter 也不会 false negative，只会 false positive；CMS 不会 underestimate，只会 overestimate。

CountSketch vs CountMinSketch 怎么比较?

核心差异：

  • CountSketch 用 signs 抵消噪声，误差跟 有关。
  • CountMinSketch 不抵消，只取 minimum，误差跟 有关。
  • CountSketch 可处理 general turnstile。
  • CountMinSketch 更适合非负频率，因为它依赖 overestimate。

什么时候 guarantee 更好? 如果频率分布很集中， 可能远小于 。

什么时候 guarantee 够用? 如果只需要 heavy hitters，且 heavy threshold 本来就是 ，CMS 很直接。

norm 关系为什么常出现?

Week 9 题目会用：

和：

这些不等式用来比较不同 sketch 的误差。你可以用极端例子理解：

  • 如果质量集中在一个坐标，。
  • 如果质量均匀分布在很多坐标， 会比 大很多。

做题时怎么下手?

  • 题目问是否是 sketch：检查两个 summaries 能否合并。
  • 题目问是否 linear sketch：看 summary 是否能写成 。
  • 题目问 CMS：强调 no underestimation、take minimum、 error。
  • 题目问 CountSketch：强调 random signs、median、 error。
  • 题目问 turnstile：有负更新时，优先考虑 CountSketch；CMS 需要非负频率保证。
  • 题目问 heavy hitters：把阈值写成 或 ，再用 sketch error bound 证明不会漏报。

1. Sketching algorithm

Sketching 关心：能否把两个 stream 的 summary 合并成 concatenated stream 的 summary。

若算法 满足：

则它是 sketching algorithm。

若进一步：

则是 linear sketch。

Linear sketch 特别适合：

  • distributed streaming；
  • parallel computation；
  • turnstile updates。

2. Cash register vs turnstile

Cash register：

频率只增不减。

Turnstile：

可以增加或减少。

Strict turnstile：

整个过程中始终：

General turnstile：

允许中间或最终频率为负。

3. CountSketch

CountSketch 使用：

  • hash ；
  • sign hash ；
  • array 。

更新 ：

查询：

估计是 unbiased：

方差：

取：

并用 median trick，可得：

以 概率成立。

空间：

4. CountSketch 是 linear sketch

只要两个 sketches 使用相同 hash functions ，对两个 streams 的 updates 分别累加后，相加 arrays 等同于在拼接 stream 上处理全部 updates。

所以：

5. CountMinSketch

CMS 使用 行，每行一个 hash function：

更新 ：

查询：

在 cash register / strict turnstile 中：

且：

以 概率成立。

参数：

空间：

6. CountMinSketch 为什么用 minimum?

单行估计是：

noise 非负。每行可能因为 collision 太大而 overestimate。取 minimum 就是在多次独立尝试中选噪声最小的那次。

失败事件：

等价于所有行都坏，因此概率指数下降：

7. CountSketch vs CountMinSketch

项目 CountSketch CountMinSketch
Model turnstile cash register / strict turnstile
Error
Bias unbiased overestimate
Space in
Amplification median trick built-in min over rows
Handles negative frequencies yes not by standard proof

8. Applications of sketching

Week 8-9 going-further reading 强调 sketching 的应用路径：

  • 网络流量统计；
  • 数据库 query approximation；
  • distributed monitoring；
  • heavy hitters；
  • approximate histograms；
  • ML/linear algebra 中的 random projection。

理论上，sketch 的核心价值是把高维频率向量压缩成小空间 summary，同时保留可 merge、可 query 的性质。

本周核心记忆

主题 关键结论
Sketching summaries 可合并
Linear sketch 合并就是向量相加
CountSketch error, turnstile
CountSketch space
CMS error, overestimate
CMS space
MG mergeable but not linear
Strict turnstile ，CMS analysis 可用
General turnstile CMS 标准 Markov proof 失效