Workload-aware materialization for efficient variable elimination on Bayesian networks

Näytä kaikki kuvailutiedot



Pysyväisosoite

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

Lähdeviite

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

Julkaisun nimi: Workload-aware materialization for efficient variable elimination on Bayesian networks
Tekijä: Aslay, Cigdem; Ciaperoni, Martino; Gionis, Aristides; Mathioudakis, Michael
Tekijän organisaatio: Department of Computer Science
Algorithmic Data Science
Päiväys: 2021-04-19
Kieli: eng
Sivumäärä: 12
Kuuluu julkaisusarjaan: 2021 IEEE 37th International Conference on Data Engineering (ICDE)
Kuuluu julkaisusarjaan: IEEE International Conference on Data Engineering
ISBN: 978-1-7281-9185-0
978-1-7281-9184-3
ISSN: 1084-4627
DOI-tunniste: https://doi.org/10.1109/ICDE51399.2021.00104
URI: http://hdl.handle.net/10138/335891
Tiivistelmä: 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.
Avainsanat: 113 Computer and information sciences
probabilistic inference
materialization
Vertaisarvioitu: Kyllä
Tekijänoikeustiedot: unspecified
Pääsyrajoitteet: openAccess
Rinnakkaistallennettu versio: acceptedVersion
Rahoittaja: Suomen Akatemia Projektilaskutus
Rahoitusnumero: 322046


Tiedostot

Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
icde2021_773.pdf 928.5KB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot