Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Island algorithm
open-in-new
<p>The island algorithm is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> for performing inference on <a href="/facts/Hidden_Markov_models/ur1zTAhP">hidden Markov models</a>, or their generalization, <a href="/facts/Dynamic_Bayesian_networks/Gm1jeuh2">dynamic Bayesian networks</a>. It calculates the <a href="/facts/Marginal_distribution/U9XBWAd1">marginal distribution</a> for each unobserved node, conditional on any observed nodes. </p><p>The island algorithm is a modification of <a href="/facts/Belief_propagation/TRY5LVbP">belief propagation</a>. It trades smaller <a href="/facts/Memory_usage/vthLkUpz">memory usage</a> for longer running time: while belief propagation takes <a href="/facts/Big_O_notation/weFFjSWg">O(n)</a> 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. </p>