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


PhD Thesis Defence


"Continuous Monitoring of Multi-dimensional Queries"

By

Mr. Kyriakos Mouratidis


Abstract

This thesis studies the monitoring of continuous multi-dimensional
queries. A continuous query runs over long periods of time and requests
reporting of its result as the data dynamically change. Initially, we
focus on nearest neighbor (NN) monitoring, a problem that typically arises
in location-based services. In this context, the query points and the data
objects move arbitrarily, and the task of a central server is to report
the k closest objects (i.e., the k NNs) to each query point. First, we
propose a method that aims at minimizing the communication cost spent in
message exchanges between the data objects and the server. Our second
contribution is an algorithm that minimizes the processing cost at the
server, assuming that the distance between objects and queries is defined
according to the Euclidean metric. Next, we present efficient NN
monitoring techniques targeted to applications where the objects and the
queries move in a road network, and their distance is defined as the
length of the shortest path connecting them in the network. Finally, we
consider a class of non-spatial queries and show that geometric reasoning
can be used for their efficient monitoring. In particular, we study
continuous top-k processing over sliding windows. In this setting, a
stream of multi-dimensional tuples arrives at a central server. Among
these tuples, only the most recent ones are considered valid. Given a
function that assigns a score (i.e., a real number) to each tuple, the
task of the server is to continuously report the k valid tuples with the
highest scores.


Date:			Tuesday, 28 February 2006

Time:			5:00p.m.-7:00p.m.

Venue:			Room 3301
			Lifts 17-18

Chairman:		Prof. Theodore CLARK  (ISMT)

Committee Members:	Prof. Dimitris Papadias (Supervisor)
			Prof. Lei Chen
			Prof. Frederick Lochovsky
			Prof. Andrew LIM (IELM)
			Prof. Kian-Lee Tan (Comp. Sci.,
					    National Univ. of Singapore)


**** ALL are Welcome ****