Efficient processing of proximity based spatial queries

Abstract

Spatial databases play a vital role in many applications such as Geographic Information Systems (GIS), Computer Aided Design (CAD), Very-Large-Scale Integration (VLSI) designs, Multimedia Information System (MMIS), and medicine and biological research. Due to their importance, a large body of work has focused on efficiently computing various spatial queries. A proximity based spatial query computes the results based on the proximity (closeness) between the objects. Range queries, reverse k nearest neighbors (RkNN) queries and k-closest pairs queries are some of the most important and well studied proximity based spatial queries. In this thesis, we provide efficient solutions for these queries under various settings. Below is a brief description of our contributions.

We present several algorithms to answer RkNN queries under different settings. More specifically, we present an approach, called Lazy Updates, to continuously monitor RkNN queries in Euclidean space as well as in spatial networks. Lazy Updates outperforms all of the existing techniques in terms of both the computation cost and the communication cost. We devise another technique, based on a novel concept of influence zone, to efficiently compute both snapshot and continuous RkNN queries. The influence zone based approach outperforms the existing techniques for both the snapshot and the continuous RkNN queries. We also provide efficient solution for probabilistic RNN queries for the case when the underlying data is uncertain.

We are the first to study the efficient monitoring of moving range queries over a set of static data objects in Euclidean space and in spatial networks. We conduct a rigorous theoretical analysis to show the effectiveness of our approach. The theoretical results are verified by an extensive experimental study. The experimental results also demonstrate that the proposed approach is close to optimal.

We are the first to present a unified framework to answer a broad class of top-k pairs queries including the k-closest pairs queries, k-furthest pairs queries and their bichromatic variants. We conduct a rigorous complexity analysis and show that the expected cost of our proposed algorithms is optimal when the scoring function uses at most two attributes.