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: 3778
Venue: SIGMOD
Year: 2006
Pagerank: 6.4784181e-05
Overall Rank: 4,070 | 71.69%
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,247	On Efficient Spatial Matching	2007	VLDB	9.2048219e-05
2,454	Efficient Computation of Reverse Skyline Queries	2007	VLDB	8.778281e-05
4,960	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD	5.7987607e-05
6,045	FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data	2008	VLDB	5.2372658e-05
9,025	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB	4.4072367e-05
11,904	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	4.1945683e-05
12,227	K-Nearest Neighbor Search for Fuzzy Objects	2010	SIGMOD	4.1945683e-05
12,268	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	4.1945683e-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.0032169493
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.0005181666
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.0004429571
601	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019375875
1,933	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010038508

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
802	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00016502317
8,425	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD	4.5163161e-05
1,542	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011456321
709	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017768547
6,946	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	4.8909775e-05
10,165	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1945683e-05
3,579	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	6.9502303e-05
12,268	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	4.1945683e-05
9,025	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB	4.4072367e-05
1,933	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010038508