期刊
ACM TRANSACTIONS ON DATABASE SYSTEMS
卷 30, 期 2, 页码 529-576出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1071610.1071616
关键词
algorithms; experimentation; spatial database; nearest neighbor queries; aggregation
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 q(1),... q(n), an ANN query outputs the facility p is an element of P that minimizes the sum of distances \pq(i)\ for 1 <= i <= n that the users have to travel in order to meet there. Similarly, another ANN query may report the point p is an element of 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据