Range counting over multidimensional data streams
Subhash Suri, Csaba D. Tóth, Yunhong Zhou · 2004
We consider the problem of approximate range counting over streams of d-dimensional points. In the data stream model, the algorithm makes a single scan of the data, which is presented in an arbitrary order, and computes a compact summary (called a sketch). The sketch, whose size depends on the approximation parameter ε, can be used to count the number of points inside a query range within additive error εn, where n is the size of the stream. We present several results, deterministic and randomized, for both rectangle and halfplane ranges.