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

Rank Citing Paper Year Venue Pagerank
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040719947
85 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00035405879
190 Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases 2001 SIGMOD 0.00026105472
277 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022537944
308 Shooting Stars in the Sky: An Online Algorithm for Skyline Queries 2002 VLDB 0.00021787597
433 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00018532516
483 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017756569
546 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016734556
578 Efficient Algorithms for Mining Outliers from Large Data Sets 2000 SIGMOD 0.00016221871
581 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016153395
592 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00016029789
601 Exact Indexing of Dynamic Time Warping 2002 VLDB 0.00015870156
623 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00015684963
665 Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases 2004 VLDB 0.00015167291
675 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00015080025
796 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.00013932561
810 Similarity-Based Queries for Time Series Data 1997 SIGMOD 0.00013874464
815 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013835761
926 Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination 2020 SIGMOD 0.00013181732
1,137 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00012027131
1,175 Simba: Efficient In-Memory Spatial Analytics 2016 SIGMOD 0.00011812263
1,280 Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials 2004 SIGMOD 0.00011354776
1,281 Continuous Nearest Neighbor Search 2002 VLDB 0.00011349245
1,373 A Model for the Prediction of R-tree Performance 1996 PODS 0.0001098638
1,418 LISA: A Learned Index Structure for Spatial Data 2020 SIGMOD 0.00010835539
1,517 Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation 1997 SIGMOD 0.00010520118
1,525 Incremental Distance Join Algorithms for Spatial Databases 1998 SIGMOD 0.00010493702
1,572 LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index 2016 SIGMOD 0.00010329197
1,605 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 0.00010229844
1,612 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010218134
1,618 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 0.00010207737
1,619 Indexing Land Surface for Efficient kNN Query 2008 VLDB 0.00010207737
1,620 Continuous Nearest Neighbor Monitoring in Road Networks 2006 VLDB 0.00010206305
1,685 Closest Pair Queries in Spatial Databases 2000 SIGMOD 0.00010017073
1,698 A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects 2005 SIGMOD 9.980335e-05
1,776 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.7853414e-05
1,778 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.7769047e-05
1,819 Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects 2009 VLDB 9.6810907e-05
1,840 Effectively Learning Spatial Indices 2020 VLDB 9.6404567e-05
2,153 Monitoring Path Nearest Neighbor in Road Networks 2009 SIGMOD 9.0762376e-05
2,205 Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring 2005 SIGMOD 8.9591376e-05
2,349 On Efficient Spatial Matching 2007 VLDB 8.7115756e-05
2,375 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB 8.6753909e-05
2,761 On Computing Top-t Most Influential Spatial Sites 2005 VLDB 8.154319e-05
2,774 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 8.1372328e-05
3,217 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.6314544e-05
3,290 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.5531472e-05
3,363 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 7.4808966e-05
3,462 Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates 2003 VLDB 7.3922569e-05
3,534 Location-Aware Type Ahead Search on Spatial Databases: Semantics and Efficiency 2011 SIGMOD 7.3347488e-05
Previous Page 1 / 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