与上一篇一样，本文来自于算分小班课的一个 challange。这个版本是一个摘要；想要看一个更详细的版本可以戳页面右上角看英文版。（两个版本的变量名不相同。）\(\def\eps{\varepsilon}\DeclareMathOperator{\plog}{ProductLog}\)
假设读者对数据流算法的一些常识和 Space Saving 算法有一些基础了解。下面我们证明，如果一个确定性算法足够类似于 Space Saving，那么它求解 Top-\(k\) 时不可能比 Space Saving 在 Zipf 分布数据的渐近复杂度上更优。
背景
我们的设定如下。给定一个数据流，每个元素都在集合 \(A\) 中。某个用于计算 Top-\(k\) 的算法，在内存中追踪了 \(m\) 个不同的元素，然后为每个元素追踪了一些信息。我们不关心这些信息是什么样子的。一个关键的假设\(\left( * \right)\)是，所有未被追踪的item对算法来说看起来都是一样的。换言之，如果一个 \(\text{item}\) 不在当前追踪的元素中，那么把它换成另一个未被追踪的元素，算法应该有相同的行为。进一步地，算法不能“变出”元素来：假设新来一个元素 \(x\) 之前，原本追踪的元素是 \(a_{1}\cdots a_{m}\)，那么这一步之后追踪的至多 \(m\) 个元素必然是 \(\left\{ x,a_{1},\cdots,a_{m} \right\}\) 的子集。此外，该算法是确定性的。
我们假设输入是 Zipf 的：排名为 \(i\) 的元素出现了 \(\frac{X}{i}\) 次，但其顺序可以被 adversary 恶意构造。则数据流的总大小是 \(W = X \times H_{\left| A \right|}\)，其中 \(H_{i}\) 代表调和级数。
攻击方式
我们的 adversary 试图构造一个序列，使得排名第 \(k\) 的元素被低估尽可能多次。下文中，我们用元素的排名来称呼这个元素；换言之，“元素 \(a\)”指的是“排名为 \(a\) 的元素”。
我们设算法连续接受了 \(\mathcal{W}\) 个元素 \(s_{1}\cdots s_{\mathcal{W}}\)，且其中的每个都是“当前不在追踪的元素”。一个 \(s_{i}\) 出现之后，如果它没有被算法追踪，我们称作出现了一次 rejection。我们先假设没有 rejection 出现。
我们设算法维护了 \(m\) 个格子 \(g_{1}\cdots g_{m}\)，分别存着追踪的元素。对于 \(s_{1}\cdots s_{\mathcal{W}}\) 中的每个元素，它总是会占据一个新的格子，然后把这个格子原来的元素顶替掉。我们设 \(c_{1},\cdots,c_{\mathcal{W}}\) 分别表示每个新元素占据了哪个格子（编号）。由于抽屉原理，我们知道总存在一个 \(g_{i}\)，使得 \(\left| \left\{ j\mid c_{j} = i \right\} \right| > \frac{\mathcal{W}}{m}\)，也就是说这个格子被更新了至少 \(\frac{\mathcal{W}}{m}\) 次。设 \(T = \left\{ j\mid c_{j} = i \right\} = \left\{ T_{1},\cdots,T_{\mathcal{l}} \right\}\)，其中 \(T_{1} < T_{2} < \cdots < T_{\mathcal{l}}\)。我们把 \(t_{T_{1}},t_{T_{3}},t_{T_{5}},\cdots,t_{T_{2j + 1}},\cdots\) 全部替换成 \(k\)，注意到此时 \(t\) 序列中的每个元素依然是“当前不在追踪的元素”（因为每次 \(k\) 被算法追踪之后，都会被其后面的 \(t_{T_{2j}}\) 顶替掉，才会再次出现）。如此做之后，\(k\) 会在序列中出现 \(\frac{\mathcal{l}}{2}\) 次，最终会被算法忘掉。我们知道 \[ \frac{\mathcal{l}}{2} \geq \frac{\mathcal{W}}{2m} \] 如果出现了 rejection，我们可以把被 reject 的那些全部换成 \(k\)，由于算法是确定性的，这些 \(k\) 的出现次数全部会被浪费掉，因此这个 \(\frac{1}{2m}\) 的比例不会降低。
我们现在构造一个尽可能长的 \(s\) 序列，使得其中的每个在加入的时候都是“当前不在追踪的元素”。设 \[ S_{1} = \left\{ 2m + 1,\cdots,\ 2m + 2m \right\},S_{2} = \left\{ 4m + 1,\cdots,\ 4m + 2m \right\},\cdots,S_{j} = \left\{ 2jm + 1,\cdots,\ 2jm + 2m \right\} \] 由于Zipf分布的性质，\(S_{j}\) 中的每个元素出现了至少 \(\frac{X}{2\left( j + 1 \right)m}\) 次。
我们先把 \(S_{1}\) 的元素依次放进数据流，【然后观察此时算法的内部状态的至多 \(m\) 个元素构成的集合 \(S\)。此时 \(S_{1} \smallsetminus S\) 至少有 \(m\) 个元素，因此可以把它们依次放进数据流，】注意到方括号中的过程可以持续做至少 \(\frac{X}{2\left( 1 + 1 \right)m}\) 次。此后，我们可以对 \(S_{2}\) 做一样的事情，对 \(S_{3},S_{4},\cdots\) 同理，以此类推。
这样我们的数据流长度会是 \[ \mathcal{W \geq}\sum_{1 \leq j \leq z}^{}{\frac{X}{2\left( j + 1 \right)m} \times m} = \frac{X}{2}\left( H_{z + 1} - 1 \right) \approx \frac{X}{2}\left( \ln\left| A \right| - \ln m - \ln 2 - 1 \right) \] 代入上面的式子，我们知道，只要 \(\frac{\mathcal{W}}{3m} > \frac{X}{k^{2}} > \frac{X}{k} - \frac{X}{k + 1}\)，即 \(\frac{X}{6m}\left( \ln\left| A \right| - \ln m - \ln 2 - 1 \right) > \frac{X}{k^{2}}\) 时，我们能按上面的方法构造输入，来让算法在计算Top-\(k\) 时犯错。
注意到上述过程中，每个元素 \(i\) 都出现了 \(\leq \frac{X}{i}\) 次。为了让整个数据符合 Zipf 分布，我们把所有剩下多出来的次数全部以任意的顺序加进去。我们知道算法在这个过程中不可能获取额外的信息来区分出 \(k\) 和 \(k + 1\)。（如果算法碰巧发现了正确的，可以直接交换二者。）
最后的式子大概是 \(6m \ge k^{2}\left( \ln\left| A \right| - \ln m - \ln 2 - 1 \right)\)，化简一下是 \(m\ge\Theta\left(k^2\plog \left(\frac{|A|}{k^2}\right)\right)\)。在 \(k\) 不太大的时候，换言之 \(k=|A|^{\frac 12-o(1)}\) 的时候，Space Saving 是最优的。（同样，利用 \(\plog\) 在 \(\to 0\) 时的性质，可以发现在 \(k>\sqrt{|A|}\) 时也是最优的。）
结论
上述证明可以用于攻击在一类基于 Space-Saving 的优化上。这些优化包括但不限于：
对 \(\text{count}\) 与 \(\varepsilon\) 做一些额外的处理
维护额外的统计信息（包括进入的时刻等）
对数据结构分级，对不同级别使用不同的策略(Friedman, Goaz and Rottenstreich, 2021)，或者维护一些类似队列的结构(Zhou, Chen and Xiong, 2010)
使用随机化方法来调整 \(\text{count}\) 等(Basat et al., 2016)
但有很多 Top-\(k\) 求解算法绕过了这一限制。我们的算法要求”所有没有被追踪的元素看起来是一样的”，但以下方法不符合上述假设：
使用一个 CM-Sketch 或者别的什么东西来带误差地未追踪的元素的个数(Homem and Carvalho, 2010)
别的依赖于元素的哈希的东西
根据上述结论，如果一个 Top-\(k\) 算法要比 Space-Saving 具有理论上的优越性，它必须引入这样的东西才能成功。然而 CM-Sketch 的理论分析就远远没有这么简单了。
参考文献
Basat, R. B. et al. (2016) Randomized Admission Policy for Efficient Top-k and Frequency Estimation, arXiv:1612.02962 [cs]. Available at: http://arxiv.org/abs/1612.02962.
Friedman, R., Goaz, O. and Rottenstreich, O. (2021) Effective Space Saving, in International Conference on Distributed Computing and Networking 2021. New York, NY, USA: Association for Computing Machinery (ICDCN ’21), pp. 66–75. doi: 10.1145/3427796.3427803.
Mitzenmacher, M., Steinke, T. and Thaler, J. (2012) Hierarchical Heavy Hitters with the Space Saving Algorithm, in 2012 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics (Proceedings), pp. 160–174. doi: 10.1137/1.9781611972924.16.
Zhou, J., Chen, M. and Xiong, H. (2010) A More Accurate Space Saving Algorithm for Finding the Frequent Items, in 2010 2nd International Workshop on Database Technology and Applications, pp. 1–5. doi: 10.1109/DBTA.2010.5659027.