Probabilistic Counting in Generalized Turnstile Models

Traditionally in the turnstile model of data streams, there is a state vector $x=(x_1,x_2,\dots ,x_n)$ which is updated through a stream of pairs $(i,k)$ where $i\in [n]$ and $k\in \mathbb{Z}$. Upon receiving $(i,k)$, $x_i\leftarrow x_i+k$. A distinct count algorithm in the turnstile model takes one pass of the stream and then estimates $\text{norm}{x}_0=\mathrm{\mid }\{i\in [n]\mid x_i\mathrm{\ne }0\}\mathrm{\mid }$ (aka $L_0$, the Hamming norm). In this paper, we define a finite-field version of the turnstile model. Let $F$ be any finite field. Then in the $F$-turnstile model, for each $i\in [n]$, $x_i\in F$; for each update $(i,k)$, $k\in F$. The update $x_i\leftarrow x_i+k$ is then computed in the field $F$. A distinct count algorithm in the $F$-turnstile model takes one pass of the stream and estimates $\text{norm}{x}_{0;F}=\mathrm{\mid }\{i\in [n]\mid x_i\mathrm{\ne }{0}_F\}\mathrm{\mid }$. We present a simple distinct count algorithm, called $F$-\pcsa{}, in the $F$-turnstile model for any finite field $F$. The new $F$-\pcsa{} algorithm takes $m\log (n)\log (\mathrm{\mid }F\mathrm{\mid })$ bits of memory and estimates $\text{norm}{x}_{0;F}$ with $O(\frac{1}{\sqrt{m}})$ relative error where the hidden constant depends on the order of the field. $F$-\pcsa{} is straightforward to implement and has several applications in the real world with different choices of $F$. Most notably, it makes distinct count with deletions as simple as distinct count without deletions.