The Optimal-Location Query

Dr. Donghui Zhang
College of Computer & Information Science,
Northeastern University.

Friday April 28, 2006
11:00 a.m. - 12:00 p.m.
Fuller Labs 320

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 Reverse Nearest Neighbors (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 presentation 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 as 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.

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. His primary research area is databases, and query optimization in spatio-temporal database systems, in particular. Professor Zhang received the NSF CAREER Award for "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 a referee for over 10 journals such as TODS and VLDBJ.

Host: Murali Mani

Refreshments will be served.