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: hb045533afc30811b
Venue: SIGMOD
Year: 2006
Pagerank: 7.0277477e-05
Overall Rank: 3,774 | 74.63%
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,892	Efficient Computation of Reverse Skyline Queries	2007	VLDB	9.4166991e-05
2,406	On Efficient Spatial Matching	2007	VLDB	8.5169461e-05
4,797	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD	6.4113285e-05
5,342	FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data	2008	VLDB	6.1725496e-05
9,329	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB	5.1923126e-05
12,396	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	4.9793485e-05
12,713	K-Nearest Neighbor Search for Fuzzy Objects	2010	SIGMOD	4.9793485e-05
12,754	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	4.9793485e-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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040370171
90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00034860244
545	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016607433
1,571	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010201796

Semantically Similar Papers

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