A general approach for cache-oblivious range reporting and approximate range counting

We present cache-oblivious solutions to two important variants of range searching: range reporting and approximate range counting. Our main contribution is a general approach for constructing cache-oblivious data structures that provide relative (1+ε)-approximations for a general class of range counting queries. This class includes three-sided range counting, 3-d dominance counting, and 3-d halfspace range counting. The constructed data structures use linear space and answer queries in the optimal query bound of O(log B (N/K)) block transfers in the worst case, where K is the number of points in the query range. As a corollary, we also obtain the first approximate 3-d halfspace range counting and 3-d dominance counting data structures with a worst-case query time of O(log (N/K)) in internal memory. An easy but important consequence of our main result is the existence of O(N logN)-space cache-oblivious data structures with an optimal query bound of O(log B N + K/B) block transfers for the reporting versions of the above problems. Using standard reductions, these data structures allow us to obtain the first cache-oblivious data structures that use almost linear space and achieve the optimal query bound for circular range reporting and K-nearest neighbour searching in the plane, as well as for orthogonal range reporting in three dimensions.