Sébastien Laborie
email: sebastien.laborie@inrialpes.fr

Jérôme Euzenat
email: jerome.euzenat@inrialpes.fr

Nabil Layaïda
email: nabil.layaida@inrialpes.fr

Multimedia Document Summarization based on a Semantic Adaptation Framework

Keywords: H, 5, 1 [Information Systems]: Multimedia Information Systems Qualitative representation and reasoning, SMIL documents

The multiplication of presentation contexts (such as mobile phones, PDAs) for multimedia documents requires the adaptation of document specifications. In an earlier work, a semantic framework for multimedia document adaptation was proposed. This framework deals with the semantics of the document composition by transforming the relations between multimedia objects. However, it was lacking the capability of suppressing multimedia objects. In this paper, we extend the proposed adaptation with this capability. Thanks to this extension, we present a method for summarizing multimedia documents. Moreover, when multimedia objects are removed, the resulted document satisfies some properties such as presentation contiguity. To validate our framework, we adapt standard multimedia documents such as SMIL documents.

INTRODUCTION

A multimedia document may be played on different devices with different capabilities: phones, PDAs, desktop computers, setup boxes, etc. These introduce different constraints on the presentation itself. For instance, CPU or player limitations (e.g., mobile phones) may prevent videos from being displayed concurrently. Other constraints may also be introduced by user preferences, content protection or terminal capabilities [START_REF]W3C. Composite Capability/Preference Profiles (CC/PP): Structure and Vocabularies[END_REF]. The constraints imposed by a client constitute its profile.

To satisfy profiles, multimedia documents must be adapted, i.e., transformed into documents compatible with the target contexts before being played. Several kinds of adaptation are possible, such as local adaptation (adaptation of media objects individually) and global adaptation (adaptation of the document structure). This paper focuses on the latter.

In [START_REF] Euzenat | A semantic framework for multimedia document adaptation[END_REF], a framework for adapting multimedia documents based on the qualitative semantics of the documents and constraints was proposed. This approach transforms the relations between multimedia objects and ensures two main properties: (1) that adaptation constraints are satisfied and (2) that the adapted document is as close as possible to the initial document. As an example, for the temporal dimension of documents, this work has been applied to descriptions based on the Allen algebra [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF].

Currently, this framework is lacking the capability of suppressing multimedia objects. In this paper, we propose to extend the proposed adaptation framework with this capability. Hence, two applications can result. First, the profile may express that some multimedia objects are forbidden and consequently adaptation must remove them ( §4). Second, the profile may express that only a certain number of multimedia objects are allowed and adaptation can be considered as a summarization process ( §5). Moreover, we show that when multimedia objects are removed, the resulted document satisfies properties such as presentation contiguity.

For a smooth implementation, we provide algorithms that compute adapted multimedia documents. Finally, we validate our adaptation approach by adapting real standard multimedia documents such as SMIL documents [START_REF]W3C. Synchronized Multimedia Integration Language (SMIL 2.0) Specification[END_REF] ( §6).

Let introduce a multimedia document example ( §2) that will be used in this paper and the current proposed adaptation framework ( §3).

MULTIMEDIA DOCUMENT SPECIFICA-TION

Multimedia documents are composed of various multimedia objects such as texts, images, sounds and videos. These multimedia objects are organized into several dimensions [START_REF] Roisin | Authoring structured multimedia documents[END_REF]: temporal, spatial, logical and hypermedia.

For example, Figure 1 shows the temporal dimension of a movie trailer presentation composed of different multimedia objects such as a movie Poster (Image), a Trailer (Video), an Abstract (Text), the Characters interview (Video) and the upcoming Dates (Text). There are several languages or formats for specifying multimedia documents such as SMIL [START_REF]W3C. Synchronized Multimedia Integration Language (SMIL 2.0) Specification[END_REF], SVG [START_REF]W3C. Scalable Vector Graphics (SVG)[END_REF], Madeus [START_REF] Jourdan | Madeus, an authoring environment for interactive multimedia documents[END_REF], etc. Making the adaptation format-dependent requires an adaptation strategy for every single format. Instead, we propose an abstraction layer which allows to hide the format specific syntax and details, and capture the essence of a given document with respect to its main dimensions (Def. 1).

The advantages of such an adaptation scheme are twofold. First, it allows to reuse the same strategy for the different formats. Second, the abstract representation provides more flexibility for the adaptation since the relations between multimedia objects can be described qualitatively.

