Scaling Up MAP Search in Bayesian Networks Using External Memory

State-of-the-art exact algorithms for solving the MAP problem in Bayesian networks use depth-first branch-and-bound search with bounds computed by evaluating a join tree. Although this approach is effective, it can fail if the join tree is too large to fit in RAM. We describe an external-memory MAP search algorithm that stores much of the join tree on disk, keeping the parts of the join tree in RAM that are needed to compute bounds for the current search nodes, and using heuristics to decide which parts of the join tree to write to disk when RAM is full. Preliminary results show that this approach improves the scalability of exact MAP search algorithms.