Abstract
The paper extends several variable elimination schemes into a two-phase message passing algorithm along a bucket-tree. Our analysis shows that the new algorithm, called Bucket-Tree Elimination (BTE), may provide a substantial speed-up over standard variable-elimination for important probabilistic reasoning tasks. The algorithm is developed and analyzed within a unifying view of tree-clustering methods, making crisp the relationship between the two approaches, and allowing enhancement schemes to be transferred. In particular we show how time-space tradeoffs of BTE are cast within the tree-decomposition framework.