HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Journal/Magazine Articles >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/2388
Title: Aggregate nearest neighbor queries in spatial databases
Authors: Papadias, Dimitris
Tao, Yufei
Mouratidis, Kyriakos
Hui, Chun Kit
Keywords: Database management
Information storage and retrieval
Algorithms
Experimentation
Spatial database
Nearest neighbor queries
Aggregation
Issue Date: 2005
Citation: ACM transactions on database systems, v. 30, no. 2, June 2005, p. 529-576
Abstract: 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 ∈ P that minimizes the sum of distances |pqi| for 1≤i≤n that the users have to travel in order to meet there. Similarly, another ANN query may report the point p ∈ 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.
Rights: © ACM, 2005. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM transactions on Database Systems, v. 30, no. 2, June 2005.
URI: http://hdl.handle.net/1783.1/2388
Appears in Collections:CSE Journal/Magazine Articles

Files in This Item:

File Description SizeFormat
TODS05ANN.pdfpre-published version688KbAdobe PDFView/Open

Find published version via OpenURL Link Resolver

All items in this Repository are protected by copyright, with all rights reserved.