Database Paper Browser

Back to papers

Nearest Neighbor Queries

Summary: Presents an efficient branch-and-bound R-tree traversal for nearest neighbor queries in spatial databases. Generalizes to kNN with metrics for optimistic and pessimistic search ordering and pruning, plus empirical scalability results. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
2789
Venue
SIGMOD
Year
1995
Pagerank
0.0007015885
Overall Rank
47 | 99.68%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 96 citing papers.

Rank Citing Paper Year Venue Pagerank
91 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.0005181666
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.0004429571
195 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00035406558
243 Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases 2001 SIGMOD 0.00031074984
284 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00028994728
386 Shooting Stars in the Sky: An Online Algorithm for Skyline Queries 2002 VLDB 0.00024768022
433 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00023310419
471 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00022364776
575 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00019882723
598 Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases 2004 VLDB 0.00019474545
601 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00019375875
648 Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects 2009 VLDB 0.00018666267
665 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00018451109
682 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00018201541
699 Exact Indexing of Dynamic Time Warping 2002 VLDB 0.00018015254
701 Efficient Algorithms for Mining Outliers from Large Data Sets 2000 SIGMOD 0.00017938417
749 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00017228334
802 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.00016502317
871 Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation 1997 SIGMOD 0.00015767786
997 Similarity-Based Queries for Time Series Data 1997 SIGMOD 0.00014739219
1,183 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00013455596
1,275 Continuous Nearest Neighbor Search 2002 VLDB 0.00012883899
1,363 Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials 2004 SIGMOD 0.00012372959
1,364 Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination 2020 SIGMOD 0.00012370117
1,435 Simba: Efficient In-Memory Spatial Analytics 2016 SIGMOD 0.00012004456
1,513 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 0.00011593275
1,514 Indexing Land Surface for Efficient kNN Query 2008 VLDB 0.00011593275
1,526 Monitoring Path Nearest Neighbor in Road Networks 2009 SIGMOD 0.00011512916
1,528 A Model for the Prediction of R-tree Performance 1996 PODS 0.00011497734
1,542 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 0.00011456321
1,576 Continuous Nearest Neighbor Monitoring in Road Networks 2006 VLDB 0.00011286717
1,631 Incremental Distance Join Algorithms for Spatial Databases 1998 SIGMOD 0.00011078269
1,755 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 0.00010669106
1,768 Closest Pair Queries in Spatial Databases 2000 SIGMOD 0.00010622873
1,917 A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects 2005 SIGMOD 0.0001009778
1,925 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010073407
1,933 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010038508
1,971 LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index 2016 SIGMOD 9.893198e-05
2,115 LISA: A Learned Index Structure for Spatial Data 2020 SIGMOD 9.5257379e-05
2,247 On Efficient Spatial Matching 2007 VLDB 9.2048219e-05
2,360 Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring 2005 SIGMOD 8.9605432e-05
2,541 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB 8.5795657e-05
2,678 Effectively Learning Spatial Indices 2020 VLDB 8.3252088e-05
2,711 On Computing Top-t Most Influential Spatial Sites 2005 VLDB 8.2492925e-05
2,974 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 7.789769e-05
3,107 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.550885e-05
3,275 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.2897998e-05
3,415 Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates 2003 VLDB 7.1219721e-05
3,555 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9772546e-05
3,570 Location-Aware Type Ahead Search on Spatial Databases: Semantics and Efficiency 2011 SIGMOD 6.958427e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032169493
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016162015
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083378538
56 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00065631356
148 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041182766
290 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00028919734
354 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00026137988
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
6,946 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB 4.8909775e-05
1,514 Indexing Land Surface for Efficient kNN Query 2008 VLDB 0.00011593275
3,800 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 6.7585633e-05
4,070 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 6.4784181e-05
12,268 Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures 2010 VLDB 4.1945683e-05
5,917 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB 5.2739511e-05
433 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00023310419
4,960 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 5.7987607e-05
1,542 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 0.00011456321
1,768 Closest Pair Queries in Spatial Databases 2000 SIGMOD 0.00010622873