We provide improved bounds on the size of cacheoblivious range reporting data structures that achieve the optimal query bound of O(logB N + K/B) block transfers. Our first main result is an O(N √ logN log logN)-space data structure that achieves this query bound for 3-d dominance reporting and 2-d three-sided range reporting. No cache-oblivious o(N log N/ log logN)-space data structure for these problems was known before, even when allowing a query bound of O(logO(1) 2 N + K/B) block transfers.1 Our result also implies improved space bounds for general 2-d and 3-d orthogonal range reporting. Our second main result shows that any cache-oblivious 2-d three-sided range reporting data structure with the optimal query bound has to use Ω(N logε N) space, thereby improving on a recent lower bound for the same problem. Using known transformations, the lower bound extends to 3-d dominance reporting and 3-d halfspace range reporting.
Proceedings of the 22nd Annual Acm-siam Symposium on Discrete Algorithms. Soda 2011, 2011, p. 1745-1758