Island algorithm: Difference between revisions

Revision as of 02:21, 16 November 2011

Revision as of 04:46, 18 November 2011

Line 3:

The island algorithm is a modification of [[belief propagation]].

It trades smaller memory usage for longer running time: while belief propagation takes O(n) time and O(n) memory, the island algorithm takes O(n log n) time and O(log n) memory. On a computer with an unlimited number of processors, this can be reduced to O(n) total time, while still taking only O(log n) memory. <ref>J. Binder, K. Murphy and S. Russell. Space-Efficient Inference in Dynamic Probabilistic Networks. Int'l, Joint Conf. on Artificial Intelligence, 1997.</ref>

==The algorithm==

Line 20:

==References==

{{reflist}}

{{Uncategorized|date=November 2011}}