接近最优的按键流式分位数估计

《Proceedings of the ACM on Management of Data》:Near-Optimal Per-Key Streaming Quantile Estimation

【字体: 大 中 小 】 时间:2026年10月24日 来源:Proceedings of the ACM on Management of Data

编辑推荐:

   摘要AI 摘要要查看此 AI 生成的摘要,您必须拥有高级访问权限。了解更多登录摘要摘要分位数估计在流式计算模型中起着关键作用。2016 年,Karnin、Lang 和 Liberty 提出了 KLL 草图,该算法被广泛认为是随机化流式分位数估计的最优算法。最近,逐键分位数估计

  

摘要

摘要

分位数估计在流式计算模型中起着关键作用。2016 年,Karnin、Lang 和 Liberty 提出了 KLL 草图,该算法被广泛认为是随机化流式分位数估计的最优算法。最近,逐键分位数估计引起了研究人员的广泛关注。在此类场景中,数据流中的每个条目都表示一个键值对 (k, v),目标是为所有重击者估计分位数——即数据流中比例超过某个阈值 φ 的键。逐键分位数估计在网络测量、数据管理和异常检测中有广泛应用,已有若干解决方案被提出以应对此问题。然而,虽然这些方法在经验上证明了有效性,但它们要么缺乏严格的误差保证,要么导致次优的空间复杂度,理论与实践之间仍存在差距。本文提出了 KLL-Polymer,这是首个实现近最优空间复杂度的逐键分位数草图。KLL-Polymer 继承了 KLL 草图的层次采样思想,但在采样过程中按键聚合条目,从而使单个草图能够高效处理多个键,而非为每个键维护独立的 KLL 草图。因此,KLL-Polymer 实现了 O(1/(φε) log2log 1/ε) 的空间复杂度,同时保证误差超过 ε 的概率至多为 δ,这非常接近理论下界 O(1/(φδ) loglog 1/δ)。我们进一步引入了 KLL-Polymer 的确定性压缩变体,通过在顶层更有效地过滤低频键来优化其性能。实验结果表明,在仅增加极少开销的情况下,KLL-Polymer 与现有方法相比显著降低了估计误差。此外,我们将 KLL-Polymer 集成到 RocksDB 数据库中,成功加速了分布监控并降低了逐键分位数查询的尾部延迟。

AI 摘要

AI 生成摘要(实验性)

本摘要由自动化工具生成,并非由文章作者撰写或审核。其目的是支持文献发现,帮助读者评估相关性,并协助来自相邻研究领域的读者理解该工作。它旨在作为作者提供摘要的补充,后者仍为论文的正式摘要。全文仍为权威版本记录。 点击此处了解更多。

点击 此处 对本摘要的准确性、清晰度和实用性进行评论。这将有助于改进和未来的重新生成版本。

要查看此 AI 生成的通俗摘要,您必须拥有高级访问权限。

相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号