Nearest neighbor queries in spatial and spatio-temporal databases

Abstract

Nearest neighbor (NN) search constitutes one of the most important forms of spatial / spatio-temporal information processing. Despite the large amount of related work during the past decade, NN queries are not yet fully exploited. In this thesis, we provide effective solutions for a variety of problems related to NN search: (i) motivated by the fact that the current cost models for NN search are too expensive for query optimization, we propose an efficient method that captures the performance of NN queries in real-time; (ii) we study a variance of NN search, called the all-nearest-neighbor query, which retrieves for each object in a dataset, its NN in another dataset; (iii) we investigate NN queries in dynamic environments and develop an approach that enables mobile clients to determine the validity of previous NN queries based on their current locations; (iv) we discuss NN queries in spatial network databases where nearest neighbors are defined with respect to network distance (i.e., the shortest path distance between objects in the underlying network); (v) finally, we present algorithms for NN queries in the presence of obstacles.

Date of Award	2003
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology