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.00051134355
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,646 Location-based Spatial Queries 2003 SIGMOD 7.1177166e-05
3,666 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 7.0975312e-05
3,893 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9232481e-05
4,375 Searching Trajectories by Locations - An Efficiency Study 2010 SIGMOD 6.6172049e-05
4,821 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 6.3876508e-05
4,879 The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data 2023 SIGMOD 6.3567479e-05
4,954 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.3263552e-05
5,084 The V*-Diagram: A Query-Dependent Approach to Moving KNN Queries 2008 VLDB 6.2674446e-05
5,360 FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data 2008 VLDB 6.1498141e-05
5,537 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB 6.075858e-05
5,547 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 6.0715188e-05
5,554 AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data 2015 VLDB 6.0707181e-05
5,668 Scalable Ranked Publish/Subscribe 2008 VLDB 6.0272577e-05
5,737 Ranked Subsequence Matching in Time-Series Databases 2007 VLDB 5.9955855e-05
5,970 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.9116326e-05
6,040 Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search 2002 SIGMOD 5.8900832e-05
6,552 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.7306642e-05
6,760 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.6706378e-05
6,811 An Incremental Hausdorff Distance Calculation Algorithm 2011 VLDB 5.6598101e-05
6,885 Flexible Aggregate Similarity Search 2011 SIGMOD 5.6402295e-05
7,045 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 5.5975731e-05
7,306 Continuous Obstructed Nearest Neighbor Queries in Spatial Databases 2009 SIGMOD 5.5452852e-05
7,519 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 5.4892692e-05
7,775 Uncertain Time-Series Similarity: Return to the Basics 2012 VLDB 5.4386818e-05
8,391 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.3248747e-05
8,592 Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation 2001 VLDB 5.2936565e-05
8,783 Maintenance of Spatial Semijoin Queries on Moving Points 2004 VLDB 5.2645572e-05
8,847 Spatial Queries with Two kNN Predicates 2012 VLDB 5.2495672e-05
8,981 Adaptive Location Constraint Processing 2007 SIGMOD 5.2326057e-05
9,289 Processing Moving kNN Queries Using Influential Neighbor Sets 2015 VLDB 5.1860131e-05
9,321 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 5.1825641e-05
9,440 Indexing Medium-dimensionality Data in Oracle 1999 SIGMOD 5.163285e-05
9,465 Hypersphere Dominance: An Optimal Approach 2014 SIGMOD 5.1590473e-05
9,631 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.1362663e-05
9,794 A Generic Framework for Handling Uncertain Data with Local Correlations 2011 VLDB 5.115551e-05
10,140 Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations 2025 PODS 5.0597449e-05
10,180 Distance-Based Outlier Detection: Consolidation and Renewed Bearing 2010 VLDB 5.0555297e-05
10,358 WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search 2026 SIGMOD 5.0156513e-05
10,767 On Fair Epsilon Net and Geometric Hitting Set 2026 VLDB 4.9605343e-05
10,929 Pail: Efficient kNN Search on Set-Valued Attributes 2026 VLDB 4.9605343e-05
12,483 A Demonstration of AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data 2015 VLDB 4.9605343e-05
12,612 PLASMA-HD: Probing the LAttice Structure and MAkeup of High-dimensional Data 2013 VLDB 4.9605343e-05
12,762 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 4.9605343e-05
13,010 On Dominating Your Neighborhood Profitably 2007 VLDB 4.9605343e-05
13,098 Complex Spatio-Temporal Pattern Queries 2005 VLDB 4.9605343e-05
13,202 Analyzing Energy Behavior of Spatial Access Methods for Memory-Resident Data 2001 VLDB 4.9605343e-05
13,281 Algorithms for Querying by Spatial Structure 1998 VLDB 4.9605343e-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.0019892478
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011386412
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00031562001
146 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.000289618
338 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.0002058961
363 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00019931086
Previous Page 1 / 1 Next

Semantically Similar Papers

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