Cache-oblivious range reporting with optimal queries requires superlinear space

Abstract

We consider a number of range reporting problems in two and three dimensions and prove lower bounds on the amount of space required by any cache-oblivious data structure for these problems that achieves an optimal query bound of O(logBN + K/B) block transfers in the worst case, where K is the size of the query output.