Query Processing over Spatial Networks

PhD Thesis Proposal Defence


Title: "Query Processing over Spatial Networks"

by

Mr. Da YAN


Abstract:

Spatial networks are ubiquitous in various real world applications. For
example, GPS navigation systems maintain and query road networks to guide
car-drivers to their destinations; while rescue centers maintain the
terrain information for the purpose of disaster response.

Compared with Euclidean space, spatial networks are usually a more
realistic setting for many real world database applications, and thus, it
is very important to support efficient query processing over spatial
networks. Many spatial queries that were first studied in the Euclidean
space have been studied over spatial networks, including nearest neighbor
(NN) queries, reverse nearest neighbor (RNN) queries, aggregate nearest
neighbor (ANN) queries, skyline queries, facility location problem, etc.

The scope of this proposal goes beyond those traditional spatial queries,
and we propose to study novel spatial queries that are of special interest
to applications related to spatial networks. This first kind of query is
Optimal Meeting Point (OMP) query that finds the location p that minimizes
a cost function defined over the distances from p to all the query points.
Applications of OMP queries include determining the location of a
conference venue, and deciding the pick-up location of a tourist bus. The
second kind of query is Distance-Preserving Subgraph (DPS) query which
finds a subgraph of the spatial network that preserves the shortest path
between any two query points. DPS queries are important in route
recommendation systems, logistics planning, and all kinds of
shortest-path-related applications that run on resource-limited mobile
devices.

We also study Triangulated Irregular Network (TIN) that models terrain
data. Specifically, we study monochromatic and bichromatic reverse nearest
neighbor queries over terrain data. We show that evaluating such
traditional spatial queries over terrain data conforming to TIN model is
very challenging, and introducing techniques for efficient query
processing over terrain.

Finally, we discuss about possible future work over spatial networks.


Date:			Monday, 18 November 2013

Time:                   4:30pm - 6:30pm

Venue:                  Room 5510
                         lifts 25/26

Committee Members:	Dr. Wilfred Ng (Supervisor)
 			Prof. Dik-Lun Lee (Chairperson)
 			Dr. Lei Chen
 			Dr. Raymond Wong


**** ALL are Welcome ****