用预测过滤长间隔出现的物品，显著提升滑动窗口频率估计的内存效率。
Learning-Augmented Frequency Estimation in Sliding Windows
- 通过预测下一次出现时间长的项目并提前过滤
- 在真实数据集上实现更优的内存-精度权衡
- 适合需要高效流式处理的系统设计者
我们展示了如何在「带预测的算法」框架下，利用机器学习方法改进滑动窗口中近似频率估计的算法。在动态环境中，以往的学习增强型算法效果不佳，因为滑动窗口内的特性与全流数据差异显著。本文聚焦于预测并过滤掉下一次出现时间较长的项目——即其下次出现存在较大间隔——从数据流中，从而显著改善内存与准确率之间的权衡。我们给出了理论定理，揭示该技术提升的程度，并在真实数据集上进行了实验验证。结果表明，预测器在具有挑战性的滑动窗口场景中依然具有实际价值。
原文摘要 · Abstract (English)
We show how to utilize machine learning approaches to improve sliding window algorithms for approximate frequency estimation problems, under the ``algorithms with predictions'' framework. In this dynamic environment, previous learning-augmented algorithms are less effective, since properties in sliding window resolution can differ significantly from the properties of the entire stream. Our focus is on the benefits of predicting and filtering out items with large next arrival times -- that is, there is a large gap until their next appearance -- from the stream, which we show improves the memory-accuracy tradeoffs significantly. We provide theorems that provide insight into how and by how much our technique can improve the sliding window algorithm, as well as experimental results using real-world data sets. Our work demonstrates that predictors can be useful in the challenging sliding window setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。