Definition 1 (Multimedia document specification).

A multimedia document specification s = O, C is made of a set of multimedia objects O and a set of constraints C between these objects. In the remainder, the constraints will be considered as binary.

MULTIMEDIA DOCUMENT ADAPTATION

In [START_REF] Euzenat | A semantic framework for multimedia document adaptation[END_REF], a semantic approach for multimedia document adaptation is defined. This approach interprets each document as the set of its potential executions (i.e., related to the initial document) and a profile as the set of its possible executions. In this context, "adapting" amounts to find the set of potential executions that are possible. When none is possible, the goal of adaptation is to find executions as close as possible to potential executions that satisfy the profile.

We consider both the multimedia document specifications and the profiles as a set of relations holding between multimedia objects. The potential and possible executions are ideally represented by relation graphs.

Definition 2 (Relation graph). Let O be a set of multimedia objects and C a set of constraints between the elements of O.

A multimedia document specification s = O, C relative to a set of executions can be represented as a complete directed labeled graph gs = O, E, λ called a relation graph. The elements of O are nodes, E is the set of edges and λ : E → 2 R is a total labeling function from the edges to a set of relations of R such that for each x r y ∈ C, r ∈ λ( x, y ).

Figure 2 presents two relation graphs. Each node corresponds to a multimedia object and each edge is labeled by a set of relations. In this example, the Allen algebra of temporal interval relations R [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF] is used to describe the temporal dimension. These relations are presented in Table In this context, adapting consists of finding a set of relation graphs corresponding to the possible relation graph (i.e., satisfying the profile) at a minimal distance from the potential relation graph (i.e., the initial document specification). This set of relation graphs is thus called adapted relation graph solutions.

% % J J J J J J J J J J J J J J J J J J J J {m,
We consider that the proximity between two relation graphs depends on the proximity between relations borne by the same edge in both graphs. This proximity relies on the conceptual neighborhood between these relations and is measured by the shortest path distance in the corresponding conceptual neighborhood graph (Fig. 3, [START_REF] Freksa | Temporal reasoning based on semi-intervals[END_REF]).

bi

k mi k oi k d d si k d d f k d d di k e k d k d d fi k d d s k d d o k m k b k Figure 3: Allen conceptual neighborhood graph.
Thus, a distance d between relation graphs is obtained by summing up all the conceptual distances δ between relationships used in both graphs (Def. 3).

Definition 3.

d(λ, λ ) = Σo 1 ,o 2 ∈O Min r∈λ( o 1 ,o 2 ), r ∈λ ( o 1 ,o 2 ) δ(r, r )
This approach has been fully defined for the temporal [START_REF] Euzenat | A semantic framework for multimedia document adaptation[END_REF], spatial [START_REF] Laborie | A spatial algebra for multimedia document adaptation[END_REF], spatio-temporal [START_REF] Laborie | Spatio-temporal proximities for multimedia document adaptation[END_REF] and hypermedia [START_REF] Laborie | Adapting the hypermedia structure in a generic multimedia adaptation framework[END_REF] cases.

Our goal is to extend this framework by removing multimedia objects.

REMOVING MULTIMEDIA OBJECTS

As we may notice in Section 3, the adaptation framework considers that the adapted documents contains the same number of multimedia objects as in the initial document. However, it may happen in the target device profile that some multimedia objects are forbidden. We note this set O f (i.e., nodes of relation graph that are forbidden). For example, a mobile profile may express that it is not possible to execute videos. Hence, in Figure 1 the adaptation must remove the videos of the Trailer and the Characters interview, i.e., O f ={Trailer, Characters}.

The general strategy

We propose in this section to extend the adaptation framework described in Section 3 by removing forbidden multimedia objects of the presentation. Two extensions are possible:

• extend the distance defined in Definition 3 by considering relation graphs with different nodes number.

• adapt the document as in Section 3 and remove the forbidden multimedia objects.

We choose the latter as it preserves our distance defined in Definition 3. We propose three steps to remove multimedia objects. Figure 4 presents these steps by adapting Figure 1.

Step 1: For each edge incident to a forbidden multimedia object, label this edge by R. This means that all relations are possible. For the other edges, preserve the relations which satisfy the profile. Step 3: Remove from the adapted relation graphs computed in Step 2 all forbidden nodes of O f and all edges incident to these nodes.

P oster

{m,mi,b,bi} / / {m,mi,b,bi}

% % J J J J J J J J J J J J J J J J J J J J R Abstract R y y t t t t t t t t t t t t t t t t t t t t R ) ) T T T T T T T T T T T T T railer Characters R O O R / / R ? ? Dates {m,mi,b,bi} O O R 5 5 j j j j j j j j j j j j j (a)
Step 1: Possible relation graph. . This execution satisfies the profile and is close to the initial document. However, removing multimedia objects from the initial presentation may introduce gaps, i.e., time intervals where no multimedia objects are executed. For example, in Figure 5 there is a gap between the Abstract and the upcoming Dates.

