THESIS
2004
xii, 95 leaves : ill. ; 30 cm
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 q
l, q
n, an ANN query would output the facility p ∈ P that minimizes the sum of distances lpq
il 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...[
Read more ]
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 q
l, ... q
n, an ANN query would output the facility p ∈ P that minimizes the sum of distances lpq
il 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.
Post a Comment