FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds

Summary: FastPDB tackles bag-probabilistic queries with bag semantics and PTIME data, but exact processing is slower than deterministic evaluation. It enables fast approximations by sampling monomials directly, avoiding upfront lineage, scalable to data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h2231da645ffdad86
Venue: SIGMOD
Year: 2025
Pagerank: 5.2534908e-05
Overall Rank: 8,895 | 40.22%
DOI: 10.1145/3709691

Incoming Non-self Citations Over Time

Authors

1. Aaron Huber (State University of New York at Buffalo)
2. Oliver Kennedy (State University of New York at Buffalo)
3. Atri Rudra (State University of New York at Buffalo)
4. Zhuoyue Zhao (State University of New York at Buffalo)
5. Su Feng (Nanjing Tech University)
6. Boris Glavic (University of Illinois Chicago)

BibTeX Citation

@inproceedings{huber_sigmod25,
        title = {{FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds}},
        author = {Huber, Aaron and Kennedy, Oliver and Rudra, Atri and Zhao, Zhuoyue and Feng, Su and Glavic, Boris},
        series = {{SIGMOD} '25},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3709691},
        url = {https://dl.acm.org/doi/10.1145/3709691},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,516	Variational Inference for De Finetti Logic	2026	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 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
104	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00033676943
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029858107
175	Simple Random Sampling from Relational Databases	1986	VLDB	0.00026776696
245	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00023251151
337	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00020613834
579	Incremental Knowledge Base Construction Using DeepDive	2015	VLDB	0.00016083582
596	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015782051
660	The Complexity of Query Reliability	1998	PODS	0.00015045167
1,066	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012194105
1,348	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB	0.00010942213
1,713	SMOKE: Fine-grained Lineage at Interactive Speed	2018	VLDB	9.8129981e-05
1,812	ProvSQL: Provenance and Probability Management in PostgreSQL	2018	VLDB	9.5780882e-05
3,494	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	7.2548566e-05
3,994	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	6.8652819e-05
4,870	Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers	2019	SIGMOD	6.3718189e-05
5,799	MCDB-R: Risk Analysis in the Database	2010	VLDB	5.9879586e-05
6,002	Approximate Query Engines: Commercial Challenges and Research Opportunities	2017	SIGMOD	5.9149725e-05
6,091	Lenses: An On-Demand Approach to ETL	2015	VLDB	5.8880755e-05
8,435	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	5.3324907e-05
8,650	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	5.2929907e-05
9,383	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB	5.1843659e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,431	Local Structure and Determinism in Probabilistic Databases	2012	SIGMOD
2	4,657	A Temporal-Probabilistic Database Model for Information Extraction	2013	VLDB
3	8,193	Probabilistic Histograms for Probabilistic Data	2009	VLDB
4	4,390	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB
5	8,650	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD
6	7,470	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS
7	5,342	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB
8	4,176	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB
9	4,215	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
10	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB