Article

Free access

Nearest neighbor queries

Authors:

Nick Roussopoulos,

Stephen Kelley,

Frédéric VincentAuthors Info & Claims

SIGMOD '95: Proceedings of the 1995 ACM SIGMOD international conference on Management of data

Pages 71 - 79

https://doi.org/10.1145/223784.223794

Published: 22 May 1995 Publication History

PDF eReader

Abstract

A frequently encountered type of query in Geographic Information Systems is to find the k nearest neighbor objects to a given point in space. Processing such queries requires substantially different search algorithms than those for location or range queries. In this paper we present an efficient branch-and-bound R-tree traversal algorithm to find the nearest neighbor object to a point, and then generalize it to finding the k nearest neighbors. We also discuss metrics for an optimistic and a pessimistic search ordering strategy as well as for pruning. Finally, we present the results of several experiments obtained using the implementation of our algorithm and examine the behavior of the metrics and the scalability of the algorithm.

References

[1]

Beckmann, N., H.-P. Kriegel, R. Schneider and B. Seeger, "The R*-tree" an efficient and robust access method for points and rectangles," ACM SIGMOD, pp 322-331, May 1990.

Digital Library

Google Scholar

[2]

Brinkhoff, T., Kriegel, H.P., and Seeger, B., "Efficient Processing of Spatial Joins Using R- trees," Proc. ACM SIGMOD, May 1993, pp. 237- 246.

Digital Library

Google Scholar

[3]

Friedman, J.H., Bentley, j.L., and Finkel, R.A., "An algorithm for finding the best matches in logarithmic expected time," ACM Trans. Math. Software, 3, September 1977, pp. 209-226.

Digital Library

Google Scholar

[4]

Guttman, A., "R-trees,: A Dynamic index Structure for Spatial Searching," Proc. ACM SIG- MOD, pp. 47-57, June 1984.

Digital Library

Google Scholar

[5]

Horowitz, E., Sahni, S., "Fundamentals of Computer Algorithms," Computer Science Press, 1978, pp. 370-421.

Digital Library

Google Scholar

[6]

Jagadish, H.V., "Linear Clustering of Objects with Multiple Attributes," Proc. ACM SIGMOD, May 1990, pp. 332-342.

Digital Library

Google Scholar

[7]

Kamel, I. and Faloutsos, C., "Hilbert R- Tree: an Improved R-Tree Using Fractals," Proc. of VLDB, 1994, pp. 500-509.

Digital Library

Google Scholar

[8]

Roussopoulos, N. and D. Leifker, "Direct Spatial Search on Pictorial Databases Using Packed R-trees," Proc. ACM SIGMOD, May 1985.

Digital Library

Google Scholar

[9]

Samet, H., "The Design & Analysis Of Spatial Data Structures," Addison-Wesley, 1989.

Digital Library

Google Scholar

[10]

Samet, H., "Applications Of Spatial Data Structures, Computer Graphics, Image Processing and GIS," Addison-Wesley, 1990.

Digital Library

Google Scholar

[11]

Sellis T., Roussopoulos, N., and Faloutsos, C., "The R+-tree: A Dynamic Index for Multidimensional Objects," Proc. 13th international Conference on Very Large Data Bases, 1987, pp. 507-518.

Digital Library

Google Scholar

[12]

Sproull, R.F., "Refinements to Nearest- Neighbor Searching in k-Dimensional Trees," A1- gorithmica, 6, 1987, pp. 579-589.

Google Scholar

Cited By

View all

Tatit PAdhinugraha KTaniar D(2024)Navigating the Maps: Euclidean vs. Road Network Distances in Spatial QueriesAlgorithms10.3390/a1701002917:1(29)Online publication date: 10-Jan-2024
https://doi.org/10.3390/a17010029
Li MWang HDai HLi MChai CGu RChen FChen ZLi SLiu QChen G(2024)A Survey of Multi-Dimensional Indexes: Past and Future TrendsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.336418336:8(3635-3655)Online publication date: Aug-2024
https://doi.org/10.1109/TKDE.2024.3364183
Chen JGao HZhang KWang JLuo YWu ZLi J(2024)On Efficiently Processing MIT Queries in Trajectory DataIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.336194836:7(3329-3347)Online publication date: Jul-2024
https://doi.org/10.1109/TKDE.2024.3361948
Show More Cited By

Index Terms

Nearest neighbor queries

Recommendations

Nearest neighbor queries

A frequently encountered type of query in Geographic Information Systems is to find the k nearest neighbor objects to a given point in space. Processing such queries requires substantially different search algorithms than those for location or range ...
Approximate Direct and Reverse Nearest Neighbor Queries, and the k-nearest Neighbor Graph
SISAP '09: Proceedings of the 2009 Second International Workshop on Similarity Search and Applications

Retrieving the \emph{k-nearest neighbors} of a query object is a basic primitive in similarity searching. A related, far less explored primitive is to obtain the dataset elements which would have the query object within their own \emph{k}-nearest ...
K-Nearest Neighbor Finding Using MaxNearestDist

Similarity searching often reduces to finding the k nearest neighbors to a query object. Finding the k nearest neighbors is achieved by applying either a depth- first or a best-first algorithm to the search hierarchy containing the data. These ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGMOD '95: Proceedings of the 1995 ACM SIGMOD international conference on Management of data

June 1995

508 pages

ISBN:0897917316

DOI:10.1145/223784

Editors:
Michael Carey
Univ. of Wisconsin
,
Donovan Schneider
Red Brick Systems

ACM SIGMOD Record Volume 24, Issue 2
May 1995
490 pages
ISSN:0163-5808
DOI:10.1145/568271
Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 May 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS95

Sponsor:

SIGMOD/PODS95: Joint ACM SIGMOD Intl Conference on Management of Data and ACM SIGACT-SIGMOD- SIGART Symposium on Principles of Database Systems

May 22 - 25, 1995

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1,230
Total Citations
View Citations
7,274
Total Downloads

Downloads (Last 12 months)382
Downloads (Last 6 weeks)48

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Tatit PAdhinugraha KTaniar D(2024)Navigating the Maps: Euclidean vs. Road Network Distances in Spatial QueriesAlgorithms10.3390/a1701002917:1(29)Online publication date: 10-Jan-2024
https://doi.org/10.3390/a17010029
Li MWang HDai HLi MChai CGu RChen FChen ZLi SLiu QChen G(2024)A Survey of Multi-Dimensional Indexes: Past and Future TrendsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.336418336:8(3635-3655)Online publication date: Aug-2024
https://doi.org/10.1109/TKDE.2024.3364183
Chen JGao HZhang KWang JLuo YWu ZLi J(2024)On Efficiently Processing MIT Queries in Trajectory DataIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.336194836:7(3329-3347)Online publication date: Jul-2024
https://doi.org/10.1109/TKDE.2024.3361948
Xu ZPeng SGeng CMou LYan ZSun JBao HZhou X(2024)Relightable and Animatable Neural Avatar from Sparse-View Video2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.00100(990-1000)Online publication date: 16-Jun-2024
https://doi.org/10.1109/CVPR52733.2024.00100
Zhang RLi YZhuang MChen GYu Z(2024)Processing Conflict-Aware $k$ Nearest Neighbor Queries in Euclidean Space2024 IEEE International Conference on Big Data and Smart Computing (BigComp)10.1109/BigComp60711.2024.00035(175-182)Online publication date: 18-Feb-2024
https://doi.org/10.1109/BigComp60711.2024.00035
Liu PLi CChen H(2024)Enhancing Storage Efficiency and Performance: A Survey of Data Partitioning TechniquesJournal of Computer Science and Technology10.1007/s11390-024-3538-139:2(346-368)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s11390-024-3538-1
Dutta ABreloff SMahmud DDai FSinsel EWarren CWu J(2023)Automated Classification of the Phases Relevant to Work-Related Musculoskeletal Injury Risks in Residential Roof Shingle Installation Operations Using Machine LearningBuildings10.3390/buildings1306155213:6(1552)Online publication date: 18-Jun-2023
https://doi.org/10.3390/buildings13061552
Gu TFeng KCong GLong CWang ZWang S(2023)The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial DataProceedings of the ACM on Management of Data10.1145/35889171:1(1-26)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588917
Zheng YLu RGuan YZhang SShao JWang FZhu H(2023)Efficient and Privacy-Preserving Spatial-Feature-Based Reverse kNN QueryIEEE Transactions on Services Computing10.1109/TSC.2022.321909916:4(2620-2631)Online publication date: 1-Jul-2023
https://doi.org/10.1109/TSC.2022.3219099
Xu HXiao BLiu XWang LJiang SXue WWang JLi K(2023)Empowering Authenticated and Efficient Queries for STK Transaction-Based BlockchainsIEEE Transactions on Computers10.1109/TC.2023.324126372:8(2209-2223)Online publication date: 1-Aug-2023
https://doi.org/10.1109/TC.2023.3241263
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Nearest neighbor queries

Approximate Direct and Reverse Nearest Neighbor Queries, and the k-nearest Neighbor Graph

K-Nearest Neighbor Finding Using MaxNearestDist