Identifying heavy hitters and estimating the frequencies of flows are
fundamental tasks in various network domains. Existing approaches to this
challenge can broadly be categorized into two groups, hashing-based and
competing-counter-based. The Count-Min sketch is a standard example of a
hashing-based algorithm, and the Space Saving algorithm is an example of a
competing-counter algorithm. Recent works have explored the use of machine
learning to enhance algorithms for frequency estimation problems, under the
algorithms with prediction framework. However, these works have focused solely
on the hashing-based approach, which may not be best for identifying heavy
hitters. In this paper, we present the first learned competing-counter-based
algorithm, called LSS, for identifying heavy hitters, top k, and flow frequency
estimation that utilizes the well-known Space Saving algorithm. We provide
theoretical insights into how and to what extent our approach can improve upon
Space Saving, backed by experimental results on both synthetic and real-world
datasets. Our evaluation demonstrates that LSS can enhance the accuracy and
efficiency of Space Saving in identifying heavy hitters, top k, and estimating
flow frequencies.

通过使用基于竞争计数的算法，我们提出了一种称为 LSS 的学习算法，用于识别重要对象、top k 以及流量频率的估计，该算法充分利用了众所周知的 Space Saving 算法，并提供了理论洞察以及基于综合和真实世界数据集的实验结果，验证了 LSS 在提高 Space Saving 的准确性和效率方面的能力。