Workload-aware materialization for efficient variable elimination on Bayesian networks

Cigdem Aslay, Martino Ciaperoni, Aristides Gionis, Michael Mathioudakis

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

1 Citation (Scopus)
52 Downloads (Pure)

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.

Original languageEnglish
Title of host publicationProceedings - 2021 IEEE 37th International Conference on Data Engineering, ICDE 2021
PublisherIEEE
Pages1152-1163
Number of pages12
ISBN (Electronic)9781728191843
DOIs
Publication statusPublished - Apr 2021
MoE publication typeA4 Conference publication
EventInternational Conference on Data Engineering - Virtual, Online, Chania, Greece
Duration: 19 Apr 202122 Apr 2021
Conference number: 37

Publication series

NameProceedings - International Conference on Data Engineering
Volume2021-April
ISSN (Print)1084-4627

Conference

ConferenceInternational Conference on Data Engineering
Abbreviated titleICDE
Country/TerritoryGreece
CityChania
Period19/04/202122/04/2021

Keywords

  • Materialization
  • Probabilistic inference

Fingerprint

Dive into the research topics of 'Workload-aware materialization for efficient variable elimination on Bayesian networks'. Together they form a unique fingerprint.

Cite this