Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data

Summary: Efficient under- and over-approximation framework for certain and possible answers to ranking, top-k and—uniquely—windowed aggregation queries over uncertain data. Implements physical operators for uncertain sorting/window in PostgreSQL, integrates with existing uncertain-DB methods, and empirically outperforms prior approaches in speed and accuracy. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 12999
Venue: VLDB
Year: 2023
Pagerank: 4.4039656e-05
Overall Rank: 9,044 | 37.09%
DOI: 10.14778/3583140.3583151

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,364	A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores	2025	SIGMOD	4.1945683e-05
10,377	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 21 of 21 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
31	Provenance Semirings	2007	PODS	0.0007857786
321	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00027527389
560	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00020141923
893	Data Integration: The Teenage Years	2006	VLDB	0.00015558352
1,106	Provenance for Aggregate Queries	2011	PODS	0.0001398766
1,609	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011150935
1,707	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010816111
1,867	Interpretable Data-Based Explanations for Fairness Debugging	2022	SIGMOD	0.00010272055
2,268	OLAP Over Uncertain and Imprecise Data	2005	VLDB	9.1497575e-05
3,051	Partial Results in Database Systems	2014	SIGMOD	7.6512591e-05
4,706	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB	5.9820914e-05
4,806	Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers	2019	SIGMOD	5.9092698e-05
5,548	Foundations of Uncertain-Data Integration	2010	VLDB	5.4446854e-05
5,779	Lenses: An On-Demand Approach to ETL	2015	VLDB	5.3307398e-05
5,857	Making SQL Queries Correct on Incomplete Databases: A Feasibility Study	2016	PODS	5.3000054e-05
6,079	Querying Uncertain Data with Aggregate Constraints	2011	SIGMOD	5.2223439e-05
6,295	Your notebook is not crumby enough, REPLace it	2020	CIDR	5.1249204e-05
7,941	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	4.613363e-05
8,138	Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints	2020	SIGMOD	4.5771031e-05
8,803	Coping with Incomplete Data: Recent Advances	2020	PODS	4.4470842e-05
9,522	SGL: A Scalable Language for Data-Driven Games	2008	SIGMOD	4.3319585e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,191	Efficient Rank Join with Aggregation Constraints	2011	VLDB	4.1945683e-05
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057857292
1,609	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011150935
7,941	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	4.613363e-05
3,014	Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures	2011	SIGMOD	7.70946e-05
12,272	Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations	2010	VLDB	4.1945683e-05
3,185	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD	7.4192604e-05
7,513	Ranking Large Temporal Data	2012	VLDB	4.7180617e-05
1,707	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010816111
4,080	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	6.4652983e-05