Parallel Recursive Best-First AND/OR Search for Exact MAP Inference in Graphical Models
Abstract
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.
Cite
Text
Kishimoto et al. "Parallel Recursive Best-First AND/OR Search for Exact MAP Inference in Graphical Models." Neural Information Processing Systems, 2015.Markdown
[Kishimoto et al. "Parallel Recursive Best-First AND/OR Search for Exact MAP Inference in Graphical Models." Neural Information Processing Systems, 2015.](https://mlanthology.org/neurips/2015/kishimoto2015neurips-parallel/)BibTeX
@inproceedings{kishimoto2015neurips-parallel,
title = {{Parallel Recursive Best-First AND/OR Search for Exact MAP Inference in Graphical Models}},
author = {Kishimoto, Akihiro and Marinescu, Radu and Botea, Adi},
booktitle = {Neural Information Processing Systems},
year = {2015},
pages = {928-936},
url = {https://mlanthology.org/neurips/2015/kishimoto2015neurips-parallel/}
}