Workload-aware materialization for efficient variable elimination on Bayesian networks

Visa fullständig post



Permalänk

http://hdl.handle.net/10138/335891

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

Titel: Workload-aware materialization for efficient variable elimination on Bayesian networks
Författare: Aslay, Cigdem; Ciaperoni, Martino; Gionis, Aristides; Mathioudakis, Michael
Upphovmannens organisation: Department of Computer Science
Algorithmic Data Science
Datum: 2021-04-19
Språk: eng
Sidantal: 12
Tillhör serie: 2021 IEEE 37th International Conference on Data Engineering (ICDE)
Tillhör serie: IEEE International Conference on Data Engineering
ISBN: 978-1-7281-9185-0
978-1-7281-9184-3
ISSN: 1084-4627
DOI: https://doi.org/10.1109/ICDE51399.2021.00104
Permanenta länken (URI): http://hdl.handle.net/10138/335891
Abstrakt: 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.
Subject: 113 Computer and information sciences
probabilistic inference
materialization
Referentgranskad: Ja
Licens: unspecified
Användningsbegränsning: openAccess
Parallelpublicerad version: acceptedVersion
Finansierad av: Suomen Akatemia Projektilaskutus
Finansierings ID: 322046


Filer under denna titel

Totalt antal nerladdningar: Laddar...

Filer Storlek Format Granska
icde2021_773.pdf 928.5Kb PDF Granska/Öppna

Detta dokument registreras i samling:

Visa fullständig post