Cache-oblivious range reporting with optimal queries requires superlinear space

We consider a number of range reporting problems in two and three dimensions and prove lower bounds on the amount of space used by any cache-oblivious data structure for these problems that achieves the optimal query bound of O(log B N +K/B) block transfers, where K is the size of the query output. The problems we study are three-sided range reporting, 3-d dominance reporting, and 3-d halfs-pace range reporting. We prove that, in order to achieve the above query bound or even a bound of f(log B N, K/B), for any monotonically increasing function f(·, ·), the data structure has to use Ω(N(log logN)ε) space. This lower bound holds even for the expected size of any Las-Vegas-type data structure that achieves an expected query bound of at most f(log B N, K/B) block transfers. The expo-nent ε depends on the function f and on the range of permissible block sizes. Our result has a number of interesting consequences. The first one is a new type of separation between the I/O model and the cache-oblivious model, as deterministic I/O-efficient data structures with the optimal query bound in the worst case and using linear or O(N log ∗ N) space are known for the above problems. The second consequence is the non-existence of linear-space cache-oblivious persistent B-trees with optimal 1-d range reporting queries.