Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond
Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond
复制标题
DOI：
10.1145/3584372.3588680
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
Dingyu Wang;Seth Pettie
中科院分区：
文献类型：
--
作者：
Dingyu Wang;Seth Pettie
基数估计（又名不同元素）是数据库、网络和安全领域许多应用程序草图中的一个经典问题。尽管草图算法相当简单，但分析基数估计器却非常困难，即使在今天，对 HyperLogLog 和 ¶CSA 等最先进草图的分析也不是很容易实现。在本文中，我们介绍了一类新的估计器，称为 τ-广义剩余面积估计器，以及一种非常简单的分析估计器的方法。 Durand 和 Flajolet、Flajolet 等人以及 Lang 的估计量可以视为 τ 整数值的 τ-GRA 估计量。通过使用 τ 的分数值，我们得出了 HyperLogLog 和 ¶CSA 的改进估计量，其方差非常接近 Cramé r-Rao 下界。我们还为 Pettie、Wang 和 Yin 引入的 Curtain sketch 类推导了基于 τ-GRA 的估计器，它可以被视为 HyperLogLog 和 ¶CSA 的混合体，具有比两者更有吸引力的简单性与准确性权衡。
Cardinality Estimation (aka Distinct Elements) is a classic problem in sketching with many applications in databases, networking, and security. Although sketching algorithms are fairly simple, analyzing the cardinality estimators is notoriously difficult, and even today the analyses of state-of-the-art sketches like HyperLogLog and ¶CSA are not very accessible. In this paper we introduce a new class of estimators called τ-Generalized-Remaining-Area estimators, as well as a dramatically simpler approach to analyzing estimators. The estimators of Durand and Flajolet, Flajolet et al., and Lang can be seen as τ-GRA estimators for integer values of τ. By using fractional values of τ we derive improved estimators for HyperLogLog and ¶CSA whose variance comes very close to the Cramé r-Rao lower bounds. We also derive τ-GRA-based estimators for the class of Curtain sketches introduced by Pettie, Wang, and Yin, which can be seen as a hybrid of HyperLogLog and ¶CSA with a more attractive simplicity-accuracy tradeoff than both.