Please use this identifier to cite or link to this item:

All-nearest-neighbors queries in spatial databases

Authors Zhang, J.
Mamoulis, N. HKUST affiliated (currently or previously)
Papadias, D. View this author's profile
Tao, Y.
Issue Date 2004
Source Proceedings of the International Conference on Scientific and Statistical Database Management, SSDBM , v. 16, 2004, p. 297-306
Summary Given two sets A and B of multidimensional objects, the all-nearest-neighbors (ANN) query retrieves for each object in A its nearest neighbor in B. Although this operation is common in several applications, it has not received much attention in the database literature. In this paper we study alternative methods for processing ANN queries depending on whether A and B are indexed. Our algorithms are evaluated through extensive experimentation using synthetic and real datasets. The performance studies show that they are an order of magnitude faster than a previous approach based on closest-pairs query processing.
ISSN 1099-3371
Rights © 2004 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Language English
Format Conference paper
Access View full-text via Scopus
Files in this item:
File Description Size Format
papadias3.pdf 155063 B Adobe PDF