Logarithmic Time Parallel Bayesian Inference
Abstract
I present a parallel algorithm for exact probabilistic inference in Bayesian networks. For polytree networks with n variables, the worstcase time complexity is O(logn) on a CREW PRAM (concurrent-read, exclusive-write parallel random-access machine) with n processors, for any constant number of evidence variables. For arbitrary networks, the time complexity is O(r3w log n) for n processors, or O(w log n) for r3w log n processors, where r is the maximum range of any variable, and w is the induced width (the maximum clique size), after moralizing and triangulating the network.
Cite
Text
Pennock. "Logarithmic Time Parallel Bayesian Inference." Conference on Uncertainty in Artificial Intelligence, 1998.Markdown
[Pennock. "Logarithmic Time Parallel Bayesian Inference." Conference on Uncertainty in Artificial Intelligence, 1998.](https://mlanthology.org/uai/1998/pennock1998uai-logarithmic/)BibTeX
@inproceedings{pennock1998uai-logarithmic,
title = {{Logarithmic Time Parallel Bayesian Inference}},
author = {Pennock, David M.},
booktitle = {Conference on Uncertainty in Artificial Intelligence},
year = {1998},
pages = {431-438},
url = {https://mlanthology.org/uai/1998/pennock1998uai-logarithmic/}
}