P oster {m} / / {b} % % J J J J J J J J J J J J J J J J J J J J {b} Abstract {m} y y t t
During adaptation, it could be useful that the adapted document satisfies some properties such as presentation contiguity, because we consider that gaps in a multimedia presentation are not communicating for the end users. Property 1 (Contiguity). Let gs = O, E, λ be a relation graph and O f ⊆ O a set of forbidden nodes. gs satisfies the contiguity property iff it is not possible to find a partition P of two disjoint non-empty sets in O-O f , namely P1 and P2, such that all elements of P1 are bef ore (in the sense of Allen) all elements of P2 (resp., af ter).

P oster {m} / / {b} % % J J J J J J J J J J J J J J J J J J J J {b} Abstract {m} y y t t

Implementation

For a smooth implementation of our adaptation framework, we present the Adapt algorithm (Alg. 1) which computes adapted relation graph solutions. This algorithm is the Nebel backtracking algorithm [START_REF] Nebel | Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-horn class[END_REF], which enumerates consistent relation graphs, enhanced with a Branch and Bound optimization [START_REF] Land | An automatic method for solving discrete programming problems[END_REF] for adaptation.

The relation graph corresponding to potential executions (i.e., the initial document specification) and the one corresponding to possible executions (i.e., the one satisfying the profile) are encoded into two matrix Ii,j and Pi,j.

Before the Adapt(Ii,j, Pi,j) call, we first apply Step 1 on Pi,j and sort each label of the matrix Pi,j according to the distance δ (cf., Section 3) from each label of the matrix Ii,j. We have shown that it is possible to remove multimedia objects with the adaptation framework of Section 3. However, we know in advance which multimedia objects have to be removed. Hence, we propose in the next section a method for summarizing multimedia documents.

SUMMARIZING MULTIMEDIA DOCU-MENTS

Thanks to our extension of Section 4, we want to show in this section that the adaptation can be used to summarize multimedia documents.

Suppose we have this new following profile: only one video is possible in the presentation and multimedia objects cannot be played concurrently. It is difficult to adapt the document of Figure 1 with the strategy described in Section 4 because we do not know in Step 1 which multimedia objects are forbidden, i.e., it could be either the Trailer or the Characters interview.

Thus, we propose to define a preference-based adaptation by giving to each multimedia object a relevance degree inside the document. These relevance degrees are given by the author of the document or computed by the machine. For example, Table 2

% % J J J J J J J J J J J J J J J J J J J J {m,
) ) T T T T T T T T T T T T railer Characters R O O R / / R ? ? Dates {m,mi,b,bi} O O {m,mi,b,bi} 5 5 j j j j j j j j j j j j j (a) Possible relation graph with O f ={Characters}. P oster {m,mi,b,bi} / / {m,mi,b,bi} % % J J J J J J J J J J J J J J J J J J J J R Abstract {m,mi
P oster {m} / / {b} % % J J J J J J J J J J J J J J J J J J J J {b} Abstract {m} y y t t
) ) T T T T T T T T T T T T T railer Dates {bi} O O {mi} 5 5 j j j j j j j j j j j j j (b) Step 3: remove O f = {Characters}. Poster (Image) Abstract (Text) Trailer (Video) Dates (Text)
(c) An adapted document corresponding to the first line of Table 2. In this section, we have shown that the adaptation described in Section 4 can be used to summarize multimedia documents. The proximity between the initial and the adapted document given by the adaptation framework of Section 3

P oster {m} / / {b} % % J J J J J J J J J J J J J J J J J J J
/ / {b} & & L L L L L L L L L L L L L L L L L L L L L L L L L Abstract {m}
x x r r r r r r r r r r r r r r r r r r r r r r r r r

Characters {bi} O O {m} / / Dates {bi} O O (b) Step 3: remove O f = {T railer}. Poster (Image) Abstract (Text) Characters (Video) Dates (Text)
(c) An adapted document corresponding to the second line of Table 2. 2.

