Workload-aware materialization for efficient variable elimination on Bayesian networks

Show simple item record

dc.contributor.author Aslay, Cigdem
dc.contributor.author Ciaperoni, Martino
dc.contributor.author Gionis, Aristides
dc.contributor.author Mathioudakis, Michael
dc.date.accessioned 2021-11-01T08:09:01Z
dc.date.available 2021-11-01T08:09:01Z
dc.date.issued 2021-04-19
dc.identifier.citation Aslay , C , Ciaperoni , M , Gionis , A & Mathioudakis , M 2021 , Workload-aware materialization for efficient variable elimination on Bayesian networks . in 2021 IEEE 37th International Conference on Data Engineering (ICDE) . IEEE International Conference on Data Engineering , pp. 1152-1163 , IEEE International Conference on Data Engineering (IEEE ICDE) , Chania , Greece , 19/04/2021 . https://doi.org/10.1109/ICDE51399.2021.00104
dc.identifier.citation conference
dc.identifier.other PURE: 161497572
dc.identifier.other PURE UUID: 4e789583-5895-4796-a925-06e0381a671c
dc.identifier.other WOS: 000687830800097
dc.identifier.other ORCID: /0000-0003-0074-3966/work/102449402
dc.identifier.uri http://hdl.handle.net/10138/335891
dc.description.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. en
dc.format.extent 12
dc.language.iso eng
dc.relation.ispartof 2021 IEEE 37th International Conference on Data Engineering (ICDE)
dc.relation.ispartofseries IEEE International Conference on Data Engineering
dc.relation.isversionof 978-1-7281-9185-0
dc.relation.isversionof 978-1-7281-9184-3
dc.rights unspecified
dc.rights.uri info:eu-repo/semantics/openAccess
dc.subject 113 Computer and information sciences
dc.subject probabilistic inference
dc.subject materialization
dc.title Workload-aware materialization for efficient variable elimination on Bayesian networks en
dc.type Conference contribution
dc.contributor.organization Department of Computer Science
dc.contributor.organization Algorithmic Data Science
dc.description.reviewstatus Peer reviewed
dc.relation.doi https://doi.org/10.1109/ICDE51399.2021.00104
dc.relation.issn 1084-4627
dc.rights.accesslevel openAccess
dc.type.version acceptedVersion
dc.relation.funder Suomen Akatemia Projektilaskutus
dc.relation.grantnumber 322046

Files in this item

Total number of downloads: Loading...

Files Size Format View
icde2021_773.pdf 928.5Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record