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: 3840
Venue: SIGMOD
Year: 2006
Pagerank: 7.1780127e-05
Overall Rank: 3,710 | 74.55%
DOI: 10.1145/1142473.1142531

Incoming Non-self Citations Over Time

Authors

1. Elke Achtert (University of Munich)
2. Christian Bohm (University of Munich)
3. Peer Kroeger (University of Munich)
4. Peter Kunath (University of Munich)
5. Alexey Pryakhin (University of Munich)
6. Matthias Renz (University of Munich)

BibTeX Citation

@inproceedings{achtert_sigmod06,
        title = {{Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces}},
        author = {Achtert, Elke and Bohm, Christian and Kroeger, Peer and Kunath, Peter and Pryakhin, Alexey and Renz, Matthias},
        series = {{SIGMOD} '06},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1142473.1142531},
        url = {https://dl.acm.org/doi/10.1145/1142473.1142531},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,847	Efficient Computation of Reverse Skyline Queries	2007	VLDB	9.6252055e-05
2,349	On Efficient Spatial Matching	2007	VLDB	8.7115756e-05
4,711	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD	6.5506926e-05
5,664	FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data	2008	VLDB	6.1289238e-05
9,165	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB	5.3101672e-05
12,103	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	5.093636e-05
12,422	K-Nearest Neighbor Search for Fuzzy Objects	2010	SIGMOD	5.093636e-05
12,463	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	5.093636e-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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040719947
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
546	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016734556
1,612	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010218134

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	796	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD
2	7,259	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD
3	1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
4	690	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD
5	6,561	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB
6	10,454	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
7	3,363	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD
8	12,463	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB
9	9,165	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB
10	1,612	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB