SieveSketch：一种用于精确频率估计的细粒度、自适应草图框架

《Proceedings of the ACM on Management of Data》：SieveSketch: A Fine-grained and Adaptive Sketch Framework for Accurate Frequency Estimation

冷热项自适应过滤与细粒度计数框架提升数据流频率估计精度

　　

摘要

在数据流中估计项目频率是一项基础任务，它支持着广泛的应用场景。为了提高准确性，现有算法通常使用过滤器分别处理冷（不频繁出现）和热（频繁出现）的项目。然而，由于参数设置固定，这些算法在不同数据流上的准确性往往会下降。一旦过滤器达到其容量上限，就无法有效区分目标项目，从而导致准确性大幅下降。为了实现更高的准确性和更好的数据流适应性，我们提出了SieveSketch，这是一个用于数据流处理中的频率估计的新框架。SieveSketch借鉴了两个观察结果：一是冷项目频率范围较窄，二是项目对哈希碰撞的敏感度不同。该框架采用自适应缩放机制，通过少量比特（例如4比特）来调整每个计数器的计数范围，从而高效地记录大量冷项目；同时采用基于频率的计数方法，在更细粒度的层面处理项目，以提高准确性。我们对SieveSketch的误差范围进行了理论分析，并在真实世界和合成数据集上进行了大量实验。实验结果表明，与现有技术相比，SieveSketch的估计误差降低了多达222.1倍。