Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Logarithmic Time Parallel Bayesian Inference
David Pennock
I present a parallel algorithm for exact probabilistic inference in Bayesian networks. For polytree networks with n variables, the worst-case time complexity is O(log n) 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(r^{3w}*log n) for n processors, or O(w*log n) for r^{3w}*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.
Keywords: Probabilistic inference, parallel algorithms, Bayesian networks.
Pages: 431-438
PS Link: http://www.eecs.umich.edu/~dpennock/homepage/papers/parallel-final.ps
PDF Link: /papers/98/p431-pennock.pdf
AUTHOR = "David Pennock ",
TITLE = "Logarithmic Time Parallel Bayesian Inference",
BOOKTITLE = "Proceedings of the Fourteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-98)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1998",
PAGES = "431--438"

hosted by DSL   •   site info   •   help