Aggregate Nearest Neighbor Queries in Spatial Databases
Given two spatial datasets P (e.g., facilities) and Q (queries), an aggregate nearest neighbor (ANN) query retrieves the point(s) of P with the smallest aggregate distance(s) to points in Q. Assuming, for example, n users at locations q1,...qn, an ANN query outputs the facility p belongs to P that m...
Saved in:
Main Authors: | , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2005
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/175 https://ink.library.smu.edu.sg/context/sis_research/article/1174/viewcontent/TODS05_ANN.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-1174 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-11742016-04-29T06:15:47Z Aggregate Nearest Neighbor Queries in Spatial Databases PAPADIAS, Dimitris TAO, Yufei MOURATIDIS, Kyriakos HUI, Chun Kit Given two spatial datasets P (e.g., facilities) and Q (queries), an aggregate nearest neighbor (ANN) query retrieves the point(s) of P with the smallest aggregate distance(s) to points in Q. Assuming, for example, n users at locations q1,...qn, an ANN query outputs the facility p belongs to P that minimizes the sum of distances |pqi| for 1 is less than or equal to i is less than or equal to n that the users have to travel in order to meet there. Similarly, another ANN query may report the point p belongs to P that minimizes the maximum distance that any user has to travel, or the minimum distance from some user to his/her closest facility. If Q fits in memory and P is indexed by an R-tree, we develop algorithms for aggregate nearest neighbors that capture several versions of the problem, including weighted queries and incremental reporting of results. Then, we analyze their performance and propose cost models for query optimization. Finally, we extend our techniques for disk-resident queries and approximate ANN retrieval. The efficiency of the algorithms and the accuracy of the cost models are evaluated through extensive experiments with real and synthetic datasets. 2005-06-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/175 info:doi/10.1145/1071610.1071616 https://ink.library.smu.edu.sg/context/sis_research/article/1174/viewcontent/TODS05_ANN.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 Aggregation Nearest neighbor queries Spatial database weighted queries Databases and Information Systems Numerical Analysis and Scientific Computing Theory and Algorithms |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Aggregation Nearest neighbor queries Spatial database weighted queries Databases and Information Systems Numerical Analysis and Scientific Computing Theory and Algorithms |
spellingShingle |
Aggregation Nearest neighbor queries Spatial database weighted queries Databases and Information Systems Numerical Analysis and Scientific Computing Theory and Algorithms PAPADIAS, Dimitris TAO, Yufei MOURATIDIS, Kyriakos HUI, Chun Kit Aggregate Nearest Neighbor Queries in Spatial Databases |
description |
Given two spatial datasets P (e.g., facilities) and Q (queries), an aggregate nearest neighbor (ANN) query retrieves the point(s) of P with the smallest aggregate distance(s) to points in Q. Assuming, for example, n users at locations q1,...qn, an ANN query outputs the facility p belongs to P that minimizes the sum of distances |pqi| for 1 is less than or equal to i is less than or equal to n that the users have to travel in order to meet there. Similarly, another ANN query may report the point p belongs to P that minimizes the maximum distance that any user has to travel, or the minimum distance from some user to his/her closest facility. If Q fits in memory and P is indexed by an R-tree, we develop algorithms for aggregate nearest neighbors that capture several versions of the problem, including weighted queries and incremental reporting of results. Then, we analyze their performance and propose cost models for query optimization. Finally, we extend our techniques for disk-resident queries and approximate ANN retrieval. The efficiency of the algorithms and the accuracy of the cost models are evaluated through extensive experiments with real and synthetic datasets. |
format |
text |
author |
PAPADIAS, Dimitris TAO, Yufei MOURATIDIS, Kyriakos HUI, Chun Kit |
author_facet |
PAPADIAS, Dimitris TAO, Yufei MOURATIDIS, Kyriakos HUI, Chun Kit |
author_sort |
PAPADIAS, Dimitris |
title |
Aggregate Nearest Neighbor Queries in Spatial Databases |
title_short |
Aggregate Nearest Neighbor Queries in Spatial Databases |
title_full |
Aggregate Nearest Neighbor Queries in Spatial Databases |
title_fullStr |
Aggregate Nearest Neighbor Queries in Spatial Databases |
title_full_unstemmed |
Aggregate Nearest Neighbor Queries in Spatial Databases |
title_sort |
aggregate nearest neighbor queries in spatial databases |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2005 |
url |
https://ink.library.smu.edu.sg/sis_research/175 https://ink.library.smu.edu.sg/context/sis_research/article/1174/viewcontent/TODS05_ANN.pdf |
_version_ |
1770568910772371456 |