摘要
We present a new data structure, *block cover*, for approximate weighted counting and sampling of subsets of a given query set. Such queries are the main computational bottleneck, e.g., in advanced Markov chain Monte Carlo algorithms for Bayesian learning of Bayesian networks. Given a collection of weighted subsets of a ground set N, our key idea is to select a few moderate-size subsets B of N, called blocks, so as to cover all or most of the input collection by the power sets 2^B. An approximate sum over the subsets of a query set Q is obtained by adding up the contributions within each block, which contibutions we precompute. We also give a similar, efficient algorithm for generating a subset of Q with probability proportional to its weight. Our empirical results suggest that block covers are superior to previous approaches, which consider the subsets of interest one by one.