Database Paper Browser

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
4025
Venue
SIGMOD
Year
2008
Pagerank
0.00010820803
Overall Rank
1,703 | 88.17%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank Citing Paper Year Venue Pagerank
1,159 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB 0.00013584223
1,612 A Unified Approach to Ranking in Probabilistic Databases 2009 VLDB 0.00011142757
3,190 Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers 2009 SIGMOD 7.413338e-05
3,509 Consensus Answers for Queries over Probabilistic Databases 2009 PODS 7.0283775e-05
4,094 Ranking Continuous Probabilistic Datasets 2010 VLDB 6.4510938e-05
4,328 Sliding-Window Top-k Queries on Uncertain Streams 2008 VLDB 6.2765138e-05
4,370 Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance 2010 VLDB 6.2392118e-05
4,721 Nearest-Neighbor Searching Under Uncertainty 2012 PODS 5.9647585e-05
6,184 Top-K Deep Video Analytics: A Probabilistic Approach 2021 SIGMOD 5.1636368e-05
6,378 Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings 2018 VLDB 5.0844506e-05
6,707 Consistent Query Answers in Inconsistent Probabilistic Databases 2010 SIGMOD 4.9500448e-05
6,752 Evaluation of Probabilistic Threshold Queries in MCDB 2010 SIGMOD 4.9349474e-05
7,751 Computing Immutable Regions for Subspace Top-k Queries 2013 VLDB 4.6562296e-05
8,883 Threshold Query Optimization for Uncertain Data 2010 SIGMOD 4.4247207e-05
9,044 Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data 2023 VLDB 4.3997447e-05
9,167 Computing All Skyline Probabilities for Uncertain Data 2009 PODS 4.380727e-05
9,280 Ranking Distributed Probabilistic Data 2009 SIGMOD 4.3604461e-05
9,308 Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates 2015 SIGMOD 4.3544778e-05
9,495 Spatial Data Quality in the IoT Era: Management and Exploitation 2022 SIGMOD 4.3300131e-05
10,376 A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores 2025 SIGMOD 4.1905499e-05
11,511 TQEL: Framework for Query-Driven Linking of Top-K Entities in Social Media Blogs 2021 VLDB 4.1905499e-05
11,998 Attraction and Avoidance Detection from Movements 2014 VLDB 4.1905499e-05
12,216 On Pruning for Top-K Ranking in Uncertain Databases 2011 VLDB 4.1905499e-05
12,288 Building Ranked Mashups of Unstructured Sources with Uncertain Information 2010 VLDB 4.1905499e-05
12,386 Query Answering Techniques on Uncertain and Probabilistic Data 2008 SIGMOD 4.1905499e-05
12,415 Systems Aspects of Probabilistic Data Management 2008 VLDB 4.1905499e-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
8 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0015436578
74 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00057797415
103 ULDBs: Databases with Uncertainty and Lineage 2006 VLDB 0.00049520051
463 Evaluating Probabilistic Queries over Imprecise Data 2003 SIGMOD 0.00022497894
630 Management of Probabilistic Data: Foundations and Challenges 2007 PODS 0.00018942778
823 On the Representation and Querying of Sets of Possible Worlds 1987 SIGMOD 0.00016225326
1,181 Probabilistic Skylines on Uncertain Data 2007 VLDB 0.00013447487
1,269 The Dichotomy of Conjunctive Queries on Probabilistic Structures 2007 PODS 0.00012911894
1,568 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.0001131667
2,316 Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data 2004 VLDB 9.0513688e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
463 Evaluating Probabilistic Queries over Imprecise Data 2003 SIGMOD 0.00022497894
12,386 Query Answering Techniques on Uncertain and Probabilistic Data 2008 SIGMOD 4.1905499e-05
9,044 Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data 2023 VLDB 4.3997447e-05
1,612 A Unified Approach to Ranking in Probabilistic Databases 2009 VLDB 0.00011142757
4,094 Ranking Continuous Probabilistic Datasets 2010 VLDB 6.4510938e-05
1,535 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 0.00011461371
2,316 Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data 2004 VLDB 9.0513688e-05
10,376 A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores 2025 SIGMOD 4.1905499e-05
1,805 Top-k Query Evaluation with Probabilistic Guarantees 2004 VLDB 0.00010479371
3,190 Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers 2009 SIGMOD 7.413338e-05