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: 13000
Venue: VLDB
Year: 2023
Pagerank: 4.3997447e-05
Overall Rank: 9,044 | 37.15%
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,376	A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores	2025	SIGMOD	4.1905499e-05
10,389	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	4.1905499e-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.00078516827
322	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00027523667
560	Dependencies Revisited for Improving Data Quality	2008	PODS	0.0002012328
889	Data Integration: The Teenage Years	2006	VLDB	0.00015548507
1,106	Provenance for Aggregate Queries	2011	PODS	0.00013976386
1,612	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011142757
1,703	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010820803
1,869	Interpretable Data-Based Explanations for Fairness Debugging	2022	SIGMOD	0.00010263235
2,273	OLAP Over Uncertain and Imprecise Data	2005	VLDB	9.1447774e-05
3,054	Partial Results in Database Systems	2014	SIGMOD	7.6478475e-05
4,708	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB	5.9763416e-05
4,809	Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers	2019	SIGMOD	5.9035874e-05
5,556	Foundations of Uncertain-Data Integration	2010	VLDB	5.4394558e-05
5,788	Lenses: An On-Demand Approach to ETL	2015	VLDB	5.3256103e-05
5,863	Making SQL Queries Correct on Incomplete Databases: A Feasibility Study	2016	PODS	5.2949117e-05
6,083	Querying Uncertain Data with Aggregate Constraints	2011	SIGMOD	5.2173276e-05
6,295	Your notebook is not crumby enough, REPLace it	2020	CIDR	5.1200006e-05
7,944	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	4.6089395e-05
8,139	Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints	2020	SIGMOD	4.5727142e-05
8,802	Coping with Incomplete Data: Recent Advances	2020	PODS	4.4428211e-05
9,522	SGL: A Scalable Language for Data-Driven Games	2008	SIGMOD	4.3278071e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,199	Efficient Rank Join with Aggregation Constraints	2011	VLDB	4.1905499e-05
1,612	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011142757
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057797415
7,944	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	4.6089395e-05
3,015	Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures	2011	SIGMOD	7.7079141e-05
3,190	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD	7.413338e-05
12,280	Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations	2010	VLDB	4.1905499e-05
7,512	Ranking Large Temporal Data	2012	VLDB	4.7135369e-05
1,703	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010820803
4,328	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	6.2765138e-05