Range Counting over Multidimensional Data Streams

We consider the problem of approximate range counting over a stream 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 data structure. The summary, 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 seen so far. We present several results, deterministic and randomized, for both rectangle and halfspace ranges.