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.640909e-05
Overall Rank: 3,107 | 79.12%
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,064	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012202916
3,893	Ranking Continuous Probabilistic Datasets	2010	VLDB	6.9371894e-05
6,066	k-Hit Query: Top-k Query with Probabilistic Utility Function	2015	SIGMOD	5.8950525e-05
6,178	Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings	2018	VLDB	5.8581814e-05
6,743	Efficiently Answering Durability Prediction Queries	2021	SIGMOD	5.6892637e-05
9,224	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	5.2034204e-05
11,109	A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores	2025	SIGMOD	4.9769913e-05
12,328	Range-Max Queries on Uncertain Data	2016	PODS	4.9769913e-05
12,663	Schema-As-You-Go: On Probabilistic Tagging and Querying of Wide Tables	2011	SIGMOD	4.9769913e-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.00042926566
126	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.00030430114
245	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00023251151
370	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.00019837998
587	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00015927027
1,397	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010787659
2,710	Comparing and Aggregating Rankings with Ties	2004	PODS	8.1024763e-05
3,328	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	7.4194442e-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,520	URank: Formulation and Efficient Evaluation of Top-k Queries in Uncertain Databases	2007	SIGMOD
4	9,383	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB
5	6,178	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,109	A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores	2025	SIGMOD
8	2,621	Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures	2011	SIGMOD
9	3,328	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB
10	1,397	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD