Orthogonal Range Reporting in 3 and Higher Dimensions

Speaker:	Professor Lars ARGE
		Aarhus University
		Denmark

Title:		"Orthogonal Range Reporting in 3 and Higher
		 Dimensions"

Date:		Tuesday, 9 November 2010

Time:		4:00pm - 5:00pm

Venue:		Room 3311 (via lifts 17/18), HKUST

Abstract:

Orthogonal range reporting is the problem of storing a set of n points in
d-dimensional space, such that the k points in an axis-orthogonal query
box can be reported efficiently. While the 2-d version of the problem was
completely characterized in the pointer machine model more than two
decades ago, until recently this was not the case in higher dimensions.

In this talk, we describe techniques that can be used to obtain a space
optimal pointer machine data structure for 3-d orthogonal range reporting
that answers queries in O(log n + k) time. Thus we settle the complexity
of the problem in 3-d. The techniques can also be used to obtain improved
structures in higher dimensions, namely structures with a log n/ log log n
factor increase in space and query time per dimension. Thus for d >= 3 we
obtain a structure that both uses optimal O(n(log n/ log log n)^{d-1})
space and answers queries in the best known query bound O(log n(log n/ log
log n)^{d-3} + k). At the end of the talk we will mention how the new
techniques can also be used to obtain improved or even optimal external
memory structures, and how we have also proved lower bounds show that the
optimal query bound increases from \Theta(log n + k) to \Omega((log n/ log
log n)^2 + k) somewhere between three and six dimensions.

*******************
Biography:

Lars Arge is a Professor of Computer Science at Aarhus University, as well
as Director of Center for Massive Data Algorithmics (MADALGO) funded by
the Danish National Research Foundation. He obtained a Ph.D. from Aarhus
University in 1996 and from 1996 to 2004 he was at Duke University in the
US. His main research interests lie in the area of memory-hierarchy
efficient algorithms, especially I/O-efficient algorithms for problems
involving massive datasets. He have worked on massive dataset problems in
many fundamental areas, but much of his work has been on I/O-efficient
algorithms and data structures for problems with practical applications in
geographic information systems and spatial databases. He has investigated
the practical merits of theoretically developed I/O-efficient algorithms
in projects such as TPIE, TerraFlow and TerraStream, and is the co-founder
of the company Scalable Algorithmics (SCALGO) that specializes in software
for massive terrain data processing.