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.00051292389
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.00040363819
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034847854
194 Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases 2001 SIGMOD 0.00025637823
281 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022303081
313 Shooting Stars in the Sky: An Online Algorithm for Skyline Queries 2002 VLDB 0.00021301023
447 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00018151383
488 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017451091
545 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016599925
576 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016118297
583 Efficient Algorithms for Mining Outliers from Large Data Sets 2000 SIGMOD 0.00015952617
597 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00015759877
614 Exact Indexing of Dynamic Time Warping 2002 VLDB 0.00015563362
638 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00015331662
678 Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases 2004 VLDB 0.00014836541
686 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00014769852
826 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.000136317
829 Similarity-Based Queries for Time Series Data 1997 SIGMOD 0.0001360545
838 Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination 2020 SIGMOD 0.0001355054
839 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.0001354488
1,157 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.0001176973
1,178 Simba: Efficient In-Memory Spatial Analytics 2016 SIGMOD 0.00011627256
1,294 Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials 2004 SIGMOD 0.00011140565
1,304 Continuous Nearest Neighbor Search 2002 VLDB 0.00011099525
1,405 A Model for the Prediction of R-tree Performance 1996 PODS 0.00010759378
1,440 LISA: A Learned Index Structure for Spatial Data 2020 SIGMOD 0.00010638444
1,527 LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index 2016 SIGMOD 0.00010350688
1,547 Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation 1997 SIGMOD 0.00010289422
1,552 Incremental Distance Join Algorithms for Spatial Databases 1998 SIGMOD 0.00010270215
1,571 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010197322
1,635 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 0.00010012676
1,650 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 9.9739794e-05
1,651 Indexing Land Surface for Efficient kNN Query 2008 VLDB 9.9739794e-05
1,652 Continuous Nearest Neighbor Monitoring in Road Networks 2006 VLDB 9.973647e-05
1,721 Closest Pair Queries in Spatial Databases 2000 SIGMOD 9.792994e-05
1,733 A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects 2005 SIGMOD 9.7608733e-05
1,793 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.6212318e-05
1,814 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.5757565e-05
1,858 Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects 2009 VLDB 9.4893333e-05
1,877 Effectively Learning Spatial Indices 2020 VLDB 9.4498401e-05
2,196 Monitoring Path Nearest Neighbor in Road Networks 2009 SIGMOD 8.8763791e-05
2,244 Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring 2005 SIGMOD 8.7637082e-05
2,407 On Efficient Spatial Matching 2007 VLDB 8.5129142e-05
2,422 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB 8.4857212e-05
2,807 On Computing Top-t Most Influential Spatial Sites 2005 VLDB 7.9798533e-05
2,827 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 7.9637452e-05
3,254 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.487573e-05
3,322 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 7.4261592e-05
3,346 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.3899839e-05
3,522 Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates 2003 VLDB 7.2315814e-05
3,605 Location-Aware Type Ahead Search on Spatial Databases: Semantics and Efficiency 2011 SIGMOD 7.1667859e-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.0019923528
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011402175
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00031633451
146 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00029048509
336 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00020652147
363 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00019980483
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 6,109 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,659 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD
4 3,776 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD
5 12,760 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,799 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,721 Closest Pair Queries in Spatial Databases 2000 SIGMOD