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: 9678
Venue: VLDB
Year: 2008
Pagerank: 0.00011456321
Overall Rank: 1,542 | 89.28%
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,505	Consensus Answers for Queries over Probabilistic Databases	2009	PODS	7.0337815e-05
4,069	Proximity Rank Join	2010	VLDB	6.4789031e-05
4,095	Ranking Continuous Probabilistic Datasets	2010	VLDB	6.4556768e-05
4,681	Adaptive Sampling for Rapidly Matching Histograms	2018	VLDB	6.0034918e-05
4,724	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	5.9697823e-05
5,758	Top-k Nearest Neighbor Search In Uncertain Data Series	2015	VLDB	5.339397e-05
6,946	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	4.8909775e-05
7,084	Nearest Neighbor Searching Under Uncertainty II	2013	PODS	4.839879e-05
7,365	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	4.7517889e-05
7,540	Boosting Spatial Pruning: On Optimal Pruning of MBRs	2010	SIGMOD	4.7159549e-05
8,882	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	4.4289641e-05
9,121	Hypersphere Dominance: An Optimal Approach	2014	SIGMOD	4.3922853e-05
9,165	Computing All Skyline Probabilities for Uncertain Data	2009	PODS	4.3849295e-05
9,308	Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates	2015	SIGMOD	4.3571035e-05
9,427	A Generic Framework for Handling Uncertain Data with Local Correlations	2011	VLDB	4.3441378e-05
9,494	Spatial Data Quality in the IoT Era: Management and Exploitation	2022	SIGMOD	4.3341665e-05
11,824	Range-Max Queries on Uncertain Data	2016	PODS	4.1945683e-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
7	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015496097
47	Nearest Neighbor Queries	1995	SIGMOD	0.0007015885
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144
647	Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure	2001	SIGMOD	0.00018668224
905	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.0001546195
1,096	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00014120512
1,586	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00011250856

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,070	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.4784181e-05
4,373	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.2443809e-05
3,185	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD	7.4192604e-05
5,758	Top-k Nearest Neighbor Search In Uncertain Data Series	2015	VLDB	5.339397e-05
1,707	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010816111
1,162	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.0001358105
9,358	Probabilistic Nearest Neighbor Queries on Uncertain Moving Object Trajectories	2014	VLDB	4.3510473e-05
7,084	Nearest Neighbor Searching Under Uncertainty II	2013	PODS	4.839879e-05
6,946	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	4.8909775e-05
4,724	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	5.9697823e-05