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


PhD Thesis Defence


"Nearest Neighbor Queries in Spatial and Spatio-temporal Databases"

By

Mr. Jun Zhang


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:			Monday, 15 December 2003

Time:			2:30p.m.-4:30p.m.

Venue:			Room 1402
			Lifts 25-26

Chairman:		Prof. Wenxiong Wang (BIOL)

Committee Members:	Prof. Dimitris Papadias (Supervisor)
			Prof. Dik-Lun Lee
			Prof. Qiong Luo
			Prof. Andrew L.C. Lim (IEEM)
			Prof. Kam-Yiu Lam (Comp. Sci., CityU)



**** ALL are Welcome ****