Multi-dimensional Approximate Counting

Abstract

The celebrated Morris counter uses ${\log }_2{\log }_{2}n+O({\log }_2\ddot{I}{ƒ}^{-1})$ bits to count up to $n$ with a relative error $\ddot{I}ƒ$, where if $\hat{\hat{I}}»$ is the estimate of the current count $\hat{I}»$, then $\mathbb{E}|\hat{\hat{I}}»-\hat{I}»{|}^2<\ddot{I}{ƒ}^2\hat{I}{»}^2$. A natural generalization is \emph{multi-dimensional} approximate counting. Let $d\ge 1$ be the dimension. The count vector $x\in {\mathbb{N}}^d$ is incremented entry-wisely over a stream of coordinates $(w_1,\dots ,w_n)\in [d{]}^n$, where upon receiving $w_k\in [d]$, $x_{w_k}\leftarrow x_{w_k}+1$. A \emph{$d$-dimensional approximate counter} is required to count $d$ coordinates simultaneously and return an estimate $\hat{x}$ of the count vector $x$. Aden-Ali, Han, Nelson, and Yu \cite{aden2022amortized} showed that the trivial solution of using $d$ Morris counters that track $d$ coordinates separately is already optimal in space, \emph{if each entry only allows error relative to itself}, i.e., $\mathbb{E}|{\hat{x}}_j-x_j{|}^2<\ddot{I}{ƒ}^2|x_j{|}^2$ for each $j\in [d]$. However, for another natural error metric -- the \emph{Euclidean mean squared error} $\mathbb{E}|\hat{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 $\ddot{I}ƒ$, i.e., $\mathbb{E}|\hat{x}-x{|}^2<\ddot{I}{ƒ}^2|x{|}^2$ where $|x|=\sqrt{{\sum }_{j=1}^d{x}_j^2}$, 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.