THESIS
2014
xi, 126 pages : illustrations ; 30 cm
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...[
Read more ]
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
Pregels framework for more efficient query processing over spatial networks.
Finally, we discuss about possible future work over spatial networks.
Post a Comment