Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach

Summary: Introduces probabilistic threshold top-k queries on uncertain data, returning records with probability ≥ p to be in the top-k. Offers an exact algorithm, a fast sampling method, and a Poisson-approximation, with empirical evaluation on real and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4086
Venue: SIGMOD
Year: 2008
Pagerank: 0.00011025316
Overall Rank: 1,363 | 90.66%
DOI: 10.1145/1376616.1376685

Incoming Non-self Citations Over Time

Authors

1. Ming Hua (Simon Fraser University)
2. Jian Pei (Simon Fraser University)
3. Wenjie Zhang (National ICT Australia; University of New South Wales)
4. Xuemin Lin (National ICT Australia; University of New South Wales)

BibTeX Citation

@inproceedings{hua_sigmod08,
        title = {{Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach}},
        author = {Hua, Ming and Pei, Jian and Zhang, Wenjie and Lin, Xuemin},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376685},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376685},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,049	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012415522
1,327	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011141552
3,049	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD	7.8151597e-05
3,483	Consensus Answers for Queries over Probabilistic Databases	2009	PODS	7.372823e-05
3,599	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	7.2710351e-05
3,823	Ranking Continuous Probabilistic Datasets	2010	VLDB	7.092508e-05
4,112	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.8944534e-05
4,850	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	6.480347e-05
5,648	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD	6.1351417e-05
5,827	Top-K Deep Video Analytics: A Probabilistic Approach	2021	SIGMOD	6.0744172e-05
6,052	Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings	2018	VLDB	5.9941393e-05
6,913	Evaluation of Probabilistic Threshold Queries in MCDB	2010	SIGMOD	5.7405e-05
7,806	Computing Immutable Regions for Subspace Top-k Queries	2013	VLDB	5.5407909e-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,194	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB	5.3058708e-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,425	Ranking Distributed Probabilistic Data	2009	SIGMOD	5.2711481e-05
10,657	A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores	2025	SIGMOD	5.093636e-05
11,705	TQEL: Framework for Query-Driven Linking of Top-K Entities in Social Media Blogs	2021	VLDB	5.093636e-05
12,188	Attraction and Avoidance Detection from Movements	2014	VLDB	5.093636e-05
12,403	On Pruning for Top-K Ranking in Uncertain Databases	2011	VLDB	5.093636e-05
12,475	Building Ranked Mashups of Unstructured Sources with Uncertain Information	2010	VLDB	5.093636e-05
12,571	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD	5.093636e-05
12,600	Systems Aspects of Probabilistic Data Management	2008	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
359	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.0002023153
574	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00016278855
947	On the Representation and Querying of Sets of Possible Worlds	1987	SIGMOD	0.00013041389
1,041	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012453494
1,097	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00012181027
1,486	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00010625076
2,062	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.24085e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	359	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD
2	12,571	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD
3	9,194	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB
4	1,327	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB
5	3,823	Ranking Continuous Probabilistic Datasets	2010	VLDB
6	1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
7	2,062	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB
8	10,657	A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores	2025	SIGMOD
9	1,519	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB
10	3,049	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD