Workload-aware materialization for efficient variable elimination on Bayesian networks

Show full item record



Permalink

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

Title: Workload-aware materialization for efficient variable elimination on Bayesian networks
Author: Aslay, Cigdem; Ciaperoni, Martino; Gionis, Aristides; Mathioudakis, Michael
Other contributor: University of Helsinki, Department of Computer Science

Date: 2021-04-19
Language: eng
Number of pages: 12
Belongs to series: 2021 IEEE 37th International Conference on Data Engineering (ICDE)
Belongs to series: IEEE International Conference on Data Engineering
ISBN: 978-1-7281-9185-0
978-1-7281-9184-3
DOI: https://doi.org/10.1109/ICDE51399.2021.00104
URI: http://hdl.handle.net/10138/335891
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.
Subject: 113 Computer and information sciences
probabilistic inference
materialization
Rights:


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 full item record