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: 4195
Venue: SIGMOD
Year: 2009
Pagerank: 7.8151597e-05
Overall Rank: 3,049 | 79.09%
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,049	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012415522
3,823	Ranking Continuous Probabilistic Datasets	2010	VLDB	7.092508e-05
5,944	k-Hit Query: Top-k Query with Probabilistic Utility Function	2015	SIGMOD	6.0328749e-05
6,052	Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings	2018	VLDB	5.9941393e-05
6,761	Efficiently Answering Durability Prediction Queries	2021	SIGMOD	5.7822533e-05
9,044	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	5.3253644e-05
10,657	A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores	2025	SIGMOD	5.093636e-05
12,027	Range-Max Queries on Uncertain Data	2016	PODS	5.093636e-05
12,366	Schema-As-You-Go: On Probabilistic Tagging and Querying of Wide Tables	2011	SIGMOD	5.093636e-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
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
125	Trio: A System for Integrated Management of Data, Accuracy, and Lineage	2005	CIDR	0.00030932014
238	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.0002369322
359	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.0002023153
574	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00016278855
1,363	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00011025316
2,652	Comparing and Aggregating Rankings with Ties	2004	PODS	8.291138e-05
3,599	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	7.2710351e-05

Semantically Similar Papers

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