Re: parallelization of potential operations

David M. Pennock (dpennock@umich.edu)
Tue, 17 Nov 1998 11:19:49 -0500

Two more papers deal with speeding up Bayesian inference through
parallelization. Delcher, Grove, Kasif, and Pearl demonstrate an algorithm
that can run in O(log n) time for (causal) tree networks on a PRAM with n
processors:

@Article{Delcher96,
author = "Arthur L. Delcher and Adam J. Grove and
Simon Kasif and Judea Pearl",
title = "Logarithmic-time updates and queries in
probabilistic networks",
journal = "Journal of Artificial Intelligence Research",
year = 1996,
volume = 4,
month = feb,
pages = "37--59"}

Postscript or PDF can be downloaded from:

http://www.jair.org/abstracts/delcher96a.html

Also, my paper in UAI-98, "Logarithmic Time Parallel Bayesian Inference",
pp. 431-438, describes an algorithm that runs in O(log n) time for
polytree networks on a PRAM with n processors. You can download the
postscript from:

http://www.eecs.umich.edu/~dpennock/homepage/papers/parallel-final.ps

or I would be happy to mail you a copy. The potential benefit of either
algorithm for multiply connected networks is less clear.

Good luck,

--Dave