Published Articles >> Table of Contents >> Abstract

20th International Conference on Data Engineering (ICDE'04)   p. 301
Group Nearest Neighbor Queries
Dimitris Papadias, Hong Kong University of Science and Technology
Qiongmao Shen, Hong Kong University of Science and Technology
Yufei Tao, City University of Hong Kong
Kyriakos Mouratidis, Hong Kong University of Science and Technology

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDE.2004.1320006
Send link to a friend

Abstract
Given two sets of points P and Q, a group nearest neighbor (GNN) query retrieves the point(s) of P with the smallest sum of distances to all points in Q. Consider, for instance, three users at locations q1, q2 and q3 that want to find a meeting point (e.g., a restaurant); the corresponding query returns the data point p that minimizes the sum of Euclidean distances |pqi| for 1≤i ≤3. Assuming that Q fits in memory and P is indexed by an R-tree, we propose several algorithms for finding the group nearest neighbors efficiently. As a second step, we extend our techniques for situations where Q cannot fit in memory, covering both indexed and non-indexed query points. An experimental evaluation identifies the best alternative based on the data and query properties.
Back to Top Additional Information
Citation:  Dimitris Papadias, Qiongmao Shen, Yufei Tao, Kyriakos Mouratidis, "Group Nearest Neighbor Queries," icde, p. 301,  20th International Conference on Data Engineering (ICDE'04),  2004