
Discrete Mathematics and Optimization Seminar

Friday, Sept. 24th, 2010 MC 320, 3 PM
CacheOblivious 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 cacheoblivious 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 cacheoblivious
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 superconstant separation result between the
cacheoblivious 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
CacheOblivious Range Reporting" to be presented at SODA'11).



