Anytime approximation in probabilistic databases

Journal article

This article describes an approximation algorithm for computing the probability of propositional formulas over discrete random variables. It incrementally refines lower and upper bounds on the probability of the formulas until the desired absolute or relative error guarantee is reached. This algorithm is used by the SPROUT query engine to approximate the probabilities of results to relational algebra queries on expressive probabilistic databases. © 2013 Springer-Verlag Berlin Heidelberg.

Authors: Fink, R; Huang, J; Olteanu, D

• Publication status: Published
• Journal: VLDB JOURNAL
• Volume: 22
• Issue: 6
• Pages: 823-848
• Publication date: 2013-12-01
• DOI: 10.1007/s00778-013-0310-5
• EISSN: 0949-877X
• ISSN: 1066-8888
• Keywords: Probabilistic databases; Query evaluation; Model-based approximation; Anytime approximation