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 46 of 96 citing papers.

Rank Citing Paper Year Venue Pagerank
3,579 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 6.9502303e-05
3,800 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 6.7585633e-05
3,814 Location-based Spatial Queries 2003 SIGMOD 6.7341058e-05
4,112 Searching Trajectories by Locations - An Efficiency Study 2010 SIGMOD 6.4422697e-05
4,529 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.1078661e-05
4,882 The V*-Diagram: A Query-Dependent Approach to Moving KNN Queries 2008 VLDB 5.8548674e-05
4,960 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 5.7987607e-05
5,065 Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search 2002 SIGMOD 5.7247716e-05
5,391 Scalable Ranked Publish/Subscribe 2008 VLDB 5.533552e-05
5,572 The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data 2023 SIGMOD 5.4277273e-05
5,636 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 5.3981191e-05
5,790 AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data 2015 VLDB 5.3269734e-05
5,878 Ranked Subsequence Matching in Time-Series Databases 2007 VLDB 5.2916009e-05
5,882 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.2892937e-05
5,917 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB 5.2739511e-05
6,045 FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data 2008 VLDB 5.2372658e-05
6,325 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.1105081e-05
6,500 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.0381573e-05
6,547 Flexible Aggregate Similarity Search 2011 SIGMOD 5.0183532e-05
6,770 An Incremental Hausdorff Distance Calculation Algorithm 2011 VLDB 4.9317829e-05
6,778 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 4.9284526e-05
7,049 Continuous Obstructed Nearest Neighbor Queries in Spatial Databases 2009 SIGMOD 4.8505287e-05
7,418 Uncertain Time-Series Similarity: Return to the Basics 2012 VLDB 4.7354852e-05
7,540 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 4.7159549e-05
8,110 Adaptive Location Constraint Processing 2007 SIGMOD 4.5843047e-05
8,123 Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation 2001 VLDB 4.5801104e-05
8,223 Maintenance of Spatial Semijoin Queries on Moving Points 2004 VLDB 4.5553657e-05
8,359 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 4.5372925e-05
8,629 Spatial Queries with Two kNN Predicates 2012 VLDB 4.4809879e-05
8,889 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 4.4278238e-05
8,925 Processing Moving kNN Queries Using Influential Neighbor Sets 2015 VLDB 4.427232e-05
9,017 Indexing Medium-dimensionality Data in Oracle 1999 SIGMOD 4.4091374e-05
9,121 Hypersphere Dominance: An Optimal Approach 2014 SIGMOD 4.3922853e-05
9,143 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 4.3850454e-05
9,427 A Generic Framework for Handling Uncertain Data with Local Correlations 2011 VLDB 4.3441378e-05
9,761 Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations 2025 PODS 4.2856106e-05
9,787 Distance-Based Outlier Detection: Consolidation and Renewed Bearing 2010 VLDB 4.2823546e-05
10,129 WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search 2026 SIGMOD 4.1945683e-05
10,223 On Fair Epsilon Net and Geometric Hitting Set 2026 VLDB 4.1945683e-05
11,943 A Demonstration of AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data 2015 VLDB 4.1945683e-05
12,075 PLASMA-HD: Probing the LAttice Structure and MAkeup of High-dimensional Data 2013 VLDB 4.1945683e-05
12,227 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 4.1945683e-05
12,479 On Dominating Your Neighborhood Profitably 2007 VLDB 4.1945683e-05
12,568 Complex Spatio-Temporal Pattern Queries 2005 VLDB 4.1945683e-05
12,672 Analyzing Energy Behavior of Spatial Access Methods for Memory-Resident Data 2001 VLDB 4.1945683e-05
12,751 Algorithms for Querying by Spatial Structure 1998 VLDB 4.1945683e-05
Previous Page 2 / 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