  Learning a Bayesian networks with bounded treewidth is important for reducing
the complexity of the inferences. We present a novel anytime algorithm (k-MAX)
method for this task, which scales up to thousands of variables. Through
extensive experiments we show that it consistently yields higher-scoring
structures than its competitors on complete data sets. We then consider the
problem of structure learning from incomplete data sets. This can be addressed
by structural EM, which however is computationally very demanding. We thus
adopt the novel k-MAX algorithm in the maximization step of structural EM,
obtaining an efficient computation of the expected sufficient statistics. We
test the resulting structural EM method on the task of imputing missing data,
comparing it against the state-of-the-art approach based on random forests. Our
approach achieves the same imputation accuracy of the competitors, but in about
one tenth of the time. Furthermore we show that it has worst-case complexity
linear in the input size, and that it is easily parallelizable.
