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

Rank Citing Paper Year Venue Pagerank
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040370171
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034860244
193 Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases 2001 SIGMOD 0.00025648171
279 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022308048
313 Shooting Stars in the Sky: An Online Algorithm for Skyline Queries 2002 VLDB 0.00021311041
447 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00018159715
488 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017457851
545 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016607433
576 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016121388
583 Efficient Algorithms for Mining Outliers from Large Data Sets 2000 SIGMOD 0.00015960125
597 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00015766567
613 Exact Indexing of Dynamic Time Warping 2002 VLDB 0.00015570505
638 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00015338893
677 Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases 2004 VLDB 0.00014843441
686 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00014775707
826 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.0001363793
829 Similarity-Based Queries for Time Series Data 1997 SIGMOD 0.00013611445
837 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013551047
839 Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination 2020 SIGMOD 0.00013547412
1,157 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00011774968
1,178 Simba: Efficient In-Memory Spatial Analytics 2016 SIGMOD 0.00011632691
1,294 Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials 2004 SIGMOD 0.00011145111
1,304 Continuous Nearest Neighbor Search 2002 VLDB 0.00011104243
1,405 A Model for the Prediction of R-tree Performance 1996 PODS 0.0001076417
1,446 LISA: A Learned Index Structure for Spatial Data 2020 SIGMOD 0.00010629222
1,530 LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index 2016 SIGMOD 0.00010344205
1,546 Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation 1997 SIGMOD 0.00010294163
1,552 Incremental Distance Join Algorithms for Spatial Databases 1998 SIGMOD 0.00010275036
1,571 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010201796
1,635 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 0.00010017067
1,650 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 9.9787032e-05
1,651 Indexing Land Surface for Efficient kNN Query 2008 VLDB 9.9787032e-05
1,652 Continuous Nearest Neighbor Monitoring in Road Networks 2006 VLDB 9.9778734e-05
1,719 Closest Pair Queries in Spatial Databases 2000 SIGMOD 9.7976056e-05
1,730 A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects 2005 SIGMOD 9.7654336e-05
1,793 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.6235776e-05
1,813 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.5801503e-05
1,856 Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects 2009 VLDB 9.4938262e-05
1,878 Effectively Learning Spatial Indices 2020 VLDB 9.4451309e-05
2,194 Monitoring Path Nearest Neighbor in Road Networks 2009 SIGMOD 8.8805644e-05
2,243 Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring 2005 SIGMOD 8.7678247e-05
2,406 On Efficient Spatial Matching 2007 VLDB 8.5169461e-05
2,421 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB 8.4897323e-05
2,806 On Computing Top-t Most Influential Spatial Sites 2005 VLDB 7.9836326e-05
2,827 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 7.967335e-05
3,253 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.4900624e-05
3,325 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 7.4271038e-05
3,347 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.3933163e-05
3,522 Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates 2003 VLDB 7.2350043e-05
3,605 Location-Aware Type Ahead Search on Spatial Databases: Semantics and Efficiency 2011 SIGMOD 7.1701802e-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.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