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.