论文标题
最佳范围用于近似计数
Optimal bounds for approximate counting
论文作者
论文摘要
存储计数器增加$ n $ times会天真地消耗$ o（\ log n）$存储器。 1978年，莫里斯（Morris）描述了第一个流媒体算法：“莫里斯计数器”。他的算法的空格绑定是一个随机变量，已证明是$ O（\ log \ log \ log n + \ log（1/\ varepsilon） + \ log（1/δ）$ bits $ bits $ bits期望提供$（1 + \ varepsilon）$ - 近似值，近似值，近似值$ 1-Δ$。我们提供了一种新的简单算法，并提供了一个简单的分析，表明随机空间$ o（\ log \ log n + \ log（1/\ varepsilon） + \ log \ log \ log \ log \ log \ log \ log \ log（1/δ）$ lits $ lits $ lits $ lits $ bits $ bits to n ofers toss toss的差额是否足以提高对反向故障的依赖性。然后，我们提供了一项新的分析，表明原始的莫里斯（Morris）本身在未成年人但必要的调整之后，实际上也享有相同的改进上限。最后，我们证明了该任务的新下限，显示了上限的最佳性。因此，我们完全解决了近似计数的渐近空间复杂性。此外，我们所有的常数都是显式的，我们的下限和最紧密的上限也不同于最多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". His algorithm's space bound is a random variable, and it has been shown to be $O(\log\log N + \log(1/\varepsilon) + \log(1/δ))$ bits in expectation to provide a $(1+\varepsilon)$-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/\varepsilon) + \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)$.
