|
|
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).
|
|
|
|