helps in this summarization process. Moreover, this approach can be applied to the spatial, spatio-temporal and hypermedia dimensions of documents. We want in the next section to adapt real standard multimedia documents such as SMIL documents [START_REF]W3C. Synchronized Multimedia Integration Language (SMIL 2.0) Specification[END_REF].

APPLICATION TO CONCRETE MULTI-MEDIA DOCUMENTS

We want to validate our adaptation framework on real standard multimedia documents such as SMIL documents [START_REF]W3C. Synchronized Multimedia Integration Language (SMIL 2.0) Specification[END_REF]. We present in Section 6.1 a strategy which generalizes a multimedia document, adapts it with the adaptation framework defined previously, and translates it back to an adapted document. This strategy can be applied to any multimedia document languages or formats. Moreover, it is possible to summarize any kind of concrete multimedia documents and in particular SMIL documents. Finally, in Section 6.2 we present an interactive prototype which allows users to create SMIL documents, specify adaptation constraints and adapt documents.

Concrete documents adaptation

The natural way of using our adaptation framework, presented in the previous sections, for adapting actual documents (D), consists in taking the equivalent qualitative representation of the document D (α), adapting it and translating it back to an adapted document D (β). The strategy presented above, if it is effective, does not apply to a particular multimedia specification language. It must be precised for each particular language. We apply it to SMIL documents.

SMIL is an XML-based language for specifying multimedia presentations [START_REF]W3C. Synchronized Multimedia Integration Language (SMIL 2.0) Specification[END_REF]. The temporal behavior of a SMIL document is not expressed with Allen relations, as used in the previous sections, but time containers and attributes for multimedia objects synchronization.

Hence, the goal of the α function is the extraction of the relational structure involving the multimedia objects and its encoding as a relation graph on which to apply the above defined adaptation operations. This extraction is obtained by the following procedure:

1. extract all multimedia objects and make them a node in the potential relation graph;

2. add an edge between each pair of nodes (they are labeled by a set of relations R);

3. extract the relations implied by the multimedia objects synchronization, e.g., the time containers, the multimedia objects attributes, etc.

Thanks to the qualitative representation built from α, it is thus possible to adapt it with the adaptation framework described in the previous sections, e.g., for summarizing the document. Thereafter, we need to inject the adapted information inside the document.

For that purpose, the β function can be defined in a straightforward manner:

1. remove, if needed, multimedia objects that are forbidden;

2. propagate all adapted constraints from the qualitative adapted representation to the document, i.e., update the multimedia objects synchronization, e.g., the time containers, the multimedia objects attributes, etc.

Prototype

The presented adaptation framework has been implemented in an interactive adaptation prototype. Its architecture is based on Figure 11, and uses Alg. 1 and Alg. 2 to remove and summarize multimedia documents.

The author is able to edit his SMIL document and see the potential relation graph corresponding to his document. Then, it is possible to indicate to the system adaptation constraints (i.e., specify the profile).

On one hand, if the multimedia document does not need to be transformed, the adapted SMIL document is identical to the initial one. On the other hand, if the document needs to be adapted the system presents all adapted relation graph solutions, i.e., those which are at the minimal distance of the initial relation graph and satisfy the profile.

Once an adaptation solution is chosen, the system provides an adapted SMIL document and the user can execute it.

RELATED WORK

The works described in [START_REF] Asadi | Knowledge-based and semantic adaptation of multimedia content[END_REF][START_REF] Lemlouma | The negotiation of multimedia content services in heterogeneous environments[END_REF] adapt SMIL documents. [START_REF] Asadi | Knowledge-based and semantic adaptation of multimedia content[END_REF] adapts the temporal and spatial structure using semantic dependencies between multimedia objects. [START_REF] Lemlouma | The negotiation of multimedia content services in heterogeneous environments[END_REF] seeks to compute efficiently an adapted document satisfying a limited form of adaptation constraints, namely the translation of SMIL documents between the different language profiles (i.e., a form of syntactic restrictions of the different SMIL dialects [START_REF]W3C. Synchronized Multimedia Integration Language (SMIL 2.0) Specification[END_REF]). Our adaptation approach differs in that it operates at a semantical level and is therefore capable of adapting documents in the same language or between different languages or formats. Moreover, our adaptation process produces documents which are as close as possible from the initial ones.

