优化学习型计数最小映射，提速建模并保证误差上限。
Optimized Learned Count-Min Sketch
- 分域分配独立计数器，参数由理论推导确定
- 构建速度更快，不可接受误差率降低至0.1%以下
- 支持显式设定误差阈值，适合高精度场景
Count-Min Sketch (CMS) 是一种高效的多重集合元素频率估计数据结构。学习型计数最小映射（LCMS）通过引入机器学习模型，在相同内存下降低估计误差，但存在构建慢、依赖经验调参、且无不可接受误差概率的理论保障问题。本文提出优化学习型计数最小映射（OptLCMS），将输入域划分为多个子域，每个子域分配独立的CMS实例，并基于固定阈值解析推导出参数，通过动态规划结合近似可行性检查优化阈值。该方法减少对经验验证的依赖，实现更快速构建，同时在假设条件下提供理论误差保障。此外，可显式控制允许的误差阈值，提升实际应用灵活性。实验表明，OptLCMS 构建速度更快，不可接受误差概率低于0.1%，且估计精度与 LCMS 相当。
原文摘要 · Abstract (English)
Count-Min Sketch (CMS) is a memory-efficient data structure for estimating the frequency of elements in a multiset. Learned Count-Min Sketch (LCMS) enhances CMS with a machine learning model to reduce estimation error under the same memory usage, but suffers from slow construction due to empirical parameter tuning and lacks theoretical guarantees on intolerable error probability. We propose Optimized Learned Count-Min Sketch (OptLCMS), which partitions the input domain and assigns each partition to its own CMS instance, with CMS parameters analytically derived for fixed thresholds, and thresholds optimized via dynamic programming with approximate feasibility checks. This reduces the need for empirical validation, enabling faster construction while providing theoretical guarantees under these assumptions. OptLCMS also allows explicit control of the allowable error threshold, improving flexibility in practice. Experiments show that OptLCMS builds faster, achieves lower intolerable error probability, and matches the estimation accuracy of LCMS.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。