RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem

Summary: Recasts 2D reverse kNN as graphics ray casting, modeling users as rays and facilities as geometric primitives rather than relying on R-tree pruning. A GPU implementation exploiting dedicated ray-tracing cores remains effective for large k, dense users, and sparse facilities. (summarized by gpt-5.6-luna on Aug 17 2026)

Paper ID: ha210cc872b12e4f6
Venue: VLDB
Year: 2026
Pagerank: 4.9793485e-05
Overall Rank: 10,762 | 27.65%
DOI: 10.14778/3819518.3819527

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Zhengyang Bai (RIKEN Center for Computational Science)
2. Peng Chen (RIKEN Center for Computational Science)
3. Mohamed Wahib (RIKEN Center for Computational Science)

BibTeX Citation

@article{bai_vldb26,
        title = {{RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem}},
        author = {Bai, Zhengyang and Chen, Peng and Wahib, Mohamed},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {9},
        pages = {1963--1976},
        doi = {10.14778/3819518.3819527},
        url = {https://doi.org/10.14778/3819518.3819527},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 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
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
3,029	Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor	2009	VLDB	7.737708e-05
3,689	RTIndex: Exploiting Hardware-Accelerated GPU Raytracing for Database Indexing	2023	VLDB	7.0943075e-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
6,108	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	5.8850424e-05
6,444	RTScan: Efficient Scan with Ray Tracing Cores	2024	VLDB	5.7825648e-05
6,830	Maximizing Bichromatic Reverse Spatial and Textual k Nearest Neighbor Queries	2016	VLDB	5.6691409e-05
7,941	Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN	2009	VLDB	5.4219572e-05
8,487	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	5.3322198e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,806	On Computing Top-t Most Influential Spatial Sites	2005	VLDB
2	6,108	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB
3	545	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD
4	9,329	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB
5	12,754	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB
6	28	Nearest Neighbor Queries	1995	SIGMOD
7	4,797	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD
8	3,774	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
9	1,571	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB
10	8,487	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB