Norbert Zeh, from Dalhousie University
We study range reporting and range counting problems with various query shapes, most notably 3-sided queries in the plane, 3-d dominance queries, and 3-d halfspace range queries. For the reporting version, we show that any cache-oblivious data structure that achieves the optimal query bound (or even a significantly weaker bound) has to use super-linear space. This is the first separation result between I/O model and cache-oblivious model that establishes a gap that grows with the input size.
As for upper bounds, we provide a general framework based on shallow cuttings that results in linear-space cache-oblivious structures with optimal approximate range counting queries for a wide range of query ranges, including the ones above. Using this, we obtain O(n log n) space cache-oblivious reporting structures with the optimal query bound for the same types of query ranges. Our range counting result also provides the first internal-memory structure for approximate halfspace range counting with the optimal query bound in the worst case.