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
hbeaae9ea2f876907
Venue
SIGMOD
Year
1995
Pagerank
0.00051312804
Overall Rank
28 | 99.82%
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 47 of 97 citing papers.

Rank Citing Paper Year Venue Pagerank
3,638 Location-based Spatial Queries 2003 SIGMOD 7.1446219e-05
3,658 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 7.1243855e-05
3,887 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9458013e-05
4,352 Searching Trajectories by Locations - An Efficiency Study 2010 SIGMOD 6.6423022e-05
4,797 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 6.4113285e-05
4,850 The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data 2023 SIGMOD 6.3808017e-05
4,927 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.3503189e-05
5,062 The V*-Diagram: A Query-Dependent Approach to Moving KNN Queries 2008 VLDB 6.2910498e-05
5,342 FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data 2008 VLDB 6.1725496e-05
5,519 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB 6.0968085e-05
5,526 AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data 2015 VLDB 6.0937354e-05
5,532 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 6.0932822e-05
5,655 Scalable Ranked Publish/Subscribe 2008 VLDB 6.0501178e-05
5,722 Ranked Subsequence Matching in Time-Series Databases 2007 VLDB 6.0183253e-05
5,957 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.93405e-05
6,032 Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search 2002 SIGMOD 5.9097667e-05
6,540 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.7523628e-05
6,740 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.6916981e-05
6,790 An Incremental Hausdorff Distance Calculation Algorithm 2011 VLDB 5.6812765e-05
6,868 Flexible Aggregate Similarity Search 2011 SIGMOD 5.6599382e-05
7,023 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 5.6186604e-05
7,289 Continuous Obstructed Nearest Neighbor Queries in Spatial Databases 2009 SIGMOD 5.5652691e-05
7,494 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 5.5095043e-05
7,754 Uncertain Time-Series Similarity: Return to the Basics 2012 VLDB 5.4592892e-05
8,369 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.3450708e-05
8,566 Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation 2001 VLDB 5.3137327e-05
8,755 Maintenance of Spatial Semijoin Queries on Moving Points 2004 VLDB 5.2845183e-05
8,820 Spatial Queries with Two kNN Predicates 2012 VLDB 5.2694776e-05
8,950 Adaptive Location Constraint Processing 2007 SIGMOD 5.2524216e-05
9,255 Processing Moving kNN Queries Using Influential Neighbor Sets 2015 VLDB 5.2056825e-05
9,288 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 5.2021887e-05
9,405 Indexing Medium-dimensionality Data in Oracle 1999 SIGMOD 5.1828502e-05
9,435 Hypersphere Dominance: An Optimal Approach 2014 SIGMOD 5.1780501e-05
9,597 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.1557462e-05
9,757 A Generic Framework for Handling Uncertain Data with Local Correlations 2011 VLDB 5.1349531e-05
10,101 Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations 2025 PODS 5.0789354e-05
10,139 Distance-Based Outlier Detection: Consolidation and Renewed Bearing 2010 VLDB 5.0746983e-05
10,325 WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search 2026 SIGMOD 5.0346745e-05
10,696 On Fair Epsilon Net and Geometric Hitting Set 2026 VLDB 4.9793485e-05
10,859 Pail: Efficient kNN Search on Set-Valued Attributes 2026 VLDB 4.9793485e-05
12,434 A Demonstration of AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data 2015 VLDB 4.9793485e-05
12,563 PLASMA-HD: Probing the LAttice Structure and MAkeup of High-dimensional Data 2013 VLDB 4.9793485e-05
12,713 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 4.9793485e-05
12,962 On Dominating Your Neighborhood Profitably 2007 VLDB 4.9793485e-05
13,051 Complex Spatio-Temporal Pattern Queries 2005 VLDB 4.9793485e-05
13,155 Analyzing Energy Behavior of Spatial Access Methods for Memory-Resident Data 2001 VLDB 4.9793485e-05
13,234 Algorithms for Querying by Spatial Structure 1998 VLDB 4.9793485e-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.001992968
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011405675
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00031645463
146 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00029061754
335 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00020660268
364 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00019976696
Previous Page 1 / 1 Next

Semantically Similar Papers

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