A Time and Space Efficient Junction Tree Architecture
  The junction tree algorithm is a way of computing marginals of boolean
multivariate probability distributions that factorise over sets of random
variables. The junction tree algorithm first constructs a tree called a
junction tree who's vertices are sets of random variables. The algorithm then
performs a generalised version of belief propagation on the junction tree. The
Shafer-Shenoy and Hugin architectures are two ways to perform this belief
propagation that tradeoff time and space complexities in different ways: Hugin
propagation is at least as fast as Shafer-Shenoy propagation and in the cases
that we have large vertices of high degree is significantly faster. However,
this speed increase comes at the cost of an increased space complexity. This
paper first introduces a simple novel architecture, ARCH-1, which has the best
of both worlds: the speed of Hugin propagation and the low space requirements
of Shafer-Shenoy propagation. A more complicated novel architecture, ARCH-2, is
then introduced which has, up to a factor only linear in the maximum
cardinality of any vertex, time and space complexities at least as good as
ARCH-1 and in the cases that we have large vertices of high degree is
significantly faster than ARCH-1.
