Optimal Bounds for Approximate Counting
Optimal Bounds for Approximate Counting
复制标题
近似计数的最佳界限
DOI：
10.1145/3517804.3526225
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Yu, Huacheng
中科院分区：
文献类型：
--
作者：
Nelson, Jelani;Yu, Huacheng
存储递增N次的计数器将消耗O（log N）位内存。1978年，Morris描述了第一个流算法：“Morris计数器”[15]。他的算法的空间边界是一个随机变量，并且它已经被证明是O（log log N + log（1/ε）+ log（1/δ））位，期望提供计数器值的概率为$1-δ的（1+ε）-近似。我们提供了一个新的简单的算法，一个简单的分析表明，随机空间O（log log N + log（1/ε）+ log log（1/δ））位足够的相同的任务，即指数改善的依赖于逆故障概率。然后，我们提供了一个新的分析表明，原来的莫里斯计数器本身，经过一个轻微的，但必要的调整，实际上也享有同样的改进上限。最后，我们证明了一个新的下界，显示我们的上限的最优性。因此，我们完全解决了近似计数的渐近空间复杂性。此外，我们所有的常数都是明确的，我们的下限和最严格的上限相差一个乘法因子至多3+o（1）。
Storing a counter incremented N times would naively consume O(log N) bits of memory. In 1978 Morris described the very first streaming algorithm: the "Morris Counter" [15]. His algorithm's space bound is a random variable, and it has been shown to be O(log log N + log(1/ε) + log(1/δ)) bits in expectation to provide a (1+ε)-approximation with probability $1-δ to the counter's value. We provide a new simple algorithm with a simple analysis showing that randomized space O(log log N + log(1/ε) + log log(1/δ)) bits suffice for the same task, i.e. an exponentially improved dependence on the inverse failure probability. We then provide a new analysis showing that the original Morris Counter itself, after a minor but necessary tweak, actually also enjoys this same improved upper bound. Lastly, we prove a new lower bound for this task showing optimality of our upper bound. We thus completely resolve the asymptotic space complexity of approximate counting. Furthermore all our constants are explicit, and our lower bound and tightest upper bound differ by a multiplicative factor of at most 3+o(1).
应用近似计数计算长数据流的频率矩
影响因子：
0.5
作者：
André Gronemeier;Martin Sauerhoff
通讯作者：
Martin Sauerhoff
DOI：
--
发表时间：
1982-07
期刊：
--
影响因子：
--
作者：
P. Flajolet
通讯作者：
P. Flajolet
大数据小总结
影响因子：
2.5
作者：
Graham Cormode;K. Yi
通讯作者：
K. Yi