PhD Thesis Proposal Defence


"Continuous Monitoring of Multi-Dimensional Queries"

By Mr. Kyriakos Mouratidis


Abstract:

Traditional data base systems are designed to answer transient, snapshot
queries on persistent data. Recently, however, a new data processing model
has arisen. In this model, multiple long-running queries require
continuous evaluation as the data change dynamically. In this proposal we
study continuous k nearest neighbor (k-NN) monitoring over arbitrarily
moving objects. We present two methods that aim at minimizing the
processing and the communication cost, respectively. Even though our focus
here is on NN queries, in the future we plan to extend the proposed
techniques to other multi-dimensional queries. Towards this direction, we
make some preliminary observations and state the issues that need further
investigation.

Our first NN monitoring algorithm, called conceptual partitioning
monitoring (CPM), aims at minimizing the computational overhead for
centrally processing multiple queries. Given a set of moving objects P and
a k-NN query at point q, the system has to continuously report the k
objects in P that lie closest to q. Assuming that each data object issues
an update whenever it changes position, CPM achieves low running time by
handling location updates only from objects that fall in the vicinity of
some query (and ignoring the rest). It can monitor multiple, static or
moving queries, and it does not make any assumptions about the object
moving patterns. We analyze the performance of CPM and show that it
outperforms the current state-of-the-art algorithms for all problem
settings. Additionally, we extend our framework to aggregate NN (ANN)
queries, which monitor the data objects that minimize the aggregate
distance with respect to a set of query points (e.g., the objects with the
smallest sum of distances to all query points).

As opposed to CPM, the objective of our second method is to minimize the
communication cost between the central server and the objects. All the
existing NN monitoring techniques assume that the objects inform the
server about their new coordinates whenever they move. This approach,
however, requires the transmission of a large number of rapid data streams
corresponding to location updates. Intuitively, current information is
necessary only for objects that may influence some query result. Motivated
by this observation, we present a threshold-based algorithm (TB) that
exploits the computational capabilities of the objects in order to reduce
the communication overhead. TB can be used with multiple moving queries,
for any distance definition, and does not require additional knowledge
(e.g., velocity vectors) besides object locations.


Date:     		Wednesday, 25 May 2005

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

Venue:                  Room 1504
			lifts 25-26

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


**** ALL are Welcome ****