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 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.0004024707
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034749222
198 Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases 2001 SIGMOD 0.00025558119
282 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022250557
317 Shooting Stars in the Sky: An Online Algorithm for Skyline Queries 2002 VLDB 0.00021232519
449 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00018112854
490 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017397036
547 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016545689
578 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016079505
587 Efficient Algorithms for Mining Outliers from Large Data Sets 2000 SIGMOD 0.00015900873
598 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00015711108
616 Exact Indexing of Dynamic Time Warping 2002 VLDB 0.00015512487
640 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00015286314
681 Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases 2004 VLDB 0.00014792999
687 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00014736766
828 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.00013588099
832 Similarity-Based Queries for Time Series Data 1997 SIGMOD 0.00013562724
837 Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination 2020 SIGMOD 0.00013530806
843 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013501136
1,161 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00011733128
1,183 Simba: Efficient In-Memory Spatial Analytics 2016 SIGMOD 0.00011589152
1,298 Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials 2004 SIGMOD 0.00011104678
1,311 Continuous Nearest Neighbor Search 2002 VLDB 0.00011063629
1,412 A Model for the Prediction of R-tree Performance 1996 PODS 0.00010725178
1,445 LISA: A Learned Index Structure for Spatial Data 2020 SIGMOD 0.00010607118
1,524 LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index 2016 SIGMOD 0.0001033427
1,549 Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation 1997 SIGMOD 0.00010257684
1,554 Incremental Distance Join Algorithms for Spatial Databases 1998 SIGMOD 0.00010236406
1,574 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010164216
1,641 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 9.9814769e-05
1,660 Continuous Nearest Neighbor Monitoring in Road Networks 2006 VLDB 9.9414118e-05
1,661 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 9.9409992e-05
1,662 Indexing Land Surface for Efficient kNN Query 2008 VLDB 9.9409992e-05
1,729 Closest Pair Queries in Spatial Databases 2000 SIGMOD 9.761101e-05
1,741 A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects 2005 SIGMOD 9.7287344e-05
1,805 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.5936926e-05
1,825 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.5443954e-05
1,867 Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects 2009 VLDB 9.4581343e-05
1,884 Effectively Learning Spatial Indices 2020 VLDB 9.422145e-05
2,206 Monitoring Path Nearest Neighbor in Road Networks 2009 SIGMOD 8.850101e-05
2,262 Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring 2005 SIGMOD 8.7350282e-05
2,415 On Efficient Spatial Matching 2007 VLDB 8.4848606e-05
2,436 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB 8.4576934e-05
2,819 On Computing Top-t Most Influential Spatial Sites 2005 VLDB 7.953478e-05
2,838 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 7.9401525e-05
3,267 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.46539e-05
3,330 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 7.406702e-05
3,354 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.3666926e-05
3,529 Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates 2003 VLDB 7.2076747e-05
3,613 Location-Aware Type Ahead Search on Spatial Databases: Semantics and Efficiency 2011 SIGMOD 7.1431207e-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.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