2009.09.26 | Else Magård

TITLE: Optimal Cache-Oblivious Range Reporting Requires Superlinear Space

SPEAKER: Norbert Zeh, Dalhousie University

ABSTRACT:

In recent years, a numberof cache-oblvious range search structures for 3-sided range reporting in the plane, 3-d dominance reporting, and 3-d halfspace range reporting with the optimal query bound ofO(log_BN + K/B) I/O's have been developed. These structures use O(N log N) space, while the best cache-aware structures for these problems use (almost) linear space. This raises the question whether linear-space cache-oblivious structures with the optimal query bound exist for these problems. We give a negative answer to this question by proving that Omega(N (log log N)^eps) space is necessary to achieve the optimal query bound cache-obliviously. This is the first result that provides a gap between the resource consumption of a cache-oblivious algorithm or data structure and its cache-aware counterpart that grows with the input size.

Joint work with:
Peyman Afshani and Chris Hamilton

Host: Lars Arge