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 epsilon, can be used to count the number of points inside a query range within additive error epsilon 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.