Bayesian structure discovery in Bayesian networks with less space

Current exact algorithms for score-based structure discovery in Bayesian networks on $n$ nodes run in time and space within a polynomial factor of $2^n$. For practical use, the space requirement is the bottleneck, which motivates trading space against time. Here, previous results on finding an optimal network structure in less space are extended in two directions. First, we consider the problem of computing the posterior probability of a given arc set. Second, we operate with the general partial order framework and its specialization to bucket orders, introduced recently for related permutation problems. The main technical contribution is the development of a fast algorithm for a novel zeta transform variant, which may be of independent interest.