在深入 Filtered-Space Saving 算法之前，我们先聊聊 Space-Saving 算法，它由 Metwally 等人在 [1] 中提出。Space-Saving 的核心思想是只监控预先设定数量的 m 个元素及其对应的计数器。每个计数器都会随时更新，用来记录该元素可能出现的最大次数，以及这一估计中可能包含的误差。如果一个已在监控中的元素再次出现，就把它频率估计的计数器加一。如果该元素当前不在监控之列，则一律将其加入列表。如果元素数量已达上限，就丢弃出现次数估计最低的那个元素。新元素的估计误差取自被丢弃元素的频率估计，其频率估计则等于该误差加 1。
Space-Saving 算法会在列表中保留所有出现次数可能不低于「新的估计误差值」（也就是最后被丢弃元素的估计值）的元素。这样能保证不产生假阴性（false negatives），但允许出现假阳性（false positives）。那些在数据流末尾才出现的低频元素，留在列表中的概率也更高。
Filtered-Space Saving（FSS）在 Space-Saving 的基础上引入过滤（filtering）思路加以改进，它把数据结构与算法组合在一起，能在只占用常数、极小内存的前提下，准确估计数据流中出现频率最高的 top-k 个值。计算 top-k 最直白的做法，就是维护一张记录各个值及其频率的表，但这对数据流来说并不实用。
FSS 的做法是把流入的值 hash 到各个 bucket 中，每个 bucket 里都保存着一组已加入的值。如果流入的元素在对应 bucket 中已经存在，就把它的频率加一；如果尚不存在，则只要满足若干可配置的条件，就将其加入。
FSS 的一份 golang 实现见这里。
References
- A. Metwally, D. Agrawal, A. Abbadi, Efficient Computation of Frequent and Top-k Elements in Data Streams, Technical Report 2005-23, University of California, Santa Barbara, 2005.
- Homem, Nuno, and J. P. Carvalho. Finding top-k elements in data streams, Elsevier Science Inc., 2010.