

![0_image_0.png](0_image_0.png)

Our solution consists of the following steps. In a preprocessing stage, we segment each input text (Kan, Klavans, & McKeown, 1998) based on word distribution and coreference analysis, so that given two sentences within the same text, we can determine if they are topically related. Assume the themes A and B exist, where A contains sentences (A1 **... A**n),
and B contains sentences (B1 ... Bm**). Recall that a theme is a set of sentences conveying**
similar information drawn from different input texts. We denote \#AB **to be the number of**
pairs of sentences (Ai,Bj ) which appear in the same text, and \#AB+ **to be the number of**
sentence pairs which appear in the same text and are in the same segment.

In the first stage, for each pair of themes A and B**, we compute the ratio \#**AB+/\#AB
to measure the relatedness of two themes. This measure takes **into account both positive**
and negative evidence. If most of the sentences in A and B **that appear together in the same** texts are also in the same segments, it means that A and B **are highly topically related. In**
this case, the ratio is close to 1. On the other hand, if among the texts containing sentences from A and B, only a few pairs are in the same segments, then A and B **are not topically**
related. Accordingly, the ratio is close to 0. A and B **are considered related if this ratio is** higher than a predetermined threshold. We determined experimentally its value to be 0.6.

This strategy defines pairwise relations between themes. A transitive closure of this relation builds groups of related themes and, as a result, ensures that themes that do not appear together in any article but which are both related to a **third theme will still be** linked. This creates an even higher degree of relatedness among themes. Because we use a threshold to establish pairwise relations, the transitive **closure does not produce elongated**
chains that could link together unrelated themes. We are now **able to identify topically** related themes. At the end of the first stage, they are grouped **into blocks.**
In a second stage, we assign a time stamp to each block of related themes using the earliest time stamp of the themes it contains. We adapt the CO **algorithm described in 4.2.1**
to work at the level of the blocks. The blocks and the themes correspond to, respectively, themes and sentences in the CO algorithm. By analogy, we can easily show that the adapted algorithm produces a complete order of the blocks. This yields a macro-ordering of the summary. We still need to order the themes inside each block.

In the last stage of the augmented algorithm, for each block, **we order the themes it**
contains by applying the CO algorithm to them. Figure 12 shows an example of a summary produced by the augmented algorithm.