Next: Running time
Up: The ACCL algorithm
Previous: Computing cooccurrences in a
We have described efficient methods for computing the cooccurrences
and for partially sorting the mutual information values. What we aim
to create is a mechanism that will output the edges
in decreasing order of their mutual information.
We shall set up this mechanism in the form of a Fibonacci heap
[Fredman, Tarjan 1987] called that contains an element
for each , represented by the edge with the highest mutual
information among the edges , with , that are not yet
eliminated. The record in is of the form
,
with , and with being the key used for
sorting. Once the maximum is extracted, the used edge has to be
replaced by the next largest (in terms of ) edge in 's
lists.
To perform this latter task we use the data structures shown in Figure
20. Kruskal's algorithm is now used to
construct the desired spanning tree.
Figure 21 summarizes the resulting algorithm.
Figure 21:
The ACCL algorithm.

Next: Running time
Up: The ACCL algorithm
Previous: Computing cooccurrences in a
Journal of Machine Learning Research
20001019