Distributed Evidence Propagation in Junction Trees

• Yinglong Xia University of Southern California
• Viktor K. Prasanna University of Southern California

Abstract

Evidence propagation is a major step in exact inference, a key problem in exploring probabilistic graphical models. In this paper, we propose a novel approach for evidence propagation on clusters. We decompose a junction tree into a set of sub trees, and then perform evidence propagation in the sub trees in parallel. The partially updated sub trees are merged after evidence collection. In addition, we propose a technique to explore tradeoff between overhead due to startup latency of message passing and bandwidth utilization efficiency. We implemented the proposed method on state-of-the-art clusters using MPI. Experimental results show that the proposed method exhibits superior performance compared with the baseline methods.

Keywords: Junctions, Program processors, Particle separators, Bayesian methods, Merging, Bandwidth, Silicon, exact inference, junction tree, parallel computing, cluster