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: 2790
Venue: SIGMOD
Year: 1995
Pagerank: 0.0006954126
Overall Rank: 48 | 99.67%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 96 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00051785122
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00044255276
195	Optimizing Queries over Multimedia Repositories	1996	SIGMOD	0.00035317524
243	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.00031052437
301	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028396714
386	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00024740283
434	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00023277433
471	FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets	1995	SIGMOD	0.00022348285
574	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.0001987713
595	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019459302
597	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00019450818
665	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00018437125
675	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018304179
696	Exact Indexing of Dynamic Time Warping	2002	VLDB	0.00017991162
697	Efficient Algorithms for Mining Outliers from Large Data Sets	2000	SIGMOD	0.00017964755
746	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00017212135
798	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00016484637
862	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00015798065
999	Similarity-Based Queries for Time Series Data	1997	SIGMOD	0.00014726031
1,180	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00013455619
1,272	Continuous Nearest Neighbor Search	2002	VLDB	0.00012871443
1,301	Simba: Efficient In-Memory Spatial Analytics	2016	SIGMOD	0.00012702767
1,347	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00012463441
1,373	Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials	2004	SIGMOD	0.00012326961
1,511	Continuous Monitoring of Nearest Neighbors on Land Surface	2009	VLDB	0.00011582099
1,512	Indexing Land Surface for Efficient kNN Query	2008	VLDB	0.00011582099
1,519	A Model for the Prediction of R-tree Performance	1996	PODS	0.00011535609
1,535	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011461371
1,545	Monitoring Path Nearest Neighbor in Road Networks	2009	SIGMOD	0.00011428609
1,580	Continuous Nearest Neighbor Monitoring in Road Networks	2006	VLDB	0.00011272266
1,605	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011180126
1,755	Efficient User-Adaptable Similarity Search in Large Multimedia Databases	1997	VLDB	0.00010661725
1,769	Closest Pair Queries in Spatial Databases	2000	SIGMOD	0.00010608375
1,916	A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects	2005	SIGMOD	0.00010110473
1,923	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	0.00010079134
1,924	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010075677
1,966	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	9.9130791e-05
2,020	Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects	2009	VLDB	9.7766925e-05
2,108	LISA: A Learned Index Structure for Spatial Data	2020	SIGMOD	9.5283642e-05
2,248	On Efficient Spatial Matching	2007	VLDB	9.1958821e-05
2,342	Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring	2005	SIGMOD	9.0005088e-05
2,558	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.5441554e-05
2,676	Effectively Learning Spatial Indices	2020	VLDB	8.326321e-05
2,696	On Computing Top-t Most Influential Spatial Sites	2005	VLDB	8.279376e-05
2,978	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	7.7848117e-05
3,111	Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees	1995	SIGMOD	7.5445257e-05
3,278	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD	7.2858181e-05
3,415	Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates	2003	VLDB	7.1162894e-05
3,549	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD	6.9792126e-05
3,561	Location-Aware Type Ahead Search on Spatial Databases: Semantics and Efficiency	2011	SIGMOD	6.9693906e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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.0032118946
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
56	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00065500256
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
290	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00028845557
356	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00026091196

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,865	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	4.9002126e-05
1,512	Indexing Land Surface for Efficient kNN Query	2008	VLDB	0.00011582099
3,802	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD	6.7524078e-05
4,035	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.5111577e-05
12,276	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	4.1905499e-05
5,917	VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries	2010	VLDB	5.2690256e-05
434	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00023277433
4,880	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD	5.8526687e-05
1,535	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011461371
1,769	Closest Pair Queries in Spatial Databases	2000	SIGMOD	0.00010608375