Cache-oblivious data structures for orthogonal range searching

We develop cache-oblivious data structures for orthogonal range searching, the problem of finding all T points in a set of N points in Ê d lying in a query hyper-rectangle. Cacheoblivious data structures are designed to be efficient in arbitrary memory hierarchies. We describe a dynamic linear-size data structure that answers d-dimensional queries in O((N/B) 1−1/d + T/B)memory transfers, where B is the block size of any two levels of a multilevel memory hierarchy. A point can be inserted into or deleted from this data structure in O(log 2 B N) memory transfers. We also develop a static structure for the two-dimensional case that answers queries in O(logB N + T/B) memory transfers using O(N log 2 2 N) space. The analysis of the latter structure requires that B =2 2c for some nonnegative integer constant c