Anytime approximation in probabilistic databases
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 algorit...
| Hlavní autoři: | , , |
|---|---|
| Médium: | Journal article |
| Vydáno: |
2013
|
| _version_ | 1826263416854020096 |
|---|---|
| author | Fink, R Huang, J Olteanu, D |
| author_facet | Fink, R Huang, J Olteanu, D |
| author_sort | Fink, R |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T19:51:25Z |
| format | Journal article |
| id | oxford-uuid:241b3f22-db37-41c4-98cd-bb5be17872b7 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T19:51:25Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | oxford-uuid:241b3f22-db37-41c4-98cd-bb5be17872b72022-03-26T11:48:01ZAnytime approximation in probabilistic databasesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:241b3f22-db37-41c4-98cd-bb5be17872b7Symplectic Elements at Oxford2013Fink, RHuang, JOlteanu, DThis 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. |
| spellingShingle | Fink, R Huang, J Olteanu, D Anytime approximation in probabilistic databases |
| title | Anytime approximation in probabilistic databases |
| title_full | Anytime approximation in probabilistic databases |
| title_fullStr | Anytime approximation in probabilistic databases |
| title_full_unstemmed | Anytime approximation in probabilistic databases |
| title_short | Anytime approximation in probabilistic databases |
| title_sort | anytime approximation in probabilistic databases |
| work_keys_str_mv | AT finkr anytimeapproximationinprobabilisticdatabases AT huangj anytimeapproximationinprobabilisticdatabases AT olteanud anytimeapproximationinprobabilisticdatabases |