DBScholar

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
2851
Venue
SIGMOD
Year
1995
Pagerank
0.00052102434
Overall Rank
28 | 99.81%
DOI
10.1145/223784.223794

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{roussopoulos_sigmod95,
        title = {{Nearest Neighbor Queries}},
        author = {Roussopoulos, Nick and Kelley, Stephen and Vincent, Frédéric},
        series = {{SIGMOD} '95},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/223784.223794},
        url = {https://dl.acm.org/doi/10.1145/223784.223794},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 46 of 96 citing papers.

Rank Citing Paper Year Venue Pagerank
3,562 Location-based Spatial Queries 2003 SIGMOD 7.3080612e-05
3,581 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 7.2873782e-05
3,866 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 7.061829e-05
4,316 Searching Trajectories by Locations - An Efficiency Study 2010 SIGMOD 6.7647222e-05
4,711 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 6.5506926e-05
4,751 The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data 2023 SIGMOD 6.5241784e-05
4,815 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.4949956e-05
4,937 The V*-Diagram: A Query-Dependent Approach to Moving KNN Queries 2008 VLDB 6.4350791e-05
5,395 AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data 2015 VLDB 6.2331619e-05
5,405 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 6.2291247e-05
5,517 Scalable Ranked Publish/Subscribe 2008 VLDB 6.1889819e-05
5,592 Ranked Subsequence Matching in Time-Series Databases 2007 VLDB 6.1552372e-05
5,664 FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data 2008 VLDB 6.1289238e-05
5,838 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 6.0702428e-05
5,875 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB 6.0564961e-05
5,963 Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search 2002 SIGMOD 6.0267197e-05
6,426 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.8809448e-05
6,646 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.8148791e-05
6,746 Flexible Aggregate Similarity Search 2011 SIGMOD 5.7850397e-05
6,749 An Incremental Hausdorff Distance Calculation Algorithm 2011 VLDB 5.7844585e-05
6,887 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 5.7457967e-05
7,140 Continuous Obstructed Nearest Neighbor Queries in Spatial Databases 2009 SIGMOD 5.6928705e-05
7,350 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 5.6358517e-05
7,608 Uncertain Time-Series Similarity: Return to the Basics 2012 VLDB 5.5845913e-05
8,200 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.4677285e-05
8,391 Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation 2001 VLDB 5.4356884e-05
8,593 Maintenance of Spatial Semijoin Queries on Moving Points 2004 VLDB 5.4055214e-05
8,659 Spatial Queries with Two kNN Predicates 2012 VLDB 5.3904242e-05
8,787 Adaptive Location Constraint Processing 2007 SIGMOD 5.3729697e-05
9,080 Processing Moving kNN Queries Using Influential Neighbor Sets 2015 VLDB 5.3251649e-05
9,115 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 5.3215443e-05
9,233 Indexing Medium-dimensionality Data in Oracle 1999 SIGMOD 5.3017497e-05
9,261 Hypersphere Dominance: An Optimal Approach 2014 SIGMOD 5.2968259e-05
9,417 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.2740525e-05
9,581 A Generic Framework for Handling Uncertain Data with Local Correlations 2011 VLDB 5.2528121e-05
9,914 Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations 2025 PODS 5.1955087e-05
9,952 Distance-Based Outlier Detection: Consolidation and Renewed Bearing 2010 VLDB 5.191171e-05
10,417 WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search 2026 SIGMOD 5.093636e-05
10,511 On Fair Epsilon Net and Geometric Hitting Set 2026 VLDB 5.093636e-05
12,141 A Demonstration of AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data 2015 VLDB 5.093636e-05
12,272 PLASMA-HD: Probing the LAttice Structure and MAkeup of High-dimensional Data 2013 VLDB 5.093636e-05
12,422 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 5.093636e-05
12,672 On Dominating Your Neighborhood Profitably 2007 VLDB 5.093636e-05
12,761 Complex Spatio-Temporal Pattern Queries 2005 VLDB 5.093636e-05
12,865 Analyzing Energy Behavior of Spatial Access Methods for Memory-Resident Data 2001 VLDB 5.093636e-05
12,944 Algorithms for Querying by Spatial Structure 1998 VLDB 5.093636e-05
Previous Page 2 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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.0020210012
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.001157935
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.0003221055
145 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00029548428
329 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00021068647
354 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00020355578
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 6,561 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB
2 1,619 Indexing Land Surface for Efficient kNN Query 2008 VLDB
3 3,581 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD
4 3,710 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD
5 12,463 Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures 2010 VLDB
6 5,875 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB
7 433 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD
8 4,711 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD
9 1,605 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB
10 1,685 Closest Pair Queries in Spatial Databases 2000 SIGMOD