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: 10295
Venue: VLDB
Year: 2011
Pagerank: 4.9002126e-05
Overall Rank: 6,865 | 52.29%
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,084	Similarity Search and Mining in Uncertain Databases	2010	VLDB	4.5861412e-05
9,119	Hypersphere Dominance: An Optimal Approach	2014	SIGMOD	4.3881453e-05
9,309	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	4.3544778e-05
9,495	Spatial Data Quality in the IoT Era: Management and Exploitation	2022	SIGMOD	4.3300131e-05
11,912	Indexing Metric Uncertain Data for Range Queries	2015	SIGMOD	4.1905499e-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.0032118946
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
300	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00028503742
595	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019459302
823	On the Representation and Querying of Sets of Possible Worlds	1987	SIGMOD	0.00016225326
1,181	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00013447487
1,535	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011461371
1,612	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011142757
1,924	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010075677
2,334	Orion 2.0: Native Support for Uncertain Data	2008	SIGMOD	9.01132e-05
3,509	Consensus Answers for Queries over Probabilistic Databases	2009	PODS	7.0283775e-05
4,094	Ranking Continuous Probabilistic Datasets	2010	VLDB	6.4510938e-05
7,539	Boosting Spatial Pruning: On Optimal Pruning of MBRs	2010	SIGMOD	4.7116182e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
595	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019459302
7,080	Nearest Neighbor Searching Under Uncertainty II	2013	PODS	4.8353058e-05
9,026	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB	4.4030177e-05
1,159	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00013584223
12,276	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	4.1905499e-05
1,924	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010075677
9,365	Probabilistic Nearest Neighbor Queries on Uncertain Moving Object Trajectories	2014	VLDB	4.3468776e-05
4,035	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.5111577e-05
4,721	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	5.9647585e-05
1,535	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011461371