Other approaches for multimedia document adaptation are based on specialized specifications for generating documents such as [START_REF] Scherp | mobileMM4U -framework support for dynamic personalized multimedia content on mobile systems[END_REF][START_REF] Van Ossenbruggen | Cuypers : a semi-automatic hypermedia generation system[END_REF]. However, this requires the content to be initially described with these specifications instead of adapting existing documents.

Moreover, few systems are capable of multimedia document structure summarization. [START_REF] Georgantopoulos | Cross-media summarization in a retrieval setting[END_REF][START_REF] Smith | Scalable multimedia delivery for pervasive computing[END_REF] present some frameworks for SMIL documents. They aim at solving resources adaptation issues and are unable to handle document structure adaptation, especially the temporal dimension of documents.

In contrast, a fair amount of research has been conducted on text summarization. For example, [START_REF] Marcu | Discourse trees are good indicators of importance of text[END_REF] uses rhetorical relations to identify important parts of textual documents.

The results can be used to compute relevance degrees by mapping textual units as multimedia objects.

CONCLUSION

In this paper, we propose an adaptation framework which suppresses multimedia objects and summarizes multimedia documents. This framework is generic, i.e., it can be applied to other multimedia dimensions such as spatial, spatiotemporal and hypermedia. Moreover, this adaptation approach may adapt any multimedia description language. In order to validate the framework, we have implemented a prototype that adapts SMIL documents.

In the future, we plan to refine the adaptation framework by selecting suitable adapted solutions. Indeed, several adapted relation graph solutions can be computed. Currently, it is difficult to select a particular solution from this set because all solutions are close to the initial document. Using the rhetorical structure of multimedia documents, as [START_REF] Rutledge | Generating presentation constraints from rhetorical structure[END_REF] did for generating multimedia content, could be a promising direction for refining our adaptation framework.

Figure 1 :

 1 Figure 1: A multimedia document example.

Figure 2 :

 2 Figure 2: Potential and possible executions.

Figure 4 (Step 2 :

 42 a) presents the possible relation graph of Figure 1 according to the following profile: impossible to execute videos and play multimedia objects concurrently. Adapt the possible relation graph of Step 1 with the adaptation framework described in Section 3. Figure 4(b) presents an adapted relation graph solution. Its distance from the initial relation graph of Figure 2(a) is 1 because the relation between Poster and Abstract changes from o to m (δ(o, m) = 1).

Figure 4 :

 4 Figure 4: Removing multimedia objects.

Figure 5

 5 Figure5presents a possible execution of the adapted relation graph solution of Figure4(c). This execution satisfies the profile and is close to the initial document. However, removing multimedia objects from the initial presentation may introduce gaps, i.e., time intervals where no multimedia objects are executed. For example, in Figure5there is a gap between the Abstract and the upcoming Dates.

Figure 5 :

 5 Figure 5: A possible execution of the adapted relation graph of Fig. 4(c).

Figure 6 :

 6 Figure 6: Removing multimedia objects and satisfying the contiguity property.

Figure 6 Figure 7 :

 67 Figure 6 presents the adaptation steps taking into account the contiguity property. The possible relation graph of Figure 4(a) is still valid (Step 1). Figure 6(a) presents an adapted relation graph solution which satisfies Prop. 1 (Step 2). Its distance from the initial relation graph of Figure 2(a) is 2 because the relation between Poster and Abstract changes from o to m (δ(o, m) = 1) and the relation between Dates and Abstract changes from bi to mi (δ(bi, mi) = 1). The latter transformation is due to the contiguity property of Prop. 1. After removing the forbidden multimedia objects of Figure 6(a) (Step 3), we obtain the relation graph of Figure 6(b). A possible execution of the relation graph of Figure 6(b) is presented in Figure 7. This adapted execution satisfies the profile, the contiguity property and is close to the initial document of Figure 1.

  Possible relation graph with O f ={Trailer }.

Figure 8 :

 8 Figure 8: Possible relation graphs.Thereafter during Alg. 2, we use the Adapt algorithm (Alg. 1) to compute adapted relation graph solutions and preserve the contiguity property. Thanks to the distance d defined in Def. 3, we select in S the summarized documents. Finally, when Alg. 2 stops, we apply on each element of S the corresponding Step 3, i.e., remove the corresponding multimedia objects.

Figure 9

 9 Figure 9 and 10 present different summarizations according to the relevance degrees of Table2. These summarizations satisfy the profile and are close to the initial document.

