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.0244572e-05
Overall Rank: 3,776 | 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,895	Efficient Computation of Reverse Skyline Queries	2007	VLDB	9.4125147e-05
2,407	On Efficient Spatial Matching	2007	VLDB	8.5129142e-05
4,799	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD	6.4084993e-05
5,348	FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data	2008	VLDB	6.1698901e-05
9,338	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB	5.1898547e-05
12,402	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	4.9769913e-05
12,719	K-Nearest Neighbor Search for Fuzzy Objects	2010	SIGMOD	4.9769913e-05
12,760	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	4.9769913e-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.0019923528
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011402175
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040363819
90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00034847854
545	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016599925
1,571	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010197322

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	826	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD
2	6,461	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,109	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB
6	10,333	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
7	3,322	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD
8	12,760	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB
9	9,338	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB
10	1,571	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB