Reverse k Nearest Neighbors Query Processing: Experiments and Analysis

Summary: Comprehensive RkNN benchmark exposing misleading fixed I/O models and the importance of buffering, while fairly comparing prior algorithms across settings. A new filtering strategy accelerates TPL by up to 20× and halves its I/O cost. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hc4cccd911f57f1d5
Venue: VLDB
Year: 2015
Pagerank: 5.3322198e-05
Overall Rank: 8,487 | 42.94%
DOI: 10.14778/2735508.2735516

Incoming Non-self Citations Over Time

Authors

1. Shiyu Yang (University of New South Wales)
2. Muhammad Aamir Cheema (Monash University)
3. Xuemin Lin (University of New South Wales)
4. Wei Wang (University of New South Wales)

BibTeX Citation

@article{yang_vldb15,
        title = {{Reverse k Nearest Neighbors Query Processing: Experiments and Analysis}},
        author = {Yang, Shiyu and Cheema, Muhammad Aamir and Lin, Xuemin and Wang, Wei},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {6},
        pages = {605--616},
        doi = {10.14778/2735508.2735516},
        url = {https://doi.org/10.14778/2735508.2735516},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,895	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	5.6536466e-05
9,551	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.1591583e-05
10,762	RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
545	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016607433
1,237	Processing Queries By Linear Constraints	1997	PODS	0.00011396286
1,484	Query Processing Techniques for Solid State Drives	2009	SIGMOD	0.00010535051
1,571	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010201796
1,700	Discovery of Influence Sets in Frequently Updated Databases	2001	VLDB	9.8424892e-05
1,892	Efficient Computation of Reverse Skyline Queries	2007	VLDB	9.4166991e-05
5,342	FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data	2008	VLDB	6.1725496e-05
5,519	VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries	2010	VLDB	6.0968085e-05
5,914	Reverse Top-k Search using Random Walk with Restart	2014	VLDB	5.9490698e-05
6,108	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	5.8850424e-05
6,579	Parallel Computation of Skyline and Reverse Skyline Queries Using MapReduce	2013	VLDB	5.7446105e-05
7,941	Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN	2009	VLDB	5.4219572e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,108	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB
2	4,614	Branch-and-Bound Algorithm for Reverse Top-k Queries	2013	SIGMOD
3	1,477	Efficient Processing of Top-k Spatial Preference Queries	2011	VLDB
4	8,820	Spatial Queries with Two kNN Predicates	2012	VLDB
5	4,797	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD
6	12,754	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB
7	10,762	RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem	2026	VLDB
8	3,774	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
9	9,329	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB
10	1,571	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB