Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces

Summary: First approach for efficient reverse k-nearest neighbor search in arbitrary metric spaces with k specified at query time. Leverages existing metric indexes with conservative and progressive distance bounds using two-parameter upper/lower functions, no extra storage, and shows scalable real-world performance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3779
Venue: SIGMOD
Year: 2006
Pagerank: 6.5111577e-05
Overall Rank: 4,035 | 71.96%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,248	On Efficient Spatial Matching	2007	VLDB	9.1958821e-05
2,450	Efficient Computation of Reverse Skyline Queries	2007	VLDB	8.7855268e-05
4,880	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD	5.8526687e-05
5,922	FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data	2008	VLDB	5.2678889e-05
9,026	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB	4.4030177e-05
11,912	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	4.1905499e-05
12,235	K-Nearest Neighbor Search for Fuzzy Objects	2010	SIGMOD	4.1905499e-05
12,276	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	4.1905499e-05

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.0032118946
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
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
595	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019459302
1,924	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010075677

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
798	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00016484637
8,419	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD	4.5119865e-05
1,535	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011461371
710	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017727016
6,865	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	4.9002126e-05
10,165	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1905499e-05
3,574	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	6.9520978e-05
12,276	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	4.1905499e-05
9,026	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB	4.4030177e-05
1,924	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010075677