Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data

Summary: Proposes efficient probabilistic reverse nearest neighbor (PRNN) processing on uncertain data, using distance-dependency aware pruning to bound probabilities and prune candidates. Demonstrates strong empirical gains and extends to PRkNN (k>1). (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10294
Venue: VLDB
Year: 2011
Pagerank: 4.8909775e-05
Overall Rank: 6,946 | 51.68%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,087	Similarity Search and Mining in Uncertain Databases	2010	VLDB	4.5899317e-05
9,121	Hypersphere Dominance: An Optimal Approach	2014	SIGMOD	4.3922853e-05
9,309	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	4.3571035e-05
9,494	Spatial Data Quality in the IoT Era: Management and Exploitation	2022	SIGMOD	4.3341665e-05
11,904	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	4.1945683e-05

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.0032169493
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
299	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00028525071
601	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019375875
827	On the Representation and Querying of Sets of Possible Worlds	1987	SIGMOD	0.00016220185
1,179	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00013457451
1,542	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011456321
1,609	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011150935
1,933	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010038508
2,331	Orion 2.0: Native Support for Uncertain Data	2008	SIGMOD	9.018559e-05
3,505	Consensus Answers for Queries over Probabilistic Databases	2009	PODS	7.0337815e-05
4,095	Ranking Continuous Probabilistic Datasets	2010	VLDB	6.4556768e-05
7,540	Boosting Spatial Pruning: On Optimal Pruning of MBRs	2010	SIGMOD	4.7159549e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
601	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019375875
7,084	Nearest Neighbor Searching Under Uncertainty II	2013	PODS	4.839879e-05
9,025	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB	4.4072367e-05
12,268	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	4.1945683e-05
1,162	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.0001358105
1,933	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010038508
9,358	Probabilistic Nearest Neighbor Queries on Uncertain Moving Object Trajectories	2014	VLDB	4.3510473e-05
4,070	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.4784181e-05
4,724	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	5.9697823e-05
1,542	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011456321