Turnstile streaming algorithms might as well be linear sketches
Yi Li, Huy Lê Nguyễn, David P. Woodruff · 2014
In the turnstile model of data streams, an underlying vector x ∈ {--m,--m+1,..., m--1,m}n is presented as a long sequence of positive and negative integer updates to its coordinates. A randomized algorithm seeks to approximate a function f(x) with constant probability while only making a single pass over this sequence of updates and using a small amount of space. All known algorithms in this model are linear sketches: they sample a matrix A from a distribution on integer matrices in the preprocessing phase, and maintain the linear sketch A·x while processing the stream. At the end of the stream, they output an arbitrary function of A · x. One cannot help but ask: are linear sketches universal?