Aggregate nearest neighbor queries

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 ql, ... qn, an ANN query would output the facility p ∈ P that minimizes the sum of distances lpqil for 1≤i≤n that the users have to travel in order to meet there. Similarly, another ANN query may report the point p ∈ P 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 of Award	2004
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology