Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases

Summary: Efficiently finds top-k probable nearest neighbors under a general uncertainty model for data and queries. Introduces new query semantics and fast methods to compute marginal NN probabilities; handles dependencies and threshold queries, with experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9679
Venue: VLDB
Year: 2008
Pagerank: 0.00011461371
Overall Rank: 1,535 | 89.34%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,509	Consensus Answers for Queries over Probabilistic Databases	2009	PODS	7.0283775e-05
4,072	Proximity Rank Join	2010	VLDB	6.4726748e-05
4,094	Ranking Continuous Probabilistic Datasets	2010	VLDB	6.4510938e-05
4,679	Adaptive Sampling for Rapidly Matching Histograms	2018	VLDB	5.9978792e-05
4,721	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	5.9647585e-05
5,763	Top-k Nearest Neighbor Search In Uncertain Data Series	2015	VLDB	5.3358283e-05
6,865	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	4.9002126e-05
7,080	Nearest Neighbor Searching Under Uncertainty II	2013	PODS	4.8353058e-05
7,300	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	4.7640746e-05
7,539	Boosting Spatial Pruning: On Optimal Pruning of MBRs	2010	SIGMOD	4.7116182e-05
8,883	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	4.4247207e-05
9,119	Hypersphere Dominance: An Optimal Approach	2014	SIGMOD	4.3881453e-05
9,167	Computing All Skyline Probabilities for Uncertain Data	2009	PODS	4.380727e-05
9,308	Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates	2015	SIGMOD	4.3544778e-05
9,433	A Generic Framework for Handling Uncertain Data with Local Correlations	2011	VLDB	4.3399748e-05
9,495	Spatial Data Quality in the IoT Era: Management and Exploitation	2022	SIGMOD	4.3300131e-05
11,832	Range-Max Queries on Uncertain Data	2016	PODS	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
48	Nearest Neighbor Queries	1995	SIGMOD	0.0006954126
78	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056385781
649	Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure	2001	SIGMOD	0.00018652362
903	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00015449454
1,093	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00014123221
1,568	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.0001131667

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,035	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.5111577e-05
4,370	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.2392118e-05
3,190	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD	7.413338e-05
5,763	Top-k Nearest Neighbor Search In Uncertain Data Series	2015	VLDB	5.3358283e-05
1,703	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010820803
1,159	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00013584223
9,365	Probabilistic Nearest Neighbor Queries on Uncertain Moving Object Trajectories	2014	VLDB	4.3468776e-05
7,080	Nearest Neighbor Searching Under Uncertainty II	2013	PODS	4.8353058e-05
6,865	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	4.9002126e-05
4,721	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	5.9647585e-05