Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers

Summary: Top-k queries on uncertain data; expose the score distribution of top-k vectors to balance score and probability. Proposes algorithms to compute a compact set of representative vectors from distribution and extends to score ties, with empirical study. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4133
Venue: SIGMOD
Year: 2009
Pagerank: 7.4192604e-05
Overall Rank: 3,185 | 77.85%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,162	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.0001358105
4,095	Ranking Continuous Probabilistic Datasets	2010	VLDB	6.4556768e-05
6,387	Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings	2018	VLDB	5.0851965e-05
6,391	k-Hit Query: Top-k Query with Probabilistic Utility Function	2015	SIGMOD	5.0842079e-05
6,960	Efficiently Answering Durability Prediction Queries	2021	SIGMOD	4.8849367e-05
8,882	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	4.4289641e-05
10,364	A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores	2025	SIGMOD	4.1945683e-05
11,824	Range-Max Queries on Uncertain Data	2016	PODS	4.1945683e-05
12,170	Schema-As-You-Go: On Probabilistic Tagging and Querying of Wide Tables	2011	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057857292
149	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.00041101118
321	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00027527389
467	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.00022443768
627	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00018959005
1,707	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010816111
2,385	Comparing and Aggregating Rankings with Ties	2004	PODS	8.9247846e-05
4,080	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	6.4652983e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
721	Data Integration with Uncertainty	2007	VLDB	0.00017570539
1,808	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010486213
8,372	URank: Formulation and Efficient Evaluation of Top-k Queries in Uncertain Databases	2007	SIGMOD	4.532996e-05
9,044	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB	4.4039656e-05
6,387	Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings	2018	VLDB	5.0851965e-05
1,542	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011456321
10,364	A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores	2025	SIGMOD	4.1945683e-05
3,014	Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures	2011	SIGMOD	7.70946e-05
4,080	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	6.4652983e-05
1,707	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010816111