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: h75c68e904342743a
Venue: VLDB
Year: 2023
Pagerank: 5.1843659e-05
Overall Rank: 9,383 | 36.94%
DOI: 10.14778/3583140.3583151
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Su Feng (Illinois Institute of Technology)
2. Boris Glavic (Illinois Institute of Technology)
3. Oliver Kennedy (State University of New York at Buffalo)

BibTeX Citation

@article{feng_vldb23,
        title = {{Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data}},
        author = {Feng, Su and Glavic, Boris and Kennedy, Oliver},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {6},
        pages = {1346--1358},
        doi = {10.14778/3583140.3583151},
        url = {https://doi.org/10.14778/3583140.3583151},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,895	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	5.2534908e-05
11,109	A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores	2025	SIGMOD	4.9769913e-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
17	Provenance Semirings	2007	PODS	0.00059813669
245	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00023251151
501	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00017273167
811	Provenance for Aggregate Queries	2011	PODS	0.00013746145
824	Data Integration: The Teenage Years	2006	VLDB	0.00013641217
1,360	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00010913787
1,397	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010787659
1,943	Interpretable Data-Based Explanations for Fairness Debugging	2022	SIGMOD	9.3254131e-05
2,205	OLAP Over Uncertain and Imprecise Data	2005	VLDB	8.8519761e-05
2,719	Partial Results in Database Systems	2014	SIGMOD	8.0942034e-05
4,176	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB	6.7541079e-05
4,870	Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers	2019	SIGMOD	6.3718189e-05
5,652	Foundations of Uncertain-Data Integration	2010	VLDB	6.0492525e-05
5,803	Making SQL Queries Correct on Incomplete Databases: A Feasibility Study	2016	PODS	5.9867996e-05
5,986	Querying Uncertain Data with Aggregate Constraints	2011	SIGMOD	5.9232153e-05
6,048	Your notebook is not crumby enough, REPLace it	2020	CIDR	5.9024167e-05
6,091	Lenses: An On-Demand Approach to ETL	2015	VLDB	5.8880755e-05
8,172	Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints	2020	SIGMOD	5.3824434e-05
8,435	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	5.3324907e-05
9,012	Coping with Incomplete Data: Recent Advances	2020	PODS	5.2369252e-05
9,845	SGL: A Scalable Language for Data-Driven Games	2008	SIGMOD	5.1210015e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,683	Efficient Rank Join with Aggregation Constraints	2011	VLDB
2	1,360	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB
3	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
4	2,621	Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures	2011	SIGMOD
5	8,435	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD
6	12,764	Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations	2010	VLDB
7	3,107	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD
8	8,109	Ranking Large Temporal Data	2012	VLDB
9	1,397	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD
10	3,328	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB