MPhil Thesis Defence


"AGGREGATE NEAREST NEIGHBOR QUERIES"

By

Mr. Michael Chun-Kit Hui


Abstract

Given two sets of points P (e.g., facilities) and Q (queries) in a
multidimensional vector space, an aggregate nearest neighbor (ANN) query
retrieves the point(s) of P with the smallest aggregate distance(s) to
points in Q. Assuming, for example, n users at locations q1, .., qn, an
ANN query would output the facility p in P that minimizes the sum of
distances |pqi| that the users have to travel in order to meet there.
Similarly, another ANN query may report the point that minimizes the
maximum distance that any user has to travel, or the minimum distance from
some user to his/her closest facility. If Q fits in memory and P is
indexed by an R-tree, we first propose algorithms for efficient retrieval
of aggregate nearest neighbors and analyze their performance. As a second
step, we extend our techniques for disk-resident queries and approximate
ANN retrieval. The efficiency of the proposed algorithms and the accuracy
of the cost models are evaluated through extensive experiments with real
and synthetic datasets.


Date:				Monday, 30 August 2004

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

Venue:				Room 2406
				Lifts 17-18

Committee Members:		Prof. Dimitris Papadias (Supervisor)
				Prof. Siu-Wing Cheng (Chairperson)
				Prof. Mordecai Golin


**** ALL are Welcome ****