DBScholar

Back to papers

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
h2d82ea08814f1141
Venue
SIGMOD
Year
2008
Pagerank
0.0001079253
Overall Rank
1,396 | 90.62%
DOI
10.1145/1376616.1376685

Incoming Non-self Citations Over Time

Authors

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,063 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB 0.00012208695
1,365 A Unified Approach to Ranking in Probabilistic Databases 2009 VLDB 0.00010913898
3,105 Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers 2009 SIGMOD 7.6445188e-05
3,326 Sliding-Window Top-k Queries on Uncertain Streams 2008 VLDB 7.4227632e-05
3,542 Consensus Answers for Queries over Probabilistic Databases 2009 PODS 7.2155312e-05
3,893 Ranking Continuous Probabilistic Datasets 2010 VLDB 6.940442e-05
4,196 Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance 2010 VLDB 6.7421052e-05
4,835 Nearest-Neighbor Searching Under Uncertainty 2012 PODS 6.3877419e-05
5,779 Consistent Query Answers in Inconsistent Probabilistic Databases 2010 SIGMOD 5.9976039e-05
5,804 Top-K Deep Video Analytics: A Probabilistic Approach 2021 SIGMOD 5.9888455e-05
6,176 Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings 2018 VLDB 5.8609559e-05
7,050 Evaluation of Probabilistic Threshold Queries in MCDB 2010 SIGMOD 5.6132096e-05
7,877 Spatial Data Quality in the IoT Era: Management and Exploitation 2022 SIGMOD 5.4346692e-05
7,961 Computing Immutable Regions for Subspace Top-k Queries 2013 VLDB 5.4167814e-05
9,214 Threshold Query Optimization for Uncertain Data 2010 SIGMOD 5.2058816e-05
9,374 Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data 2023 VLDB 5.1868213e-05
9,502 Computing All Skyline Probabilities for Uncertain Data 2009 PODS 5.1708619e-05
9,525 Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates 2015 SIGMOD 5.1662415e-05
9,607 Ranking Distributed Probabilistic Data 2009 SIGMOD 5.1528778e-05
11,100 A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores 2025 SIGMOD 4.9793485e-05
12,009 TQEL: Framework for Query-Driven Linking of Top-K Entities in Social Media Blogs 2021 VLDB 4.9793485e-05
12,479 Attraction and Avoidance Detection from Movements 2014 VLDB 4.9793485e-05
12,694 On Pruning for Top-K Ranking in Uncertain Databases 2011 VLDB 4.9793485e-05
12,766 Building Ranked Mashups of Unstructured Sources with Uncertain Information 2010 VLDB 4.9793485e-05
12,861 Query Answering Techniques on Uncertain and Probabilistic Data 2008 SIGMOD 4.9793485e-05
12,890 Systems Aspects of Probabilistic Data Management 2008 VLDB 4.9793485e-05
Previous Page 1 / 1 Next

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.0010679641
51 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00042936299
84 ULDBs: Databases with Uncertainty and Lineage 2006 VLDB 0.00035963861
370 Evaluating Probabilistic Queries over Imprecise Data 2003 SIGMOD 0.00019846702
587 Management of Probabilistic Data: Foundations and Challenges 2007 PODS 0.00015933201
970 On the Representation and Querying of Sets of Possible Worlds 1987 SIGMOD 0.00012772086
1,065 The Dichotomy of Conjunctive Queries on Probabilistic Structures 2007 PODS 0.0001219981
1,124 Probabilistic Skylines on Uncertain Data 2007 VLDB 0.00011927351
1,518 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.00010396565
2,104 Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data 2004 VLDB 9.0366183e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 370 Evaluating Probabilistic Queries over Imprecise Data 2003 SIGMOD
2 12,861 Query Answering Techniques on Uncertain and Probabilistic Data 2008 SIGMOD
3 9,374 Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data 2023 VLDB
4 1,365 A Unified Approach to Ranking in Probabilistic Databases 2009 VLDB
5 3,893 Ranking Continuous Probabilistic Datasets 2010 VLDB
6 1,635 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB
7 2,104 Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data 2004 VLDB
8 11,100 A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores 2025 SIGMOD
9 1,535 Top-k Query Evaluation with Probabilistic Guarantees 2004 VLDB
10 3,105 Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers 2009 SIGMOD