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 halfspace 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 log N) ε ) space. This lower bound holds also 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 exponent ε 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(Nlog ∗ 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.