Anytime Approximation in Probabilistic Databases via Scaled Dissociations

Summary: Introduces an anytime branch-and-bound approximation scheme for probabilistic databases, unifying PDB and SRL model-based methods. Scaled dissociation tightens bounds for self-join-free CQ queries on tuple-independent PDBs, cutting approximation error. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hfdbabc8c657931d4
Venue: SIGMOD
Year: 2019
Pagerank: 5.2954976e-05
Overall Rank: 8,643 | 41.89%
DOI: 10.1145/3299869.3319900

Incoming Non-self Citations Over Time

Authors

1. Maarten Van den Heuvel (University of Antwerp)
2. Peter Ivanov (Northeastern University)
3. Wolfgang Gatterbauer (Northeastern University)
4. Floris Geerts (University of Antwerp)
5. Martin Theobald (University of Luxembourg)

BibTeX Citation

@inproceedings{heuvel_sigmod19,
        title = {{Anytime Approximation in Probabilistic Databases via Scaled Dissociations}},
        author = {Van den Heuvel, Maarten and Ivanov, Peter and Gatterbauer, Wolfgang and Geerts, Floris and Theobald, Martin},
        series = {{SIGMOD} '19},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3299869.3319900},
        url = {https://dl.acm.org/doi/10.1145/3299869.3319900},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,752	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.434561e-05
8,762	Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries	2024	PODS	5.283642e-05
8,886	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	5.2559789e-05
11,700	Probabilistic Reasoning at Scale: Trigger Graphs to the Rescue	2023	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
579	Incremental Knowledge Base Construction Using DeepDive	2015	VLDB	0.00016086569
696	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00014697176
934	Probase: A Probabilistic Taxonomy for Text Understanding	2012	SIGMOD	0.0001300429
1,042	YAGO3: A Knowledge Base from Multilingual Wikipedias	2015	CIDR	0.00012336872
1,615	Sensitivity Analysis and Explanations for Robust Query Evaluation in Probabilistic Databases	2011	SIGMOD	0.00010067073
1,785	Approximate Lineage for Probabilistic Databases	2008	VLDB	9.6482655e-05
2,502	Exploiting Shared Correlations in Probabilistic Databases	2008	VLDB	8.3800737e-05
2,860	Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities	2009	SIGMOD	7.9338024e-05
4,176	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB	6.7573044e-05
4,389	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	6.6226901e-05
4,765	Probabilistic Databases with MarkoViews	2012	VLDB	6.4275411e-05
5,340	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB	6.1731278e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,760	Beta Probabilistic Databases: A Scalable Approach to Belief Updating and Parameter Learning	2017	SIGMOD
2	9,169	Efficient Approximations of Conjunctive Queries	2012	PODS
3	4,655	A Temporal-Probabilistic Database Model for Information Extraction	2013	VLDB
4	5,779	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD
5	4,176	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB
6	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
7	2,018	Scalable Probabilistic Databases with Factor Graphs and MCMC	2010	VLDB
8	4,389	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB
9	5,340	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB
10	4,213	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS