假设读者对数据流算法的一些常识和 space saving

假设读者对数据流算法的一些常识和 Space Saving 算法有一些基础了解。下面我们证明，如果一个确定性算法足够类似于 Space Saving，那么它求解 Top-\(k\) 时不可能比 Space Saving 在 Zipf 分布数据的渐近复杂度上更优。

上述证明可以用于攻击在一类基于 Space-Saving 的优化上。这些优化包括但不限于：

维护额外的统计信息（包括进入的时刻等）

但有很多 Top-\(k\) 求解算法绕过了这一限制。我们的算法要求”所有没有被追踪的元素看起来是一样的”，但以下方法不符合上述假设：

使用一个 CM-Sketch 或者别的什么东西来带误差地未追踪的元素的个数(Homem and Carvalho 2010)

根据上述结论，如果一个 Top-\(k\) 算法要比 Space-Saving 具有理论上的优越性，它必须引入这样的东西才能成功。然而 CM-Sketch 的理论分析就远远没有这么简单了。