Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm
Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm
复制标题
回到未来：一种更接近最优的基数估计算法
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Kevin J. Lang
中科院分区：
文献类型：
--
作者：
Kevin J. Lang
我们描述了一种新的基数估计算法，该算法极高。它将三个新型估计量之一应用于Flajolet-Martin-85优惠券收集过程的压缩状态。在与压缩超静态草图的经验比较中，新算法同时在时间/空间/准确性权衡的所有三个维度上获胜。我们的原型使用ZSTD压缩库，并产生比HLL熵小的草图，因此压缩HLL的实现不可能匹配其空间效率。该论文的技术贡献包括对三个新估计量的分析和模拟，FM85和HLL熵的准确值，以及通过模拟估算双重渐近极限的非平凡方法。
We describe a new cardinality estimation algorithm that is extremely space-efficient. It applies one of three novel estimators to the compressed state of the Flajolet-Martin-85 coupon collection process. In an apples-to-apples empirical comparison against compressed HyperLogLog sketches, the new algorithm simultaneously wins on all three dimensions of the time/space/accuracy tradeoff. Our prototype uses the zstd compression library, and produces sketches that are smaller than the entropy of HLL, so no possible implementation of compressed HLL can match its space efficiency. The paper's technical contributions include analyses and simulations of the three new estimators, accurate values for the entropies of FM85 and HLL, and a non-trivial method for estimating a double asymptotic limit via simulation.