Query Processing over Large Spatial Networks

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Query Processing over Large 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 thesis 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 then 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.

We also consider distributed processing of large spatial networks. 
Specifically, we review the Pregel graph computing framework proposed by 
Google, and show how to process spatial queries in Pregel. We then 
indicate the weaknesses of Pregel in processing large-diameter spatial 
networks, and discuss how to improve Pregel s framework for more efficient 
query processing over spatial networks.

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


Date:			Friday, 2 May 2014

Time:			11:00am – 1:00pm

Venue:			Room 3501
 			Lifts 25/26

Chairman:		Prof. Tai-Yuan Chen (ACCT)

Committee Members:	Prof. Wilfred Ng (Supervisor)
 			Prof. Frederick Lochovsky
 			Prof. Dimitris Papadias
 			Prof. Xiangtong Qi (IELM)
                        Prof. Qing Li (Comp. Sci., CityU)


**** ALL are Welcome ****