Parallel Recursive Best-First AND/OR Search for Exact MAP Inference in Graphical Models
Akihiro Kishimoto · Radu Marinescu · Adi Botea

Thu Dec 10th 11:00 AM -- 03:00 PM @ 210 C #36 #None

The paper presents and evaluates the power of parallel search for exact MAP inference in graphical models. We introduce a new parallel shared-memory recursive best-first AND/OR search algorithm, called SPRBFAOO, that explores the search space in a best-first manner while operating with restricted memory. Our experiments show that SPRBFAOO is often superior to the current state-of-the-art sequential AND/OR search approaches, leading to considerable speed-ups (up to 7-fold with 12 threads), especially on hard problem instances.

Author Information

Akihiro Kishimoto (IBM Research)
Radu Marinescu (IBM Research, Ireland)
Adi Botea (IBM Research)

More from the Same Authors