2024/11/05 by Wang, Dingyu
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2411.03071
The celebrated Morris counter uses log2log2 n + O(log2 σ-1) bits to count up to n with a relative error σ, where if λ is the estimate of the current count λ, then 𝔼|λ-λ|2 <σ2λ2. A natural generalization is multi-dimensional approximate counting. Let d≥ 1 be the dimension. The count vector x∈ ℕd is incremented entry-wisely over a stream of coordinates (w1,…,wn)∈ [d]n, where upon receiving wk∈[d], xwk\gets xwk+1. A d-dimensional approximate counter is required to count d coordinates simultaneously and return an estimate x of the count vector x. Aden-Ali, Han, Nelson, and Yu \citeaden2022amortized showed that the trivial solution of using d Morris counters that track d coordinates separately is already optimal in space, if each entry only allows error relative to itself, i.e., 𝔼|xj-xj|2<σ2|xj|2 for each j∈ [d]. However, for another natural error metric -- the Euclidean mean squared error 𝔼 |x-x|2 -- we show that using d separate Morris counters is sub-optimal. In this work, we present a simple and optimal d-dimensional counter with Euclidean relative error σ, i.e., 𝔼 |x-x|2 <σ2|x|2 where |x|=√∑j=1d xj2, with a matching lower bound. The upper and lower bounds are proved with ideas that are strikingly simple. The upper bound is constructed with a certain variable-length integer encoding and the lower bound is derived from a straightforward volumetric estimation of sphere covering.