Empirical Evaluation of AND/OR Multivalued Decision Diagrams for Inference

William Lam and Rina Dechter

AND/OR Multi-valued Decision Diagrams (AOMDD) were shown to provide a more compact representation of discrete-domain real-valued functions compared to other decision diagram variants. We show the performance of AOMDDs on inference tasks in graphical models. We introduce the elimination operator to AOMDDs, which in conjunction with the combination operator introduced in previous work, yields a full bucket elimination (BE) scheme using AOMDDs as an alternative function representation to tables. We show that we are able to solve instances that do not fit in main memory when using tables.