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

Posted on 2026-06-01 Edited on 2026-05-31 In Course Notes , COMP5270 Word count in article: 4.3k Reading time ≈ 16 mins.

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

Part 1: Tutorial 8 详细题解

Warm-up

Problem 1: Morris counter 的 median-of-means 证明

题目: 复习 Morris counter 的 median-of-means proof，证明讲义中的结果。

题解:

Morris counter 返回的估计记为。讲义给出：

以及：

因此是无偏估计：

但方差是。如果直接用 Chebyshev：

当时，这个 bound 可能大于 1，没用。

解决办法是先做 average：

运行个独立 Morris counters，取平均：

期望仍然是，方差下降倍：

取：

即可让 Chebyshev 给出常数成功概率，即：

然后用 median trick：独立重复这个“平均估计器” 次，取中位数，把失败概率降到。

本题用到的知识点:

Morris counter 的无偏性与大方差。
平均个独立估计器使方差除以。
Chebyshev 给常数成功率。
Median trick 做概率放大。

Problem 2: Mean-of-medians 为什么不行?

题目: 若不用 median-of-means，而是反过来用 mean-of-medians，会怎样？

题解:

mean-of-medians 的问题是：Morris counter 单次估计一开始就不是“常数概率足够准”的估计器。

median trick 的前提是：每个 block 的估计已经有至少的概率是 good。然后取中位数可以过滤掉少数 bad blocks。

但如果一开始直接取若干个 Morris counters 的 median，由于每个单独 counter 方差太大，good probability 可能很低。此时中位数不一定好。

换句话说：

means 的作用：先降方差，让一个 block 变得可靠；
median 的作用：把可靠 block 的失败概率放大到很小。

顺序不能随便换。

本题用到的知识点:

Median trick 需要 base estimator 有常数成功概率。
Means 降方差，median 降失败概率。
方差太大的单估计器不能直接取 median。

Problem 3: BJKST 使用 truly random hash functions 的空间

题目: 如果 BJKST 算法不用 strongly universal hash family，而用 truly random hash functions，空间会变成多少？

题解:

Truly random hash function 需要为每个输入存一个输出。

每个输出需要：

bits，一共有个输入，所以存储需要：

bits。

而 strongly universal hash family 的好处是：只需存随机 seed 或少量参数，通常：

bits 就能描述一个 hash function。

所以 streaming 算法必须避免 truly random hash function，否则仅 hash function 本身就太大。

本题用到的知识点:

Truly random function 表需要为每个输入存输出。
Strongly universal hash family 可用短 seed 描述。
Streaming space 要把 hash seed 也算进去。

Problem 4: BJKST 为什么还要用 ?

题目: BJKST 算法中为什么用 hash function ？如果 bucket 里直接存会怎样？

题解:

BJKST 要维护通过 tidemark threshold 的 distinct elements，但直接存元素每个需要：

bits。

如果 bucket 大小约为，直接存的空间会有一项：

甚至还要乘上 log factors。

使用另一个 hash function：

是为了存较短的 fingerprint ，减少每个候选元素的存储成本，同时仍能以高概率区分 distinct elements。

因此的作用是 space saving。

本题用到的知识点:

Streaming algorithm 中存元素 ID 的成本很贵。
Fingerprinting/hash compression。
BJKST 用做 sampling level，用做 compact representation。

Problem Solving

Problem 5: Careful Morris counter

题目: 分析 careful variant of Morris counter：不再以概率把翻倍，而是以概率把乘以。

题解:

令是第次更新后 counter 的值，初始：

当第个事件到来时，令表示是否发生 increment：

更新：

a) 期望

条件在上：

因为：

所以：

取全期望：

由得：

因此估计真实计数是无偏的。

b) 方差

计算二阶矩：

因为：

用展开：

因此：

所以：

c) 用 median trick

由 Chebyshev：

若取，就能得到常数成功概率。再用 median trick 重复：

次，空间约为：

d) 不用 median trick

若希望单个 counter 直接失败概率，令：

可由 Chebyshev 直接得到：

存 exponent ，其中：

所以：

存需要：

这得到讲义中的 additive log bound。

e) 如何实现概率 ?

理论上可以从均匀采样，若：

则 increment。

在有限计算机上，可先把取为有理数，满足：

因为，所以：

也是有理数。若该概率写成，则采样 uniformly from ，当时返回 1。

本题用到的知识点:

