Probabilistic Counting in Generalized Turnstile Models

Dingyu Wang

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…