Improved Frequency Estimation Algorithms with and without Predictions
Improved Frequency Estimation Algorithms with and without Predictions
复制标题
DOI：
10.48550/arxiv.2312.07535
复制
发表时间：
2023-12
期刊：
影响因子：
--
通讯作者：
Anders Aamand;Justin Y. Chen;Huy Le Nguyen;Sandeep Silwal;A. Vakilian
中科院分区：
文献类型：
--
作者：
Anders Aamand;Justin Y. Chen;Huy Le Nguyen;Sandeep Silwal;A. Vakilian
估计数据流中出现的元素的频率是大规模数据分析的关键任务。解决这个问题的流行草图绘制方法（例如CountMin和countssketch）提供了最坏情况的保证，即对任何可能输入的估计频率的误差进行概率限制。Hsu等人（2019）的工作介绍了使用机器学习来定制草图算法以适应它们正在运行的特定数据分布的想法。特别是，他们的学习增强频率估计算法使用一个学习的重量级预言器来预测哪些元素将在流中出现多次。我们给出了一种新的算法，该算法在一些参数制度下，理论上已经优于Hsu等人的基于学习的算法，而无需使用任何预测。用重量级的预测来增强我们的算法，进一步减少了错误，提高了技术水平。从经验上看，我们的算法在所有实验中都比以前的方法具有更好的性能。
Estimating frequencies of elements appearing in a data stream is a key task in large-scale data analysis. Popular sketching approaches to this problem (e.g., CountMin and CountSketch) come with worst-case guarantees that probabilistically bound the error of the estimated frequencies for any possible input. The work of Hsu et al. (2019) introduced the idea of using machine learning to tailor sketching algorithms to the specific data distribution they are being run on. In particular, their learning-augmented frequency estimation algorithm uses a learned heavy-hitter oracle which predicts which elements will appear many times in the stream. We give a novel algorithm, which in some parameter regimes, already theoretically outperforms the learning based algorithm of Hsu et al. without the use of any predictions. Augmenting our algorithm with heavy-hitter predictions further reduces the error and improves upon the state of the art. Empirically, our algorithms achieve superior performance in all experiments compared to prior approaches.