loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
20th International Conference on Data Engineering (ICDE'04)
Group Nearest Neighbor Queries
Boston, Massachusetts
March 30-April 02
ISBN: 0-7695-2065-0
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
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.
Citation:
Dimitris Papadias, Qiongmao Shen, Yufei Tao, Kyriakos Mouratidis, "Group Nearest Neighbor Queries," icde, pp.301, 20th International Conference on Data Engineering (ICDE'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.