Abstract
Bayesian networks are popular probabilistic models that capture the conditional dependencies among a set of variables. Inference in Bayesian networks is a fundamental task for answering probabilistic queries over a subset of variables in the data. However, exact inference in Bayesian networks is NP-hard, which has prompted the development of many practical inference methods. In this paper, we focus on improving the performance of the junction-tree algorithm, a well-known method for exact inference in Bayesian networks. In particular, we seek to leverage information in the workload of probabilistic queries to obtain an optimal workload-aware materialization of junction trees, with the aim to accelerate the processing of inference queries. We devise an optimal pseudo-polynomial algorithm to tackle this problem and discuss approximation schemes. Compared to state-of-the-art approaches for efficient processing of inference queries via junction trees, our methods are the first to exploit the information provided in query workloads. Our experimentation on several real-world Bayesian networks confirms the effectiveness of our techniques in speeding-up query processing.
Originalsprog | Engelsk |
---|---|
Titel | Proceedings of the 25th International Conference on Extending Database Technology |
Antal sider | 13 |
Udgivelsessted | Konstanz |
Forlag | Universität Konstanz |
Publikationsdato | 2022 |
Sider | 65-77 |
ISBN (Elektronisk) | 9783893180868 |
DOI | |
Status | Udgivet - 2022 |
Begivenhed | 25th International Conference on Extending Database Technology - Edinburgh, Storbritannien Varighed: 29 mar. 2022 → 1 apr. 2022 Konferencens nummer: 25 |
Konference
Konference | 25th International Conference on Extending Database Technology |
---|---|
Nummer | 25 |
Land/Område | Storbritannien |
By | Edinburgh |
Periode | 29/03/2022 → 01/04/2022 |