Conditional expectation 计算 Morris-style counter。
二阶矩推方差。
Chebyshev 控制 multiplicative error。
median trick 与 careful parameter tuning。
有理概率 Bernoulli sampling。

Problem 6: Misra-Gries 输出 heavy hitters

题目: 给定 stream 长度和，定义：

修改 Misra-Gries 输出集合，满足：

空间。

题解:

运行 Misra-Gries，参数取：

Misra-Gries guarantee：

因为，所以：

输出：

若，则：

所以：

因此，即：

反过来，若，则：

又因为，所以：

即：

因此：

空间方面，Misra-Gries 只存个 key-counter pair，每个需要 bits：

本题用到的知识点:

Misra-Gries additive underestimate guarantee。
Heavy hitter threshold sandwich。
选择让误差变成。

Problem 7: Bottom- distinct elements algorithm

题目: Bottom- 算法：随机选 strongly universal hash ，维护 stream 中 distinct elements 的个最小 hash values，最后返回：

证明时以常数概率给出估计，并分析空间。

题解:

令是 distinct elements 数量。直觉是：若个 distinct items 的 hash 值像上均匀点，那么第小的值大约在：

附近，所以：

应接近。

上尾：

这等价于第小 hash 值过小：

定义 indicator：

对个 distinct items 求和：

若，则至少个元素 hash 到该阈值以下，即。

期望：

strongly universal 给出 pairwise independence，所以：

用 Chebyshev，当时：

可调常数使其。

下尾：

这等价于第小 hash 值过大：

定义：

若，则阈值以下元素少于个。

同理：

用 Chebyshev，当：

时下尾概率也可控制为。

Union bound 后，以至少概率：

再用 median trick 可把成功概率提升到。

空间复杂度

需要存：

hash function seed：；
个 hash values；
若做 median trick，再乘。

所以：

bits 级别。

本题用到的知识点:

Order statistics：第小 hash 值约为。
Strongly universal 提供 pairwise independence。
Chebyshev 足够分析 Bottom-。
Median trick 放大成功概率。

Advanced

Problem 8: 用 JL sketch 估计 stream 中平均向量大小

题目: stream 中每个元素，目标估计：

的，要求 2-approximation，成功概率至少。忽略存随机 bits 的成本，给出小空间算法。

题解:

使用 JL random projection。

取随机矩阵：

其中：

取，，则。

JL 保证对固定向量：

以高概率成立。

streaming 中维护：

因为是线性的：

最后：

输出：

作为的估计。

空间上，只存维向量和 counter 。若忽略本身随机 bits 的存储，空间非常小：

其中。

随机 bits 若朴素存 Gaussian matrix，需要个随机值；课程 solution 粗略写为级别。

本题用到的知识点:

JL lemma 保持 norm。
Linear sketch：。
Streaming 中只维护 sketch 向量，不存原始数据。
忽略随机矩阵存储时空间可很小。

Part 2: Week 8 讲义知识点

0. 基础版导读：streaming 为什么不是普通数组问题?

Week 8 开始进入 Streaming and Sketching。Streaming model 的限制是：

数据一个一个到来，只能顺序看，不能把所有数据都存下来。

例如网络 packet、搜索日志、点击流、交易流。数据长度可能极大，而内存远小于。所以 streaming algorithm 的目标不是完整保存数据，而是在小空间中维护足够回答问题的 summary。

frequency vector 是核心语言

很多 stream 都可以表示成 frequency vector：

表示 item 出现了多少次。例如 stream 是：

那么，，，其他坐标是 0。

常见任务：

: distinct elements 数量，即。
: stream 总长度，即。
heavy hitters: 找出频率很大的元素。
norms: 估计等。

讲义中的算法经常不保存整个，而是保存一个小 summary。

stream 类型要先分清

读题时先判断更新形式：

Insertion-only / cash register：只会出现。
Strict turnstile：允许加减，但保证最终。
General turnstile：允许加减，可以为负。

Week 8 主要关注 insertion-only；Week 9 会更系统讨论 sketch 和 turnstile。

Misra-Gries 的直觉：抵消法

Misra-Gries 用来找 heavy hitters。它维护最多个候选元素和 counters。

处理新元素：

如果已在表中，counter 加 1。
如果不在表中且表未满，把放入，counter 设为 1。
如果不在表中且表已满，所有 counters 减 1，减到 0 的删除。

第 3 步的直觉是：删除一组个互不相同的元素。真正的 heavy hitter 出现次数非常多，不可能被这种抵消操作完全消掉。

