Group Nearest Neighbor Queries

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 re...

Full description

Saved in:
Bibliographic Details
Main Authors: PAPADIAS, Dimitris, SHEN, Qiongmao, TAO, Yufei, MOURATIDIS, Kyriakos
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2004
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/882
https://ink.library.smu.edu.sg/context/sis_research/article/1881/viewcontent/ICDE04_GNN.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-1881
record_format dspace
spelling sg-smu-ink.sis_research-18812016-04-29T07:05:46Z Group Nearest Neighbor Queries PAPADIAS, Dimitris SHEN, Qiongmao TAO, Yufei MOURATIDIS, Kyriakos 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. 2004-03-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/882 info:doi/10.1109/ICDE.2004.1320006 https://ink.library.smu.edu.sg/context/sis_research/article/1881/viewcontent/ICDE04_GNN.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Databases and Information Systems Numerical Analysis and Scientific Computing
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Databases and Information Systems
Numerical Analysis and Scientific Computing
spellingShingle Databases and Information Systems
Numerical Analysis and Scientific Computing
PAPADIAS, Dimitris
SHEN, Qiongmao
TAO, Yufei
MOURATIDIS, Kyriakos
Group Nearest Neighbor Queries
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.
format text
author PAPADIAS, Dimitris
SHEN, Qiongmao
TAO, Yufei
MOURATIDIS, Kyriakos
author_facet PAPADIAS, Dimitris
SHEN, Qiongmao
TAO, Yufei
MOURATIDIS, Kyriakos
author_sort PAPADIAS, Dimitris
title Group Nearest Neighbor Queries
title_short Group Nearest Neighbor Queries
title_full Group Nearest Neighbor Queries
title_fullStr Group Nearest Neighbor Queries
title_full_unstemmed Group Nearest Neighbor Queries
title_sort group nearest neighbor queries
publisher Institutional Knowledge at Singapore Management University
publishDate 2004
url https://ink.library.smu.edu.sg/sis_research/882
https://ink.library.smu.edu.sg/context/sis_research/article/1881/viewcontent/ICDE04_GNN.pdf
_version_ 1770570749090725888