Multi-dimensional Approximate Counting
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915006025564160 |
|---|---|
| author | Wang, Dingyu |
| author_facet | Wang, Dingyu |
| contents | The celebrated Morris counter uses $\log_2\log_2 n + O(\log_2 σ^{-1})$ bits to count up to $n$ with a relative error $σ$, where if $\hatλ$ is the estimate of the current count $λ$, then $\mathbb{E}|\hatλ-λ|^2 <σ^2λ^2$. A natural generalization is \emph{multi-dimensional} approximate counting. Let $d\geq 1$ be the dimension. The count vector $x\in \mathbb{N}^d$ is incremented entry-wisely over a stream of coordinates $(w_1,\ldots,w_n)\in [d]^n$, where upon receiving $w_k\in[d]$, $x_{w_k}\gets 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<σ^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 $σ$, i.e., $\mathbb{E} |\hat{x}-x|^2 <σ^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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_03071 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Multi-dimensional Approximate Counting Wang, Dingyu Data Structures and Algorithms The celebrated Morris counter uses $\log_2\log_2 n + O(\log_2 σ^{-1})$ bits to count up to $n$ with a relative error $σ$, where if $\hatλ$ is the estimate of the current count $λ$, then $\mathbb{E}|\hatλ-λ|^2 <σ^2λ^2$. A natural generalization is \emph{multi-dimensional} approximate counting. Let $d\geq 1$ be the dimension. The count vector $x\in \mathbb{N}^d$ is incremented entry-wisely over a stream of coordinates $(w_1,\ldots,w_n)\in [d]^n$, where upon receiving $w_k\in[d]$, $x_{w_k}\gets 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<σ^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 $σ$, i.e., $\mathbb{E} |\hat{x}-x|^2 <σ^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. |
| title | Multi-dimensional Approximate Counting |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.03071 |