Country | : |
![]() |
Department | : | Singapore Management University |
Project Title | : | Group Nearest Neighbor Queries |
Researcher | : | TAO, Yufei , MOURATIDIS, Kyriakos , SHEN, Qiongmao , PAPADIAS, Dimitris |
Keyword | : | Numerical Analysis and Scientific Computing , Databases and Information Systems |
Publisher | : | Institutional Knowledge at Singapore Management University |
Year End | : | 2004 |
Identifier | : | https://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=1881&context=sis_research , https://ink.library.smu.edu.sg/sis_research/882 |
Source | : | Research Collection School Of Computing and Information Systems |
Abstract / Description | : |
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. |