论文标题
对保守更新的正式分析
A Formal Analysis of the Count-Min Sketch with Conservative Updates
论文作者
论文摘要
带有保守更新（CMS-CU）的计数示意图是一种流行的算法，可在数据流中大致计算项目的外观。尽管CMS-CU广泛采用了广泛的采用，但由于其固有的困难，对其性能的理论分析仍然需要。在本文中，我们提出了一种研究CMS-CU的新方法，并在I.I.D.下的估计误差的期望值和CCDF上得出了新的上限。请求过程。我们的公式可以成功地用于得出改进的重击检测方法的精确度和改进CMS-CU的配置规则的估计。在合成和真实痕迹上评估边界。
Count-Min Sketch with Conservative Updates (CMS-CU) is a popular algorithm to approximately count items' appearances in a data stream. Despite CMS-CU's widespread adoption, the theoretical analysis of its performance is still wanting because of its inherent difficulty. In this paper, we propose a novel approach to study CMS-CU and derive new upper bounds on the expected value and the CCDF of the estimation error under an i.i.d. request process. Our formulas can be successfully employed to derive improved estimates for the precision of heavy-hitter detection methods and improved configuration rules for CMS-CU. The bounds are evaluated both on synthetic and real traces.
