Workload-aware materialization for efficient variable elimination on Bayesian networks
Loading...
Access rights
openAccess
acceptedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2021-04
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
12
Series
Proceedings - 2021 IEEE 37th International Conference on Data Engineering, ICDE 2021, pp. 1152-1163, Proceedings - International Conference on Data Engineering ; Volume 2021-April
Abstract
Bayesian networks are general, well-studied probabilistic models that capture dependencies among a set of variables. Variable Elimination is a fundamental algorithm for probabilistic inference over Bayesian networks. In this paper, we propose a novel materialization method, which can lead to significant efficiency gains when processing inference queries using the Variable Elimination algorithm. In particular, we address the problem of choosing a set of intermediate results to precompute and materialize, so as to maximize the expected efficiency gain over a given query workload. For the problem we consider, we provide an optimal polynomial-time algorithm and discuss alternative methods. We validate our technique using real-world Bayesian networks. Our experimental results confirm that a modest amount of materialization can lead to significant improvements in the running time of queries, with an average gain of 70%, and reaching up to a gain of 99%, for a uniform workload of queries. Moreover, in comparison with existing junction tree methods that also rely on materialization, our approach achieves competitive efficiency during inference using significantly lighter materialization.Description
| openaire: EC/H2020/871042/EU//SoBigData-PlusPlus
Keywords
Materialization, Probabilistic inference
Other note
Citation
Aslay, C, Ciaperoni, M, Gionis, A & Mathioudakis, M 2021, Workload-aware materialization for efficient variable elimination on Bayesian networks . in Proceedings - 2021 IEEE 37th International Conference on Data Engineering, ICDE 2021 ., 9458677, Proceedings - International Conference on Data Engineering, vol. 2021-April, IEEE, pp. 1152-1163, International Conference on Data Engineering, Chania, Greece, 19/04/2021 . https://doi.org/10.1109/ICDE51399.2021.00104