Figure 9

 9 Figure 9 removes the Characters interview because the relevance degree of the Trailer (i.e., 0.7) is significantly more important than that of the Characters. Hence, there is only one possible matrix in P that minimizes cost(O f ), i.e., the relation graph of Figure 8(a) with cost(O f ) = 0.4. Figure 9(a) presents an adapted relation graph solution computed by Alg. 2. Its distance from Figure 2(a) is 4. Figure 9(b) presents the summarized relation graph removing the Char-

Figure 9 :

 9 Figure 9: Document summarization of Fig. 1 considering the first line of Table2.

Figure 10

 10 Figure 10 removes the Trailer although the relevance degrees of the Trailer and the Characters interview are the same, i.e., 0.5. Two possible matrix in P minimize cost(O f ), i.e., Figure 8(a) and 8(b) with cost(O f ) = 0.5. Figure 10(a) presents an adapted relation graph solution computed by Alg. 2. Its distance from Figure 2(a) is 1. Figure 10(b) presents the summarized relation graph removing the Trailer. Note that, removing the Characters interview introduces more transformations of the document structure than removing the Trailer (Fig. 10(c)). Consequently, this is the reason why the adaptation preserves the Characters interview in the presentation.

Figure 10 :

 10 Figure 10: Document summarization of Fig. 1 considering the second line of Table2.

Figure 11 :

 11 Figure 11: Concrete documents adaptation.

Table 1 :

 1 The thirteen Allen relations.

	1.

  t t t t t t t t t t t t t t t t t t

	O O Characters {bi}	{b} T T T T T T T T T T T T ) ) T railer {oi} 5 5 j j j j j j j j j j j j j O O Dates {mi}
	(a) Step 2: Adapted relation graph satisfying Prop. 1.
		P oster H H H {b} {m} H H H H / / Dates # # H H H H H {mi} H H H H Abstract O O

{m} / / {o} ? ? (b) Step 3: Removing O f ={Trailer, Characters}.

Table 2 :

 2 presents for each multimedia object of Figure1its relevance degree inside the document. In this table, the Poster and the Dates are the most important features of the document. We present in this table two lines, i.e., two different relevance degrees, because we want to show that according to these values the adapted documents summarization can be totally different. Relevance degree of each multimedia object of Figure1.Before the call to Alg. 2, we first compute a set of matrix P, corresponding to possible executions (i.e., satisfying the profile), on which Step 1 is applied and where cost(O f ) is minimal (the cost function sums up each relevance degree of a set of multimedia objects). This initialization of P is used as a filtering technique for selecting good candidates using relevance degrees. Note that in the worst cases, P contains 2 |O| possible relation graphs. It is thus important to introduce filters not to enumerate all possible relation graphs. Figure8presents two possible relation graphs, i.e.,

	Poster Abstract Characters Trailer Dates
	1.0	0.8	0.4	0.7	1.0
	1.0	0.8	0.5	0.5	1.0
	We present in Alg. 2 the Summarize algorithm that uses
	these relevance degrees and Alg. 1 to summarize a multime-
	dia document.
	Algorithm 2: Summarize
	Input: An initial matrix Ii,j corresponding to potential
	executions, a set of matrix P corresponding to possible executions.
	Data: S is a set of adapted relation graphs; S is a set of summarized relation graphs; M in is a current
	minimum computed distance (initialized with a
	high value).
	for all p ∈ P do S = Adapt(I, p); for all s ∈ S do tmp = d(I, s);
	if tmp < M in then
	M in ← tmp; S ← {s}; if tmp = M in then
	S ← S ∪ {s};

  t t t t t t t t t t t t t t t t t t

	O O Characters {bi}	O O Dates {bi}	{m} T T T T T T T T T T T T ) ) T railer {mi} 5 5 j j j j j j j j j j j j j
	(a) Adapted relation graph solution with P={Fig. 8(a)}.
	P oster H H H {b} H {m} H H H H H / / # # H H H H H H H H H

{m} / / {e} ? ? {b} Abstract {m}

  J

		{b}
	Abstract y y t t t t t t t t t t t t t t t t t t t t {m} T T T T T {b} T O O O O T T T T T T ) ) T railer Characters {bi} {m} / / ? ? Dates {bi} {oi} 5 5 j j j j j j j j j j j j j
		{o}
	(a) Adapted relation graph solution with P={Fig. 8(a), Fig. 8(b)}.
	P oster	{m}