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: h7bc227bf5e922386
Venue: SIGMOD
Year: 2009
Pagerank: 7.6445188e-05
Overall Rank: 3,105 | 79.13%
DOI: 10.1145/1559845.1559886

Incoming Non-self Citations Over Time

Authors

1. Tingjian Ge (Brown University)
2. Stan Zdonik (Brown University)
3. Samuel Madden (Massachusetts Institute of Technology)

BibTeX Citation

@inproceedings{ge_sigmod09,
        title = {{Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers}},
        author = {Ge, Tingjian and Zdonik, Stan and Madden, Samuel},
        series = {{SIGMOD} '09},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1559845.1559886},
        url = {https://dl.acm.org/doi/10.1145/1559845.1559886},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,063	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012208695
3,893	Ranking Continuous Probabilistic Datasets	2010	VLDB	6.940442e-05
6,065	k-Hit Query: Top-k Query with Probabilistic Utility Function	2015	SIGMOD	5.8978409e-05
6,176	Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings	2018	VLDB	5.8609559e-05
6,738	Efficiently Answering Durability Prediction Queries	2021	SIGMOD	5.6918011e-05
9,214	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	5.2058816e-05
11,100	A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores	2025	SIGMOD	4.9793485e-05
12,322	Range-Max Queries on Uncertain Data	2016	PODS	4.9793485e-05
12,657	Schema-As-You-Go: On Probabilistic Tagging and Querying of Wide Tables	2011	SIGMOD	4.9793485e-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
51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00042936299
126	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.00030439683
245	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00023258672
370	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.00019846702
587	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00015933201
1,396	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.0001079253
2,709	Comparing and Aggregating Rankings with Ties	2004	PODS	8.1063128e-05
3,326	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	7.4227632e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	715	Data Integration with Uncertainty	2007	VLDB
2	1,535	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB
3	8,514	URank: Formulation and Efficient Evaluation of Top-k Queries in Uncertain Databases	2007	SIGMOD
4	9,374	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB
5	6,176	Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings	2018	VLDB
6	1,635	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
7	11,100	A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores	2025	SIGMOD
8	2,620	Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures	2011	SIGMOD
9	3,326	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB
10	1,396	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD