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: 9869
Venue: VLDB
Year: 2008
Pagerank: 0.00010229844
Overall Rank: 1,605 | 88.99%
DOI: 10.14778/1453856.1453895

Incoming Non-self Citations Over Time

Authors

1. George Beskales (University of Waterloo)
2. Mohamed A. Soliman (University of Waterloo)
3. Ihab F. Ilyas (University of Waterloo)

BibTeX Citation

@article{beskales_vldb08,
        title = {{Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases}},
        author = {Beskales, George and Soliman, Mohamed A. and Ilyas, Ihab F.},
        journal = {PVLDB},
        series = {{VLDB} '08},
        volume = {1},
        number = {1},
        pages = {326--337},
        doi = {10.14778/1453856.1453895},
        url = {https://doi.org/10.14778/1453856.1453895},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,483	Consensus Answers for Queries over Probabilistic Databases	2009	PODS	7.372823e-05
3,823	Ranking Continuous Probabilistic Datasets	2010	VLDB	7.092508e-05
4,850	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	6.480347e-05
4,926	Adaptive Sampling for Rapidly Matching Histograms	2018	VLDB	6.4428362e-05
5,244	Top-k Nearest Neighbor Search In Uncertain Data Series	2015	VLDB	6.3018164e-05
5,640	Proximity Rank Join	2010	VLDB	6.1384844e-05
6,561	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	5.8389373e-05
7,025	Nearest Neighbor Searching Under Uncertainty II	2013	PODS	5.7234179e-05
7,350	Boosting Spatial Pruning: On Optimal Pruning of MBRs	2010	SIGMOD	5.6358517e-05
7,463	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	5.6111155e-05
8,435	Spatial Data Quality in the IoT Era: Management and Exploitation	2022	SIGMOD	5.4253644e-05
9,044	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	5.3253644e-05
9,261	Hypersphere Dominance: An Optimal Approach	2014	SIGMOD	5.2968259e-05
9,323	Computing All Skyline Probabilities for Uncertain Data	2009	PODS	5.289545e-05
9,355	Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates	2015	SIGMOD	5.282937e-05
9,581	A Generic Framework for Handling Uncertain Data with Local Correlations	2011	VLDB	5.2528121e-05
12,027	Range-Max Queries on Uncertain Data	2016	PODS	5.093636e-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
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
28	Nearest Neighbor Queries	1995	SIGMOD	0.00052102434
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044853085
648	Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure	2001	SIGMOD	0.00015324657
827	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00013769938
828	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00013769869
1,486	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00010625076

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
2	4,112	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB
3	3,049	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD
4	5,244	Top-k Nearest Neighbor Search In Uncertain Data Series	2015	VLDB
5	1,363	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD
6	1,049	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB
7	9,431	Probabilistic Nearest Neighbor Queries on Uncertain Moving Object Trajectories	2014	VLDB
8	7,025	Nearest Neighbor Searching Under Uncertainty II	2013	PODS
9	6,561	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB
10	4,850	Nearest-Neighbor Searching Under Uncertainty	2012	PODS