Space Saving Algorithm

Summary

topk问题：从一个数组中取出出现频率最高的k个元素。这个问题最简单的想法就是弄一个map，用来保存key和value，（value表示key出现的次数）。最后选择value最大的前k个key，就可以得到解决。但是当元素的数量很多的时候，那么map里的key会非常多，如果超过了机器的内存的话，这个方法就不可行了。我们需要一个方法来解决这个问题，那就是Space Saving Algorithm, 这是一个概率性的方法，存在一定的误差，但是基本可以解决topk的问题。至于为什么叫Space Saving，大概就是因为它只需要保存k个 key，value，比起原始的保存所有的kv更节省空间？

这里我们会分为三个大点来介绍SS。

  1. Space Saving Algorithm(最原始的方法)
  2. Filtered Space Saving Algorithm(优化方向1)
  3. Parallel Space Saving Algotithm(优化方向2)
  4. ClickHouse中的SpaceSaving

Space Saving Algorithm

  1. 用一个cap为k的map来记录结果，count初始化为0
  2. 读取key并存入map，count++，直到map.size() == k
  3. 如果遇到新的key
    • key in map: 对应的count++（i.e.map[key]++)
    • key not in map: 把count最小的key替换为新key，并且count++；
  4. 最后读取完数据流之后，返回最后的map

Filtered Space Saving Algorithm

比起基本的SS算法， FSS在遇到新key的替换策略上做了优化，使得出现误差的可能性更低。detail paper 加了一个bitcount的数据结构来处理新key。 FSS

Parallel Space Saving Algorithm

detail paper PSS

CK中的Space Saving Algorithm

CK中的topk函数使用的SpaceSaving结合了上面的两个论文里的优点，就是PSS 方法中的SS替换成了FSS.