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
2790
Venue
SIGMOD
Year
1995
Pagerank
0.0006954126
Overall Rank
48 | 99.67%
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,574 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 6.9520978e-05
3,802 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 6.7524078e-05
3,815 Location-based Spatial Queries 2003 SIGMOD 6.7314038e-05
4,111 Searching Trajectories by Locations - An Efficiency Study 2010 SIGMOD 6.4354586e-05
4,539 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.0982886e-05
4,880 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 5.8526687e-05
4,896 The V*-Diagram: A Query-Dependent Approach to Moving KNN Queries 2008 VLDB 5.8467149e-05
5,061 Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search 2002 SIGMOD 5.717245e-05
5,396 Scalable Ranked Publish/Subscribe 2008 VLDB 5.5279512e-05
5,463 The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data 2023 SIGMOD 5.4920768e-05
5,646 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 5.3924438e-05
5,800 AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data 2015 VLDB 5.3218628e-05
5,883 Ranked Subsequence Matching in Time-Series Databases 2007 VLDB 5.2865165e-05
5,889 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.2842168e-05
5,917 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB 5.2690256e-05
5,922 FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data 2008 VLDB 5.2678889e-05
6,316 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.1098143e-05
6,496 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.0327729e-05
6,545 Flexible Aggregate Similarity Search 2011 SIGMOD 5.01361e-05
6,778 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 4.9237313e-05
6,802 An Incremental Hausdorff Distance Calculation Algorithm 2011 VLDB 4.9172931e-05
7,048 Continuous Obstructed Nearest Neighbor Queries in Spatial Databases 2009 SIGMOD 4.8460286e-05
7,417 Uncertain Time-Series Similarity: Return to the Basics 2012 VLDB 4.7309512e-05
7,539 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 4.7116182e-05
8,107 Adaptive Location Constraint Processing 2007 SIGMOD 4.5811252e-05
8,127 Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation 2001 VLDB 4.5757206e-05
8,217 Maintenance of Spatial Semijoin Queries on Moving Points 2004 VLDB 4.5519066e-05
8,354 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 4.5329424e-05
8,629 Spatial Queries with Two kNN Predicates 2012 VLDB 4.4766922e-05
8,890 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 4.4235206e-05
8,928 Processing Moving kNN Queries Using Influential Neighbor Sets 2015 VLDB 4.4229886e-05
9,020 Indexing Medium-dimensionality Data in Oracle 1999 SIGMOD 4.4049428e-05
9,119 Hypersphere Dominance: An Optimal Approach 2014 SIGMOD 4.3881453e-05
9,173 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 4.3807204e-05
9,433 A Generic Framework for Handling Uncertain Data with Local Correlations 2011 VLDB 4.3399748e-05
9,763 Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations 2025 PODS 4.2815042e-05
9,790 Distance-Based Outlier Detection: Consolidation and Renewed Bearing 2010 VLDB 4.2782534e-05
10,129 WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search 2026 SIGMOD 4.1905499e-05
10,223 On Fair Epsilon Net and Geometric Hitting Set 2026 VLDB 4.1905499e-05
11,951 A Demonstration of AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data 2015 VLDB 4.1905499e-05
12,083 PLASMA-HD: Probing the LAttice Structure and MAkeup of High-dimensional Data 2013 VLDB 4.1905499e-05
12,235 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 4.1905499e-05
12,488 On Dominating Your Neighborhood Profitably 2007 VLDB 4.1905499e-05
12,577 Complex Spatio-Temporal Pattern Queries 2005 VLDB 4.1905499e-05
12,681 Analyzing Energy Behavior of Spatial Access Methods for Memory-Resident Data 2001 VLDB 4.1905499e-05
12,760 Algorithms for Querying by Spatial Structure 1998 VLDB 4.1905499e-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.0032118946
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016113151
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083300888
56 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00065500256
147 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041201518
290 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00028845557
356 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00026091196
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
6,865 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB 4.9002126e-05
1,512 Indexing Land Surface for Efficient kNN Query 2008 VLDB 0.00011582099
3,802 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 6.7524078e-05
4,035 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 6.5111577e-05
12,276 Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures 2010 VLDB 4.1905499e-05
5,917 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB 5.2690256e-05
434 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00023277433
4,880 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 5.8526687e-05
1,535 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 0.00011461371
1,769 Closest Pair Queries in Spatial Databases 2000 SIGMOD 0.00010608375