Scaling Up Bayesian DAG Sampling

{Bayesian} inference of {Bayesian} network structures is often performed by sampling directed acyclic graphs along an appropriately constructed {Markov} chain. We present two techniques to improve sampling. First, we give an efficient implementation of basic moves, which add, delete, or reverse a single arc. Second, we expedite summing over parent sets, an expensive task required for more sophisticated moves: we devise a preprocessing method to prune possible parent sets so as to approximately preserve the sums. Our empirical study shows that our techniques can yield substantial efficiency gains compared to previous methods.