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 ℝdlying in a query hyper-rectangle. Cache-oblivious 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(logB2N) memory transfers. We also develop a static structure for the two-dimensional case that answers queries in O(logBN + T/B) memory transfers using O(N log22N) space. The analysis of the latter structure requires that B = 22cfor some non-negative integer constant c.