Skip to main content
Article
Group Nearest Neighbor Queries
ICDE 2004: 20th IEEE International Conference on Data Engineering: Proceedings: 30 March-2 April, 2004, Boston
  • Dimitris PAPADIAS, Hong Kong University of Science and Technology
  • Qiongmao SHEN
  • Yufei TAO, City University of Hong Kong
  • Kyriakos MOURATIDIS, Singapore Management University
Publication Type
Conference Proceeding Article
Version
submittedVersion
Publication Date
3-2004
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.

ISBN
9780769520650
Identifier
10.1109/ICDE.2004.1320006
Publisher
IEEE Computer Society
City or Country
Los Alamitos, CA
Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Additional URL
http://doi.ieeecomputersociety.org/10.1109/ICDE.2004.1320006
Citation Information
Dimitris PAPADIAS, Qiongmao SHEN, Yufei TAO and Kyriakos MOURATIDIS. "Group Nearest Neighbor Queries" ICDE 2004: 20th IEEE International Conference on Data Engineering: Proceedings: 30 March-2 April, 2004, Boston (2004) p. 301 - 312
Available at: http://works.bepress.com/kyriakos_mouratidis/13/