常用 guarantee 是：

也就是说 Misra-Gries 的估计可能低估，但低估量有限。

Morris counter 的直觉：用随机性压缩计数

普通计数器数到需要 bits。Morris counter 希望用约 bits 表示非常大的计数。

它只保存一个 counter 。每来一个元素，不是每次加 1，而是以概率：

把加 1。估计值是：

为什么合理? 当越大，加 1 概率越小，所以的增长会越来越慢。最终大约是，保存只需要 bits。

单个 Morris counter 方差较大，所以要重复：

多个 counter 求平均，降低 variance。
多组平均再取 median，把成功概率放大到。

这就是 tutorial 中 median-of-means 的来源。

distinct elements / 为什么难?

如果只数 stream 长度，普通 counter 就够了。但要数不同元素，重复出现不能重复算。

朴素做法需要保存一个 set，空间可能是。

随机化算法的共同直觉是：

给每个 distinct item 一个随机 hash 值；distinct item 越多，就越可能看到很小的 hash 值。

Bottom- 保存最小的个 hash values。若第小 hash value 是，估计：

因为个均匀随机点落在上，第小大约在附近。

AMS / Tidemark / BJKST 的共同思想

这些算法都估计，角度不同：

Tidemark / AMS：观察 hash 值中 trailing zeros 的最大数量。
BJKST：维护某个 sampling level 下被保留的 distinct items；集合太大就升 level，降低采样概率。
Bottom-：直接保存最小的个 hash values。

共同思想是 subsampling：随机保留一小部分元素，再从样本反推总体规模。

证明套路

要证明无偏：直接算 expectation。
要控制误差：先算 variance，再用 Chebyshev。
要把常数成功率变成：使用 median trick。
分析 distinct elements：把 hash values 看成上的随机点。
分析 heavy hitters：把 decrement-all 看成删除一组互不相同的元素。

1. Streaming model

输入不是一次性给出，而是 stream：

每个来自 universe 。

算法通常只允许 one pass，并且空间：

理想是：

时间通常不是主要限制，空间是核心限制。

2. Frequency vector

对 stream 定义 frequency：

于是：

在 cash register model 中，频率只增不减。

3. Misra-Gries algorithm

目标：以小空间近似所有 frequencies。

参数，令：

维护至多个 counters。

更新规则：

若 item 已有 counter，加 1；
若没有且 counter 数未满，插入并设为 1；
若没有且已满，所有 counters 减 1，减到 0 的删除。

Guarantee：

空间：

Misra-Gries 是 deterministic one-pass algorithm。

4. Majority problem

要找是否存在的 majority element。

用 Misra-Gries 取，第一遍得到候选集，候选集大小常数。第二遍精确计数候选，判断是否超过。

5. Morris counter

普通精确计数到需要：

bits。

Morris counter 只存指数：

初始；
每次事件发生，以概率做；
输出：

性质：

单次方差大，需要 median-of-means 或 careful variant。

6. Careful Morris counter

把 base 从改成：

以概率将乘以；
输出。

通过调，可实现：

估计，并且空间：

这是 doubly logarithmic in 。

7. Distinct elements /

Distinct elements 数：

也叫 estimation。

8. Tidemark / AMS algorithm

取 strongly universal 。

定义：

为二进制 trailing zeros 数。

维护最大 trailing zeros：

输出约：

得到 constant-factor estimate。用 median trick 可把成功率放大。

空间：

9. BJKST algorithm

BJKST 目标是估计 distinct elements。

核心思想：

用的 trailing zeros 做 subsampling level；
用做 compact bucket/fingerprint；
维护一个大小约的 set ；
若太大，提高 threshold 并删掉不够高的元素。

Guarantee：

空间：

10. Week 8-9 going further: data stream algorithms

Chakrabarti 的 streaming notes 进一步系统化了：

one-pass vs multi-pass；
cash register vs turnstile；
frequency moments ；
sketches 的 mergeability；
lower bounds。

本课程 Week 8 的重点是三类典型问题：

问题	工具
frequent elements	Misra-Gries
approximate counting	Morris counter
distinct elements	AMS/Tidemark, BJKST, Bottom-

本周核心记忆

主题	关键结论
Streaming	输入太大，空间是主要资源
Misra-Gries
MG space
Morris counter	级别计数
Morris variance	，需降方差
Careful Morris
Distinct elements
Tidemark	constant-factor
BJKST
Bottom-	第小 hash 值估计 distinct count