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


  • 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
ISBN (Electronic)9783893180868
Publication statusPublished - 2022
Event25th International Conference on Extending Database Technology - Edinburgh, United Kingdom
Duration: 29 Mar 20221 Apr 2022
Conference number: 25


Conference25th International Conference on Extending Database Technology
LandUnited Kingdom

See relations at Aarhus University Citationformats

ID: 223751574