Discrete Mathematics and Optimization Seminar
Friday, Sept. 24th, 2010
MC 320, 3 PM
Cache-Oblivious Range Reporting
Peyman Afshani
Dalhousi Universiry
Abstract: In range reporting, the goal is to preprocess an input set of N points so that the points inside a given query region can be outputted efficiently. This is a fundamental problem in computational geometry and databases and has been studied extensively both in internal memory models as well as the external memory model. Unfortunately, little is known about this problem in models containing a memory hierarchy.

In this talk, first, I will introduce the cache-oblivious model [Frigo et al.'99] which is a simple model that elegantly models a memory hierarchy. After a brief review of some of the known results in this model, I will focus on cache-oblivious dominance reporting in three dimensions. I will discuss both upper and lower bound results for the problem.

The lower bound result is the first known super-constant separation result between the cache-oblivious model and the external memory model. For the upper bound, we will show how to build a data structure that consumes O( N \sqrt{N} loglog N ) space and answers queries optimally. This is the first known data structure that breaks the O( N log N ) space barrier.

Most of the results are from a joint work with Norbert Zeh ("Improved Space Bounds for Cache-Oblivious Range Reporting" to be presented at SODA'11).