COLLOQUIUM
             Computer Science Department, Boston University

Speaker: Donghui Zhang
         Northeastern University

Date:  Wednesday, April 19, 2006
Time:  3:00 pm
Place: Room MCS 135, 111 Cummington Street 
       (for directions, see www.cs.bu.edu/colloquium)

Title: The Optimal-Location Query

Abstract:

This talk introduces the optimal-location query in spatial
databases. Given a set of sites (e.g. McDonald's), a set of
objects (e.g. apartment buildings), and a spatial region Q,
the optimal-location query returns a location in Q which,
if a new McDonald's is built there, benefits the largest
number of customers.  This new query has practical
applications, but is very challenging to solve. Existing work on
computing RNNs assumes a single query location, and thus cannot be
used to compute optimal locations. The reason is that there are
infinite candidate locations in $Q$. If we check a finite set of
candidate locations, the result can be inaccurate, i.e. the
revealed location may not have maximum influence. This paper
proposes three methods that accurately compute optimal
locations. The first method uses a standard R*-tree. To compute an
optimal location, the method retrieves certain objects from the
R*-tree and sends them as a stream to a plane-sweep algorithm,
which uses a new data structure called the aSB-tree to ensure
query efficiency. The second method is based on a new index
structure called the OL-tree, which novelly extends the
k-d-B-tree to store segmented rectangular records. The OL-tree is
only of theoretical usage for it is not space efficient. The most
practical approach is based on a new index structure called the
Virtual OL-tree. These methods are theoretically and
experimentally evaluated.

Bio:
Professor Donghui Zhang received his Ph.D. in 2002 from the University of
California -- Riverside. Since then, he has been working as an Assistant
Professor in the College of Computer & Information Science, Northeastern
University. Professor Zhang's primary research area is databases. In
particular, query optimization in spatio-temporal database systems. Many
real application data have spatial and/or temporal dimensions. For
instance, the locations of apartment buildings, cars, mobile-phone users
which may or may not change over time. The concern is how to index such
objects and how to efficiently compute the result of interesting queries.
Professor Zhang received the NSF CAREER Award: Fast Query Support for
Emerging Spatial Database Applications. He has written two book chapters
and published over twenty peer-refereed research papers. He has served on
the panels of two NSF programs, on the Program Committees of various
international conferences including ICDE'07, SSTD'07, VLDB'05, ICDE'04 and
EDBT'04, and as referee for over 10 journals such as TODS and VLDBJ.

http://www.ccs.neu.edu/home/donghui


Host: George Kollios