Aarhus University Seal / Aarhus Universitets segl

Cigdem Aslay

Workload-Aware Materialization of Junction Trees

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

DOI

  • Martino Ciaperoni, Aalto University
  • ,
  • Cigdem Aslay
  • Aristides Gionis, Royal Institute of Technology
  • ,
  • Michael Mathioudakis, University of Helsinki

Bayesian networks are popular probabilistic models that capture the conditional dependencies among a set of variables. Inference in Bayesian networks is a fundamental task for answering probabilistic queries over a subset of variables in the data. However, exact inference in Bayesian networks is NP-hard, which has prompted the development of many practical inference methods. In this paper, we focus on improving the performance of the junction-tree algorithm, a well-known method for exact inference in Bayesian networks. In particular, we seek to leverage information in the workload of probabilistic queries to obtain an optimal workload-aware materialization of junction trees, with the aim to accelerate the processing of inference queries. We devise an optimal pseudo-polynomial algorithm to tackle this problem and discuss approximation schemes. Compared to state-of-the-art approaches for efficient processing of inference queries via junction trees, our methods are the first to exploit the information provided in query workloads. Our experimentation on several real-world Bayesian networks confirms the effectiveness of our techniques in speeding-up query processing.

Original languageEnglish
Title of host publicationProceedings of the 25th International Conference on Extending Database Technology
Number of pages13
Place of publicationKonstanz
PublisherUniversität Konstanz
Publication year2022
Pages65-77
ISBN (Electronic)9783893180868
DOIs
Publication statusPublished - 2022
Event25th International Conference on Extending Database Technology - Edinburgh, United Kingdom
Duration: 29 Mar 20221 Apr 2022
Conference number: 25

Conference

Conference25th International Conference on Extending Database Technology
Nummer25
LandUnited Kingdom
ByEdinburgh
Periode29/03/202201/04/2022

See relations at Aarhus University Citationformats

ID: 223751574