MPhil Thesis Defence


"k-Nearest-Neighbor Queries with Non-Spatial Predicates on Range
Attributes"

By

Mr. Wing Sing Wong

Abstract

Spatial databases have interesting real-life applications with high
demands in the area of geographic information system (GIS), transport
monitoring, network monitoring and VLSI (chip design). Most of the
existing works on spatial databases do not consider range attributes of
the spatial entities. However, in real-life spatial applications, spatial
entities are queried based on not only spatial constraints but also
conditions imposed on non-spatial attributes that may contain ranges of
values instead of single values. One natural and useful query is to find
the 10 nearest restaurants, with expenditure from US$40 to US$60. This
query is like a traditional 10-nearest-neighbor query, but there is an
additional constraint that the expenditure is from US$40 to US$60, which
is the non-spatial aspect of the spatial entities (restaurants). It is
noticed that the non-spatial condition is a range, which makes the
question more interesting. Current approaches would find the
nearest-neighbor result first (filter step) and then examine their
non-spatial attribute to verify that the result matches the non-spatial
constraint (refinement step). The results returned by this traditional
approach are sorted only in ascending order of their distances. However, a
better approach would be to compute a composite score based on distance
and the degree of range overlap according to user preference and to sort
the results in ascending order of the composite scores. In this thesis, a
solution to support nearest-neighbor queries with non-spatial range
predicates is described. Simulation result shows that the proposed
solution reduces the I/O and CPU cost compared to a nave approach.


Date:			Thursday, 27 January 2005

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

Venue:			Room 2504
			Lifts 25-26

Committee Members: 	Prof. Dik-Lun Lee (Supervisor)
		   	Dr. Dimitris Papadias (Chairperson)
			Dr. Qiong Luo


**** ALL are Welcome ****