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

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

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

Semantic Adaptation of Multimedia Documents

Keywords: Multimedia document transformation, qualitative representation and reasoning, SMIL

Multimedia documents have to be played on multiple device types. Hence, usage and platform diversity requires document adaptation according to execution contexts, not generally predictable at design time. In an earlier work, a semantic framework for multimedia document adaptation was proposed. In this framework, a multimedia document is interpreted as a set of potential executions corresponding to the author specification. To each target device corresponds a set of possible executions complying with the device constraints. In this context, adapting requires to select an execution that satisfies the target device constraints and which is as close as possible from the initial composition. This theoretical adaptation framework does not specifically consider the main multimedia document dimensions, i.e., temporal, spatial and hypermedia. In this paper, we propose a concrete application of this framework on standard multimedia documents. For that purpose, we first define an abstract structure that captures the spatiotemporal and hypermedia dimensions of multimedia documents, and we develop an adaptation algorithm which transforms in a minimal way such a structure according to device constraints. Then, we show how this can be used for adapting concrete multimedia documents in SMIL through converting the documents in the abstract structure, using the adaptation algorithm, and converting it back in SMIL. This can be used for other document formats without modifying the adaptation algorithm.

Introduction

In the near future, mobile access to the Web will surpass personal computer access [START_REF] W3c | Ubiquitous Web Domain[END_REF]. This includes access to multimedia content from mobile phones as well as other emerging environments, such as set-top boxes, PDAs, tablet PCs, interactive television, and even automobiles. However, mobile Web access today still lacks the necessary flexibility needed for the usability of multimedia content on such a variety of devices [START_REF]W3C. Mobile Web Initiative[END_REF].

To tackle this problem there are two possible approaches: either define a device independent multimedia document format, e.g., [START_REF] Kirda | DIWE: A Framework for Constructing Device-Independent Web Applications[END_REF], from which one can generate adapted content encoded in a specific format or define a language, e.g., [START_REF] Ayars | Synchronized Multimedia Integration Language (SMIL 2.0)[END_REF], in which variations of a document can be expressed. The former approach would encode content with this new format but ignore legacy content already found on the web today. The latter requires to anticipate all possible contexts in which a document will have to be played. First, it requires at multimedia content design time the knowledge of all the target devices characteristics on which the content would be rendered in the future. Second, it requires designers to specify a content which would gracefully and seamlessly render correctly on all existing and future devices. In practice, designers produce a very limited set of such adapted content [START_REF] Rabin | Mobile Web Best Practices 1.0. W3C[END_REF]: usually, one for desktop PCs and a second one for mobile terminals. The reason behind this is that they are more comfortable with specific designs tied to particular screen sizes and terminal characteristics. When they create content, they do generally engage in a cyclic process where they specify and check the result directly on a specific terminal. With such a process, it becomes hard to address correctly a richer set of terminals. Furthermore, multimedia documents formats are now defined as a progressively richer sets of sub-languages with increasing features. For example, the SMIL language has several versions [START_REF] Ayars | Synchronized Multimedia Integration Language (SMIL 2.0)[END_REF]: basic, tiny, mobile, advanced mobile and full together with a scalability framework. This will likely make any adaptive design more complex if not impossible without automatic processing.

In an earlier work, we proposed a semantic framework for multimedia document adaptation in which a multimedia document is interpreted as a set of potential executions [START_REF] Euzenat | A semantic framework for multimedia document adaptation[END_REF]. This framework defines adaptations as the search for a document compliant with the device constraints which is as close as possible to the executions specified by the author. It does it in a very general way, independent from the concrete multimedia document languages and independent from the main multimedia document dimensions, i.e., temporal, spatial and hypermedia.

In this paper, we show how this approach can be used for adapting the structure of multimedia documents in concrete multimedia description languages without having anticipated the type of constraints imposed by the devices. For that purpose, we define a structure that captures the spatio-temporal and hypermedia dimensions of multimedia documents. We have developed an adaptation algorithm which transforms in a minimal way such a structure according to device constraints.

Finally, we consider adaptation as a three-step process: (1) abstracting the original content format, followed by [START_REF] Amous | A contribution to multimedia document modeling and querying[END_REF] adapting that abstract representation to the device profile, and (3) producing an adapted version in the same format as the input document (see Figure 1). This approach has many advantages: It allows for defining a device independent format in the form of some abstract relations between multimedia document objects; as new format appears, it can be used by only defining rules for extracting the abstract format from the concrete one and vice-versa. Fig. 1 Multimedia document adaptation strategy: a document in a concrete language is first ( α) expressed as an abstract specification on which adaptation is performed; then, the result is transformed back in the initial format ( α).

The remainder of the paper is structured as follows. Section 2 presents a multimedia document example. In Section 3, we review existing adaptation techniques and how they are used to adapt multimedia documents. In particular, we focus on a semantic adaptation framework proposed in [START_REF] Euzenat | A semantic framework for multimedia document adaptation[END_REF] and how it compares to the other approaches. In Section 4, we extend this framework in order to capture the spatio-temporal and hypermedia dimensions of multimedia documents. In Section 5, we show how to adapt documents semantically in a minimal way according to device profiles. For that purpose, an adaptation algorithm is also described. Finally, in Section 6 we present a prototype for SMIL documents.

A Multimedia Document Example

A multimedia document is an entity that combines pieces of information which come from various media types named multimedia objects (as known as media items) [START_REF] Amous | A contribution to multimedia document modeling and querying[END_REF][START_REF] Roisin | Authoring structured multimedia documents[END_REF]. Typical examples are web documents including synchronized video or audio. Figure 2 represents a multimedia document example played on a laptop. This multimedia document is composed of four images of Athens city, namely Acropolis, Agora, Temple and Museum1 .

Multimedia documents can be modeled through three main dimensions:

-Temporal: Multimedia objects are synchronized temporally, e.g., some objects are played sequentially while others are played simultaneously. -Spatial: Some multimedia objects are organized spatially and displayed in a graphic layout, e.g., two side by side images. -Hypermedia: Links allow for interacting with the presentation and for navigating through its different parts.

In Figure 2, multimedia objects are synchronized temporally, along the presentation timeline, and organized spatially on the screen. They embed two hypermedia links, namely l 1 and l 2 (see the black thick solid lines in Figure 2). For instance, the images named Acropolis and Agora are presented from t = 0s to t = 10s. These images have identical sizes, and are displayed side by side.

Moreover, both images embed one hypermedia link which points to the beginning of the presentation of the two other images, namely Temple and Museum. The hypermedia links may have specific durations corresponding to the period of time when they are clickable or active. Actually, if a user selects l 1 or l 2 , time jumps to t = 10s. This sample multimedia document may be played on other devices, such as PDAs or mobile phones. Figure 3 shows how it is rendered on a PDA. Notice that images are not displayed correctly because the PDA has a smaller display compared to a laptop. This illustrates the need to perform adaptation in order to view this document correctly.

In the following section, we present an overview of current adaptation approaches and compare them with a semantic adaptation framework which was first proposed in [START_REF] Euzenat | A semantic framework for multimedia document adaptation[END_REF]. Fig. 3 The multimedia document presented in Figure 2 played on a PDA.

Related Work

To play a multimedia document correctly on different devices, the document needs to be adapted, i.e., transformed in order to comply with target device constraints. In Section 3.1, we review existing adaptation techniques and highlight some of their limitations. We propose, in Section 3.2, a more general semantic framework for multimedia document adaptation.

Current Multimedia Document Adaptation Techniques

A profile is a description of all the capabilities and limitations of a given terminal [START_REF] Klyne | Composite Capability/Preference Profiles (CC/PP): Structure and Vocabularies 1.0. W3C[END_REF]. Usually, profiles contain the description of both the software and hardware features of a terminal. Software capabilities list, for example, the supported codecs, whether or not the operating system is capable of handling parallel videos or audio streams, etc. The hardware capabilities are given in terms of the physical display size, the input modalities, such as keyboard and pointers. Profiles may also capture user preferences. For example, the user may prefer a particular text magnification for readability purposes. In a more abstract way, a profile can be viewed as a set of constraints on content introduced by profile descriptions. More specifically, for a given multimedia document, the profile imposes constraints on the whole document which in turn can be translated as constraints on each media object or on every pair of media objects contained in it.

For example, a possible profile P may introduce the following constraints:

a Multimedia objects cannot be executed simultaneously.

b Multimedia objects cannot be presented side by side. c A hypermedia link must remain active during its entire presentation.

The sample document of Figure 2 does not comply with the profile P. Actually, the document violates all constraints specified in P. These violations mean that the document cannot be executed correctly on the target device containing the profile P. In order to handle different devices with different profiles, a fair amount of research has been conducted on Universal Multimedia Access (UMA) [38]. Besides, many recent approaches are also focusing on multimodal fission [START_REF] Grifoni | Multimodal fission[END_REF]. Multimodal fission consists of information output arrangement and organization for different interaction devices.

Two types of adaptation are generally considered: adaptation of multimedia objects individually and adaptation of the document structure or composition. This paper focuses on the latter. For that purpose, we group document adaptation approaches into three categories2 : specification of alternatives ( §3.1.1), using transformation rules ( §3.1.2) and multimedia document generation ( §3.1.3).

Specification of Alternatives

During the document edition, an author may specify different document versions, based on its content or target profiles. Several languages allow for specifying different versions of a multimedia document, such as standard multimedia languages, like SMIL [START_REF] Ayars | Synchronized Multimedia Integration Language (SMIL 2.0)[END_REF], or multimedia models, like [START_REF] Hardman | The Amsterdam hypermedia model: adding time and context to the Dexter model[END_REF][START_REF] Rousseau | User adaptable multimedia presentations for the world wide web[END_REF]. For that purpose, they specify alternative channels that are played only if they comply with the target device profile.

As mentioned earlier, it is often tedious to specify all versions for every possible profile. Furthermore, when a document is created, it is difficult to foresee all constraints, in particular those introduced by futures devices.

Using Transformation Rules

To avoid the specification of alternatives, given a target device profile, some systems use transformation rules to select a set of predefined transformations that produce automatically a playable document.

For instance, NAC [START_REF] Lemlouma | The negotiation of multimedia content services in heterogeneous environments[END_REF] (Negotiation and Adaptation Core) is a software infrastructure for multimedia services adaptation and negotiation in heterogeneous environments. It can adapt any HTML and SMIL documents using several media transcoders combined with XSLT transformations for the document structure.

MPEG-21 [START_REF] Bormans | MPEG-21 Overview[END_REF] is an ISO standard which allows for specifying and play adaptable multimedia documents. Many frameworks use MPEG-21 in order to adapt multimedia contents, such as the one described in [START_REF] Jannach | A knowledge-based framework for multimedia adaptation[END_REF] which proposes to compose MPEG-21 semantics-based adaptation services. However, these frameworks are limited to single media content adaptation and do not consider the adaptation of the document composition. The work of [START_REF] Asadi | Knowledge-based and semantic adaptation of multimedia content[END_REF] proposes spatio-temporal transformations applied to MPEG-21 descriptions, especially semantic dependencies between content portions, in order to produce an adapted document. [START_REF] He | A flexible content adaptation system using a rule-based approach[END_REF] proposes another set of transformation rules that can be applied on HTML web pages.

AHA! [START_REF] Bra | The design of AHA![END_REF] adapts the hypermedia dimension only of multimedia documents. This system is mainly based on hypermedia transformation rules described in [START_REF] Brusilovsky | Methods and techniques of adaptive hypermedia[END_REF] and considers three different levels of adaptation: content, navigation and presentation.

The approaches based on transformation rules are usually language dependent. Moreover, it is hard to control the quality of the adaptation at the level of the entire document since the resulting document is obtained by applying the rules iteratively.

Multimedia Document Generation

Other approaches for multimedia document adaptation are based on automatic generation for particular classes of documents. For instance, Cuypers [START_REF] Geurts | Application-specific constraints for multimedia presentation generation[END_REF] is a system that automatically generates Web-based presentations from multimedia databases. It uses a set of abstractions, both on the document and on the presentation level, that are geared towards interactive, time-based and media centric presentations.

MM4U [START_REF] Scherp | MM4U -a framework for creating personalized multimedia content[END_REF] proposes a generic and application-independent framework for supporting multimedia content personalization applications. This framework provides generic components for typical tasks of the general process chain for creating personalized multimedia presentations, i.e., selection, composition, transformation and presentation.

The STAMP model [START_REF] Bilasco | STAMP: a model for generating adaptable multimedia presentations[END_REF] (Synchronized Templates for Adaptable Multimedia Presentations) addresses the dynamic generation of multimedia presentations in the domain of multimedia Web-based information systems. STAMP allows the presentation of multimedia data obtained from XML compatible data sources by means of queries. Furthermore, it proposes templates which are specific document classes to describe the spatial, temporal, navigational structure of multimedia presentations. The instantiation of a template is achieved with respect to the set of spatial and temporal constraints associated with the delivery context.

Despite the fact that these frameworks produce correctly adapted multimedia documents, the generation process requires the documents to be initially described with these templates. These approaches do share the same drawbacks with the device independent format and are limited to some particular classes of documents.

To overcome these drawbacks, we present in the following section a semantic framework for multimedia document adaptation.

A Semantic Framework for Multimedia Document Adaptation

In [START_REF] Euzenat | A semantic framework for multimedia document adaptation[END_REF], a semantic framework for multimedia document adaptation was proposed. This approach is semantic because it is based on interpretations of multimedia documents. In this framework, a multimedia document is interpreted as the set of its potential executions. For instance, in Figure 4, Is corresponds to all possible timelines of the multimedia document presented in Figure 2 (these timelines are themselves abstractions of sets of executions). A model of a multimedia document specification is an interpretation satisfying all the constraints of the document. The set of models Ms of a specification s is thus a subset of the set of interpretations Is. Actually, e 5 is a model (potential execution) which corresponds to the timeline depicted in Figure 2.

The profile of a target device can be used to identify inside Is possible executions, i.e., a set Mp of executions which comply with all constraints specified in the profile. Therefore, "adapting" is reduced to finding the set of potential executions that are possible, i.e., Ms ∩ Mp. When none is possible, i.e., Ms ∩ Mp = ∅, the goal of adaptation is to find executions as close as possible to potential executions that satisfy the profile.

Hence, we distinguish three cases of adaptation illustrated in Figure 4:

-Compliant adaptation when Ms ⊆ Mp; -Refining adaptation when Ms ∩ Mp = ∅; -Transgressive adaptation when Ms ∩ Mp = ∅.

In the following, we bridge the gap between this semantic adaptation theory and its concrete application to standard multimedia documents, such as SMIL documents [START_REF] Ayars | Synchronized Multimedia Integration Language (SMIL 2.0)[END_REF]. In some earlier works [START_REF] Laborie | Spatio-temporal proximities for multimedia document adaptation[END_REF][START_REF] Laborie | An incremental framework for adapting the hypermedia structure of multimedia documents[END_REF][START_REF] Laborie | A spatial algebra for multimedia document adaptation[END_REF], we have proposed some instantiations and extensions of the proposed semantic framework. In this paper, we take the opportunity to combine these contributions. More precisely, we consider the adaptation that deals simultaneously with the spatio-temporal and hypermedia dimensions of standard documents, such as SMIL documents.

An Abstract Description of Multimedia Documents

There are several languages or formats for specifying multimedia documents, such as SMIL [START_REF] Ayars | Synchronized Multimedia Integration Language (SMIL 2.0)[END_REF] or Madeus [START_REF] Layaïda | Madeus : système d'édition et de présentation de documents structurés multimédia[END_REF]. Instantiating the semantic adaptation framework for a specific multimedia document format requires a dedicated adaptation strategy. Instead, we propose an abstraction layer which allows for hiding the specific syntax and details, and capture the essence of a given document with respect to its main dimensions. We call this document abstraction an abstract multimedia document specification. Definition 1 (Abstract multimedia document specification) An abstract multimedia document specification s = O, C is made of a set of objects O and a set of relations (or constraints) C between these objects. In the remainder, the relations will be considered as binary.

For instance, the presentation illustrated in Figure 2 refers to the execution e 5 in Figure 4. This execution satisfies the following (temporal) abstract multimedia document specification: Many other executions could reflect the abstract multimedia document specification s 1 , e.g., with different multimedia object durations. The advantages of adapting semantic multimedia representations are twofold. First, it allows for reusing the same strategy for different formats. Second, the abstract representation provides more flexibility for the adaptation since the relations between objects can be described qualitatively.

In order to capture the spatio-temporal and hypermedia dimensions of the document illustrated in Figure 2, we propose the following definition for the spatiotemporal and hypermedia specification of a multimedia document. A spatio-temporal relation r = r t , rs of C is composed of a temporal relation r t and a spatial relation rs. In this paper, r t refers to Allen relations [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF] and rs refers to RCC8 relations [START_REF] Randell | A spatial logic based on regions and connection[END_REF] (see Figure 5 and6). An abstract multimedia document specification may be represented as a relation graph. In the remainder, we will see that the finite set R refers to all relations of a complete spatio-temporal representation.

The spatio-temporal and hypermedia relation graph of the multimedia document illustrated in Figure 2 is presented in Figure 7. It is composed of 6 objects, i.e., 4 multimedia objects and 2 hypermedia links. Each edge is labeled by a qualitative spatio-temporal relation, e.g., the relation e, DC between Acropolis and Agora means that these objects are played strictly simultaneously and are disconnected spatially.

Acropolis Agora

Temple Museum 7 The spatio-temporal and hypermedia relation graph of the multimedia document illustrated in Figure 2.

l 1 l 2 { e, DC } { m, EQ } { m, DC } { si, EQ } { f i, DC } { m, DC } { m, EQ } { si, DC } { f i, EQ } { e, DC } { bi, EQ } { mi, DC } { bi, DC } { mi, EQ } { m, DC } Fig.
According to the profile P described in Section 3.1, several qualitative relations in Figure 7 are forbidden. For instance, the relation e, DC between Acropolis and Agora violates the constraints a and b of the profile P. Actually, the temporal relation e (equals) is not compatible with the former constraint a because the two multimedia objects are played strictly at the same time, while a indicates that it is forbidden. Moreover, the spatial relation DC (disconnected) does not satisfy the latter constraint b because the two images are presented side-by-side, while b prohibits it.

In this context, the abstract multimedia document specification must be adapted, i.e., the forbidden relations must be replaced by other relations which comply with the constraints specified in the profile. In the following section, we show how to achieve this task by transforming the relation graph in a minimal way.

Adaptation of a Multimedia Document Specification

The semantic adaptation framework requires exploring potential executions to find those satisfying the adaptation constraints, and, if none is found to generate close specifications satisfying the constraints. For that purpose, we first define the notion of closeness through a specific distance ( §5.1), then we describe our algorithm ( §5.2).

Defining a Distance Between Abstract Multimedia Document Specifications

To provide an adapted relation graph, i.e., in which all relations comply with a profile, which is as close as possible from an initial relation graph, we define a distance between two relation graphs that depends on the proximity between relations beared by the same arc in both graphs.

Definition 4 (Distance between two relation graphs)

d(λ, λ ) = n,n ∈O Min r∈λ( n,n ), r ∈λ ( n,n ) δ(r, r )
We consider that the proximity between two relations relies on the conceptual neighborhood between these relations and is measured by the shortest path distance in the corresponding neighborhood graph with δ.

Definition 5 (Conceptual neighborhood) Let x and y be two objects and r(x, y) a relation between x and y. The conceptual neighborhood relation is a binary relation N X R between elements of a set of relations R such that N X R (r, r ) iff the continuous transformation X can transform r(x, y) into r (x, y) without transiting by a third relation r (x, y).

Figure 8 presents a conceptual neighborhood for the Allen temporal relations [START_REF] Freksa | Temporal reasoning based on semi-intervals[END_REF] and Figure 9 presents another conceptual neighborhood for the RCC8 spatial relations [START_REF] Randell | A spatial logic based on regions and connection[END_REF] 3 . These neighborhood graphs allow for computing the distance δ between two temporal or spatial relations.

Definition 6 (Conceptual distance between relations) The conceptual distance δ between two relations is the length of the shortest path between r and r in the graph of N X R .

For example, the distance δ between the bef ore (b) and the overlaps (o) temporal relations is 2 in Figure 8. The distance δ between the disconnected (DC) and the equals (EQ) spatial relations is 4 in Figure 9.

As we consider in this paper spatio-temporal relations, i.e., r = r t , rs , it is necessary to define the distance on such relations. We propose to simply sum the two distances, like in Manhattan distances. It is possible to give more importance to one or another component by choosing a different distance.

Definition 7 (Spatio-temporal distance between relations) Let r 1 = r 1 t , r 1 s and r 2 = r 2 t , r 2 s be two spatio-temporal relations, and N X t and N X s a temporal and a spatial neighborhood graph. The spatio-temporal distance δ(r 1 , r 2 ) = δ t (r 1 t , r 2 t ) + δs(r 1 s , r 2 s ) where δ t is computed from N X t and δs is computed from

N X s .
For instance, δ( e, DC , m, EQ ) = δ t (e, m) + δs(DC, EQ) = 3 + 4 = 7 with δ t and δs computed from the two neighborhood graphs presented in Figure 8 and9.

Other metrics for computing δ can be used together with other neighborhood graphs. However, they must reflect the semantic proximity between two spatiotemporal relations and thus two spatio-temporal and hypermedia specifications.

DC EC PO

EQ

TPPi NTPPi TPP NTPP Fig. 9 A neighborhood graph for RCC8 spatial relations (N T RCC8 ).

Adaptation Algorithm

From an initial relation graph and a given profile, we compute adapted relation graph solutions which are close from the initial one and such that all of their relations satisfy the profile. For that purpose, we consider all possible relation graphs which satisfy a given profile and for each of them we select those which are at the minimal distance from the initial relation graph.

This process has been implemented through the Adaptation algorithm (Algorithm 1). This algorithm extends the Nebel's 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. This faster extension uses a branch-andbound search. The problem of finding consistent relation graphs is known to be NP-complete [START_REF] Gerevini | Qualitative spatio-temporal reasoning with RCC-8 and Allen's interval calculus: Computational complexity[END_REF], however many optimizations and heuristics have been proposed, e.g., [START_REF] Van Beek | The design and experimental analysis of algorithms for temporal reasoning[END_REF] treats matrix elements and relations in privileged orderings, [START_REF] Nebel | Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-horn class[END_REF] groups predefined set of relations and [START_REF] Condotta | Eligible and frozen constraints for solving temporal qualitative constraint networks[END_REF] optimizes the backtracking search with a forward-checking scheme. These algorithm variants can be used to enhance the execution performance of the Adaptation algorithm. The algorithm inputs are two relation graphs: one corresponding to the initial document specification and another one corresponding to possible relations which satisfy a profile. Both specifications are encoded into two matrix I and P , respectively. Before the Adaptation(I, P ) call, we first sort each element Px,y according to the distance δ (Definition 7) from each element Ix,y.

Algorithm 1 computes the consistent possible relation graphs with the help of the pathConsistency function 4 . When the computed relation graphs are consistent, we select the minimal ones with the distance d defined in Definition 4, and store them in S. When Algorithm 1 terminates, the set S contains all adapted relation graph solutions and the variable M in is the minimal distance from the initial document specification.

On the multimedia document of Figure 2, from the initial relation graph presented in Figure 7 and the profile P presented in Section 3.1, Algorithm 1 computes the adapted relation graph illustrated in Figure 10. This adapted relation graph contains only spatio-temporal relations that satisfy all constraints specified in the profile P. Moreover, the distance d between the initial and this adapted relation graph is equal to 52 (this is the minimal distance for satisfying the profile P).

Acropolis Agora

Temple Museum Figure 11 illustrates the execution on a PDA corresponding to the adapted relation graph presented in Figure 10. All constraints specified in the profile P are now satisfied. Additionally, the produced adapted document is close to the initial one because the presentation ordering of multimedia objects has been preserved.

l 1 l 2 { m, EQ } { b, EQ } { b, EQ } { e, EQ } { m, EQ } { m, EQ } { b, EQ } { mi, EQ } { e, EQ } { m, EQ } { bi, EQ } { mi, EQ } { bi, EQ } { bi, EQ } { m, EQ }
We have shown in this section that the semantic framework proposed in [START_REF] Euzenat | A semantic framework for multimedia document adaptation[END_REF] can be extended to combine the spatio-temporal and hypermedia dimensions of abstract multimedia document specifications.

Application to Standard Multimedia Documents

This semantic adaptation framework has to be applied on SMIL documents [START_REF] Ayars | Synchronized Multimedia Integration Language (SMIL 2.0)[END_REF]. SMIL is a W3C recommendation for Synchronized Multimedia documents on the web. It is an XML-based language which enables simple authoring of interactive audiovisual presentations. Moreover, it is the main format used on mobile phone to encode Multimedia Messages (MMS) together with online multimedia services [START_REF]Multimedia Messaging Service Conformance Document[END_REF]. Many applications and players support SMIL documents, e.g., Real Player5 , Ambulant6 , and PocketSMIL7 and virtually every mobile phone supporting MMS. The temporal and spatial behaviors of a SMIL document are not expressed with qualitative relations, as used in the previous sections, but mainly with quantitative values (especially, for the specification of the spatial dimension).

Consequently, the natural way of using the adaptation framework presented in the previous section for adapting actual documents, consists of taking the equivalent qualitative representation of the document (α), adapting it and translating it back to an adapted document (α) as illustrated in Figure 1. The pair of functions α, α have to satisfy natural constraints like: α • α = Id. This strategy can be applied to different multimedia specification languages or formats. Actually, the translation functions α and α must be defined for each particular language. For instance, a SMIL document can be adapted and converted into another multimedia document language, like MPEG-4 BIFS [START_REF] Shao | SMIL to MPEG-4 BIFS Conversion[END_REF].

With respect to our proposed strategy, the goal of the α function is the extraction of the relational structure involving the document 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 hypermedia links, and make them a node in the initial relation graph; 2. add an edge between each pair of nodes (they are labeled by a set of spatiotemporal relations); 3. extract the relations implied by the spatio-temporal and hypermedia dimensions.

Simultaneously, a target device profile is interpreted, like in [START_REF] Lemlouma | Context-aware adaptation for mobile devices[END_REF], in order to identify qualitative and quantitative presentation constraints, such as the screen size or the maximum number of objects that can be played in parallel. Thanks to the profile and the qualitative representation built from α, it is possible to adapt the document representation with the adaptation framework described in the previous section.

Thereafter, we need to inject the adapted information into the document. For that purpose, the α function can be defined in a straightforward manner:

1. compute a quantitative solution from the qualitative adapted representation.

For that purpose, we consider the initial document quantitative values and the adapted computed qualitative relations between objects. The Cassowary Solver [START_REF] Badros | The cassowary linear arithmetic constraint solving algorithm[END_REF], a quadratic optimizer, is then used for computing an adapted quantitative solution. Actually, it computes a quantitative solution close to the initial values that complies with all the given qualitative relations. Quantitative constraints specified in the profile, like the screen size, are also sent to the solver in the form of linear inequalities in order to produce a suitable and playable document; 2. propagate the quantitative solution information into the document, e.g., update the multimedia objects synchronization or the display layout.

The presented adaptation framework has been implemented in an interactive adaptation prototype. The prototype architecture is depicted on Figure 1 and uses Algorithm 1 to produce adapted solutions. Figure 12 presents a screenshot of our prototype. A video screencast is also available at [START_REF] Laborie | A screencast of our SMIL document adaptation prototype[END_REF]. This implementation can adapt multimedia documents in a client-server architecture on the client side, on the server side or on intermediate entities, such as proxies. More precisely, the adaptation mechanism can be fully automated and made transparent to the user. The interactive prototype might also be useful for guiding an author during the document creation for providing feedback on how adaptations may look on particular terminals. Actually, one may specify a profile and if an author creates a forbidden relation between two objects the system could provide other possible configurations close to the initial invalid one which satisfy the given profile. Hence, a user can be assisted, for instance, during the edition of a mobile multimedia document.

Conclusion

Multimedia document adaptation is a very important feature for the continuity of the web experience by users. However, the multiplicity of contexts in which such documents have to be played prevents from leaving this adaptation task to document designers. Document adaptation must then be considered at a more abstract level and be independent from the various document formats.

We have shown how to fill the gap between an abstract semantic framework for multimedia document adaptation and its concrete application on the spatiotemporal and hypermedia dimensions of standard multimedia documents, such as SMIL documents. The originality of this approach is that the adaptation process is flexible and independent of any multimedia description language: only transformation rules have to be defined for dealing with a new concrete language. Moreover, the computed adapted solutions are guarantee to remain close to the initial multimedia document.

Fig. 2 A

 2 Fig. 2 A multimedia document played with Real Player on a laptop.

P rof ile 1 P rof ile 2 P rof ile 3 AdaptationFig. 4 A

 1234 Fig.4A semantic framework for multimedia document adaptation.

s 1 =

 1 {Acropolis, Agora, Temple, Museum}, { Acropolis{=}Agora , // Acropolis and Agora are played at the same time T emple{=}M useum , // Temple and Museum are played at the same time Acropolis{m}T emple , // Acropolis is played just before Temple Agora{m}M useum } // Agora is played just before Museum

Definition 2 (

 2 Spatio-temporal and hypermedia specification) Let Om be a set of multimedia objects and O l a set of hypermedia links. A spatio-temporal and hypermedia specification s = O, C is composed of a set of objects O with O = Om ∪ O l and a set of spatio-temporal relations C between the elements of O.

Fig. 5 Fig. 6 Definition 3 (

 563 Fig.5The Allen interval algebra (13 temporal relations).

Fig. 8 A

 8 Fig.8A neighborhood graph for Allen temporal relations (N A A 13 ).

Fig. 10

 10 Fig. 10 An adapted relation graph in which all relations comply with the profile P.

2 Fig. 11

 211 Fig.11An execution, played on a PDA, which corresponds to the adapted relation graph presented in Figure10.

Fig. 12

 12 Fig. 12 Screenshot of our SMIL document adaptation prototype.

Algorithm 1 :

 1 AdaptationInput: An initial matrix I corresponding to the initial relation graph and a matrix P corresponding to relations that satisfy all constraints specified in a profile. Data: M in is a current minimum computed distance (initialized with a high value). Output: S is a set of adapted relation graphs. pathConsistency(P ); if P does not contain an empty relation then Choose an unprocessed label Px,y and split Px,y into rz = r 1 , . . . , rn;

	if no label can be split then
	tmp ← d(I, P );
	if tmp < M in then
	M in ← tmp;
	S ← {P };
	end
	if tmp = M in then
	S ← S ∪ {P };
	end
	end
	else
	for all labels rz (1 ≤ z ≤ n) do
	Px,y ← rz;
	if d(I, P ) ≤ M in then
	Adaptation(I,P );
	end
	end
	end
	end

During the presentation, a narrative audio content commenting the images is played in parallel, however to avoid visual overloading we do not consider it in this paper.

Our proposed classification extends the one presented in[START_REF] Lei | Context-based media adaptation in pervasive computing[END_REF], especially the static and dynamic adaptation cases.

The used continuous transformations are defined in[START_REF] Freksa | Temporal reasoning based on semi-intervals[END_REF] for the Allen relations and in[START_REF] Randell | A spatial logic based on regions and connection[END_REF] for the RCC8 relations.

A path consistency function was preliminary defined for qualitative Allen temporal relations in[START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF].

http://www.real.com/international/

http://www.cwi.nl/projects/Ambulant/

http://wam.inrialpes.fr/software/pocketsmil/


Maria Roşoiu

Cássia Trojahn

Jérôme Euzenat

Ontology matching benchmarks: generation and evaluation

Keywords: Ontology matching, Matching evaluation, Test generation, Semantic web

The OAEI Benchmark data set has been used as a main reference to evaluate and compare matching systems. It requires matching an ontology with systematically modified versions of itself. However, it has two main drawbacks: it has not varied since 2004 and it has become a relatively easy task for matchers. In this paper, we present the design of a modular test generator that overcomes these drawbacks. Using this generator, we have reproduced Benchmark both with the original seed ontology and with other ontologies. Evaluating different matchers on these generated tests, we have observed that (a) the difficulties encountered by a matcher at a test are preserved across the seed ontology, (b) contrary to our expectations, we found no systematic positive bias towards the original data set which has been available for developers to test their systems, and (c) the generated data sets have consistent results across matchers and across seed ontologies. However, the discriminant power of the generated tests is still too low and more tests would be necessary to draw definitive conclusions.

Introduction

Evaluating ontology matching may be achieved in several ways. The most common one consists of providing matchers with two ontologies and comparing the returned alignment with a reference alignment [START_REF] Euzenat | Ontology alignment evaluation initiative: Six years of experience[END_REF]. However, this raises the issue of the choice of ontologies and the validity of the reference.

Since 2004, the Ontology Alignment Evaluation Initiative (OAEI) 1 makes available a collection of data sets for evaluating matching systems. One such data set is Benchmark. It is a well-defined set of tests in which each test is composed of two ontologies and a reference alignment. The tests are based on one particular ontology, from the bibliographic domain, and systematic alterations of this ontology, e.g., removing classes, renaming properties.

Benchmark was designed with the aim of covering the problem space, i.e., the various situations in which a matcher may be. However, this data set has various drawbacks: (a) lack of realism: tests are mechanically generated and cover a systematic alteration space, (b) lack of variability: it always uses the same seed ontology altered in the exact same way, and (c) lack of discriminability: the tests are not difficult enough to discriminate well matchers.

We are not particularly interested in Drawback (a) because it has been overcame by other data tests made available by OAEI. We focus on drawbacks (b) and (c). To that extent, we have developed a test generator that may be used with any seed ontology and allows for fine tuning the input parameters, as well as randomized modifications over the ontology entities. A byproduct of this generator is that it enables us to evaluate the relevance of the Benchmark dataset: by reproducing this dataset and using it to evaluate different matchers in the same conditions, we can assess how much the results obtained are dependent on the particular seed ontology or the particular matcher.

We run different matchers on the generated tests, which allows us to draw conclusions on the results obtained so far with Benchmark:

-The difficulties encountered by a matcher at a test are preserved across the seed ontology, hence, Benchmark is relevant. -Matchers have, in general, no better results with the original Benchmark than with the new generated data sets, this goes counter our expectation that, because tests and results were available, matchers would perform better. -Matcher results are generally consistent across seed ontologies and ontology results are generally consistent across matchers, but with low discrimination. This confirm that the lack of discriminability is due to Benchmark and not to the seed ontology.

The rest of the paper is structured as follows. In Section 2, we present the state-of-the-art in ontology matching test generation. In Section 3, we present the architecture of our test generator and the strategy we came with in order to reproduce the Benchmark dataset. In Section 4, we expose the results we have obtained with new generated datasets and their variability. Finally, the conclusions and future work are presented in Section 5.

Ontology matching evaluation and test generation

In this section, we briefly present the current setting of ontology matching evaluation (Section 2.1), the Benchmark data set (Section 2.2) and the state-of-theart in alignment test generators (Section 2.3). The interested reader can find a broader overview of ontology matching evaluation in [START_REF] Euzenat | Ontology alignment evaluation initiative: Six years of experience[END_REF].

Evaluating ontology matching systems

Matching can be seen as an operation which takes as input two ontologies (o and o ′ ), a set of parameters (p), a possibly empty partial alignment (A ′ ) and a set of resources (r) and outputs an alignment (A) between these ontologies (Fig. 1).

An alignment can be defined as a set of correspondences. A correspondence between two ontologies o and o ′ is a triple e, r, e ′ , where e is an entity belonging to the first ontology, e ′ is an entity belonging to the second ontology, r is a relation, e.g., equivalence or subsumption, between them. Fig. 1: Ontology matching process and evaluation (from [START_REF] Euzenat | Ontology matching[END_REF]).

A matcher can be evaluated comparing its output alignment (A) with a reference alignment (R) using some measure (Fig. 1). Usually, such measures are precision, recall and F-measure [START_REF] Euzenat | Ontology matching[END_REF]. Thus, in order to evaluate a matching system, one has to generate datasets in which a test is composed of two ontologies to be matched (o and o ′ ) and a reference alignment (R).

The Benchmark dataset

Benchmark aims at testing the strengths and the weaknesses of matching systems, depending on the availability of ontology features. This dataset has 111 tests, requiring to match an ontology written in OWL-DL to another one:

-Tests 1xx -compare the original ontology with itself, a random one and its generalization in OWL-Lite. -Tests 2xx -compare the original ontology with the ontology obtained by applying the following set of modifications to it (Fig. 2):

• names (naming conventions: synonyms, random strings, different generalization, translation into other language) • comments (no comments) • hierarchy (flattened hierarchy / expanded hierarchy / no specialization) • instances (no instance) • properties (no properties, no restrictions) • classes (flattened classes / expanded classes) -Test 3xx -compare the original ontology with real ones found on the web. Since 2004, Benchmark has been generated from the same seed ontology through the same set of XSLT stylesheets. This means, in particular, that no random modification is applied to these ontologies: the same 20% of classes are renamed and this renaming is always the same. This has advantages for studying the evolution of the field, because the test is always the same.

However, the Benchmark data set can be criticised on three main aspects: Fig. 2: The Benchmark lattice -the higher the test is in the hierarchy, the easier it is. Tests in dashed lines are not reproduced in the tests we used here (see §4).

Lack of realism Benchmark is not realistic because it covers a whole systematic space of mechanical alterations and in reality a matcher is not faced with such a space. Lack in variability Benchmark always produces the same data set hence it is not variable. This covers three slightly different kinds of problems: (a) it can only be used with one seed ontology, (b) it always applies the same transformations (to the same entities), instead of applying them randomly, and (c) it is not flexible in the sense that it is not possible to produce an arbitrary test (such as 12% renaming, 64% discarding properties). Lack of discriminability [START_REF] Giunchiglia | A large scale dataset for the evaluation of ontology matching systems[END_REF] Benchmark seems in general easy enough to OAEI participants so that they do not really allow them to make progress and to compare them. This is because, many of the proposed tests are easy and only a few are really difficult.

Our goal is to address variability and discriminability by producing a test generator (a) independent from the seed ontology, (b) with random modifications, and (c) which allows to fine tune parameters in order to cover the alteration space with any precision. With such a test generator it would be possible to generate different tests than Benchmark focusing on particular application profiles or particularly difficult cases.

We do not address the lack of realism because Benchmark has been designed to cover the problem space and not to offer one realistic profile2 . Other initiatives, such as other tracks of OAEI and other generators, address this issue.

Other ontology alignment generators

So far, some alignment test generators have been developed.

An ontology generator inspired by Benchmark is the one developed in [START_REF] Besana | Predicting the content of peer-to-peer interactions[END_REF]. Its seed ontology is a random tree which is computed using a Gaussian distribution with average 4 and deviation 4 in order to determine the number of children per node. The second ontology is obtained from the first one by applying a set of alterations, similar to the ones used in Benchmark, such as label replacement, word addition or removal in labels, node deletion and node child addition and children shuffling. Then, these two generated ontologies are used to generate alignments between them. The aim of generating the original ontology is to perform realistic tests and to allow a wider coverage of variations in their structure.

The generator proposed in [START_REF] Tournaire | Découverte automatique de correspondances entre ontologies[END_REF] satisfies two requirements: (a) to generate the structure and the instances of two taxonomies, and (b) to generate the mappings between these two generated taxonomies. Both taxonomies must have a fixed size and a Boltzmann sampler is used to achieve this. The probabilistic model used ensures an equal probability of appearance of a tree having a given size. Therefore, the input data is controlled using this sampler. The number of child nodes is controlled as well. Then, the mappings between the two taxonomies are generated, which must not be contradicted by the generated data. To achieve this goal, three constraints were enforced: the mappings must not introduce a cycle in the newly obtained graph (the mappings and the two given taxonomies), the mappings must not contradict the knowledge of the two taxonomies and they must not entail each other. In the end, instances are generated.

The TaxMe method [START_REF] Giunchiglia | A large scale dataset for the evaluation of ontology matching systems[END_REF] is build from existing directories and only approximates the reference alignment, it is not really a generator. In XML schema matching, STBenchmark [START_REF] Alexe | STBenchmark: towards a benchmark for mapping systems[END_REF] offers a way to generate one precise test (pair of schemas) by altering a source schema based on the combination of 11 base alterators. Their combination is defined through a set of input parameters. Swing [START_REF] Ferrara | Benchmarking matching applications on the semantic web[END_REF] takes a similar approach as Benchmark and introduces a new interesting way of altering ontologies by using patterns. However, it is not an automatic generator and it is aimed at generating instance data: the same ontology is, in the end, used for all tests.

We decided to rewrite our own generator because we wanted to reproduce Benchmark first. Tournaire's generator was not suited because he was aiming at realism; Besana's generator would have been useful but was not available.

A modular benchmark test generator

We developed a test generator in Java based on the Jena API3 . We present the principles of the generator (Section 3.1) and the testing strategy (Section 3.2).

Generator principles

Test generator architecture. The basic principles of the test generator is that, from one ontology, it can generate an altered one and an alignment between these two ontologies. The generator can as well accept a generated ontology, that is useful for generating scalability tests.

Because the alterations may be applied in sequence, we designed an alterator module taking as input an ontology and an alignment between this ontology and the seed ontology. This module outputs an altered ontology and an alignment between this ontology and the seed one (Fig. 3). Test generator parameters. In order to assess the capability of matchers with respect to particular ontology features, we consider the following alterations: remove/add percentage of classes; remove/add percentage of properties; remove percentage of comments; remove percentage of restrictions; remove all classes from a level; rename percentage of classes; rename percentage of properties; add a number of classes to a specific level; flatten a level; remove individuals. Generating a dataset. For modifying an ontology according to a set of parameters we use the generator as illustrated in Fig. 4. It receives as input the seed ontology and the parameters which represent the alterations to be apply. The output is the modified ontology and the reference alignment. The program is implemented in a serial manner.

The test generator can be also used to reproduce data sets such as Benchmark. For that purpose, the program will either generate all the required tests independently by running in parallel the necessary composition of alterators (Fig. 5, left) or generate them in sequence, as the initial Benchmark data set, i.e., by using a previous test and altering it further (Fig. 5, right). In the latter case, this corresponds to selecting paths in the lattice of Fig. 2 which cover the whole data set. This approach may also be used to generate complete data sets covering the whole alteration space with a varying degree of precision (incrementing the alteration proportion by 50% or by 2%).

Preliminary experiments

Before evaluating matchers on the generated data sets, we have tested the generator through unit tests, checking if the percentage of alteration was indeed respected. Initially, the parameters were applied in a random order, using the bibliographic ontology as basis. From the results, we noticed a non expected matcher behaviour, that allowed us to improve the generation strategy. Random vs. continuous policies. Contrary to expected, matchers did not had a continuous degradation of their performances as more alterations were applied. This made difficult to read one Benchmark test result, as developers would like to read them. This is the consequence of generating the dataset fully randomly (Fig. 5, left), where each test is generated independently from the others. In this modality, some tests with more alterations may be easier than other with less alterations by chance.

We validated this explanation by generating continuous tests (Fig. 5, right) as Benchmark were generated. In this case, new tests are generated from previous ones with the modular architecture of the generator. This behaviour is only observable locally, i.e., on one data set. When generating randomly several datasets, matcher behaviours are on average continuous. In results reported below, half of the tests were obtained with the random generation and half of them with continuous generation. Their results are the same (within 1 percentage point variation). Modification dependencies. We observed that test difficulty may not be the same across tests supposed to have the same amount of alteration. This is explained by the dependency between alterations. Consider, for example, a scenario in which we would like to remove 60% of classes and to rename 20% of classes. According to these two parameters, three extreme cases may happen (as illustrated in Fig. 6):

rename 20% of classes and then remove 60% of classes, including all renamed classes. In this situation, the test is easier than expected because all renamed classes have been removed; -rename 20% of classes and then remove 60% of classes, including a part of renamed classes. In this situation, the test is as hard as expected because the required proportion of the renamed classes have been removed. -rename 20% of classes and then remove 60% of classes, without removing a renamed class. In this situation, the test is harder than expected because none of the renamed classes has been removed. Hence, a random disposition of parameters might reduce the really hard cases. As can be seen from the example, the nominal expected case may be restored by removing 60% of the classes before renaming 20% of the remaining. Therefore, we established a relevant order for parameters: remove classes, remove properties, remove comments, remove restrictions, add classes, add properties, rename classes, rename properties. In this way, we obtained the expected results. This order helps determining the paths in Fig. 2 used for generating Benchmark. Such an order was not previously observed in the Benchmark tests because the value of parameters, except rename resources, was set to the value of 100%.

Benchmark validity

In order to test the validity of the Benchmark dataset principles, we used the test generator to reproduce them with different characteristics. Three modalities were used in the evaluation:

1. Regenerate the dataset using the same bibliographic ontology (biblio). 2. Generate datasets from two conference ontologies [START_REF] Šváb | Ontofarm: Towards an experimental collection of parallel ontologies[END_REF] (cmt and ekaw), of similar size and expressiveness as biblio. 3. Generate datasets from other ontologies of two other domains (tourism4 and finance 5 ).

These modalities were chosen because we assume that since participants have had the opportunity to test their systems with the original Benchmark, their results may be higher. The same holds for the conference dataset that these systems had the occasion to deal with, while the third group of tests is new for them. We thus expected them to be harder. We could evaluate the robustness of our generator, since the finance ontology has more than 300 classes and almost 2000 individuals.

In order to remove the possibility that the obtained results are an artifact of the generated test, we ran the tests five times for each method (continuous and random) and then we computed the average among the obtained results. Likewise, the tests are the same at each run (these tests are 201-202, 221-225, 228, 232-233, 236-241, 246-254, 257-262, 265-266). We decided not to reproduce the ones in which the labels are translated into another language or the ones in which the labels are replaced with their synonyms, because the corresponding alterators are not sufficiently good. The same algorithms with the same parameters have been used for all tests (the tests with the original Benchmark have been run again). In total, the results of this section are based on the execution of (1+(5 ontologies × 5 runs × 2 modalities) × 102 tests × 3 matchers =) 15606 matching tasks, i.e., a matcher has been run against a pair of ontologies and the result has been evaluated against a reference alignment.

Matchers

To test the generator, we used three different matchers participating in previous OAEI: Aroma, Anchor-Flood (Aflood) and Falcon-AO (Falcon). They are stable enough and generally available, yet sufficiently different.

Anchor-Flood tries to find alignments starting with some anchors and using the locality of a reference (super-concepts, sub-concepts, siblings, etc.) [START_REF] Hanif | Anchor-flood: Results for OAEI 2009[END_REF]. It is composed of two modules. The first one uses lexical and statistical information to extract the initial anchors. Then, starting with these anchors, it builds small blocks across ontologies and establishes the similarities between the two found blocks. Each similarity is stored in a partial alignment and, the process continues using as anchors the pairs found in the partial alignment. The process finishes when no more correspondences are found. We have used the preliminary OAEI 2010 version of Aflood.

Aroma [START_REF] David | Association rule ontology matching approach[END_REF] is divided in three stages. First, it builds a set of relevant terms for each entity, i.e. class or property. In order to achieve this, a single and binary term extractor applied to stemmed text is used to extract the vocabulary of a class or a property. In the second stage, the subsumption relations between entities are found using the implication intensity measure and an association rule model. Third, it establishes the best correspondence for each entity deducing first the equivalence relations, then suppressing the alignment graph cycles and the redundant correspondences. We have used Aroma 1.1.

Falcon-AO [START_REF] Hu | Matching large ontologies: A divide-andconquer approach[END_REF] is composed of two matchers: a linguistic (LMO) and a structural matcher (GMO). The linguistic matcher has two parts. The first one uses string comparisons and the second one uses virtual documents to describe each ontology entity. A virtual document is a "bag of words" containing the name, the comments, the labels and also neighbors names or labels of an entity. Vector space techniques are employed to measure the similarity between these virtual documents. The structural matcher represents an ontology as a bipartite graph and tries to find the similarity between the two input ontologies. In the end, if the result returned by the linguistic matcher is satisfying, it is returned. Otherwise, the structural matcher result is returned. We have used Falcon-AO 0.3.

Results

Table 1 provides the aggregated precision, recall and F-measure for each matcher and each data set. We discuss them only from the standpoint of F-measure because it allows for a more direct comparison. 1: Average results (on 5 random and 5 continuous runs) for the 2xx Benchmark series for the three matchers and six data sets.

First, we observed independently that the difficulties encountered by a matcher at a test are preserved across the seed ontology. Hence, Benchmark is useful for identifying weaknesses in matchers. What we mean here, is that by looking at the results, test by test, the relative performance of test for a matcher is preserved across seed ontologies. This is not visible in Table 1.

Then, for most of the matchers, the results obtained with the original Benchmark are not the highest. This goes counter our expectation of a positive bias in favour of the original Benchmark. In fact, the results are contrasted since Aflood has a significantly better score than with the reproduced Benchmark, Aroma has its worse score and Falcon has a very close score. It seems that the original Benchmark is quite hard because for two matchers, results are better on the (randomised) reproduced Benchmark. Original Benchmark results, even if they do not show a systematic positive bias, seems to be the outlier.

The two other groups of tests, ekaw and cmt on one hand and tourism and finance on the other hand, have homogeneous results within the group and different results across groups. This indicates that the type of seed ontology has an influence on the results but for ontologies of the same type results are homogeneous. It seems that biblio is harder than conference which is harder than tourism-finance and this for all matchers (but Falcon).

But overall, results are found in the same range. If we exclude the results of Aflood and Aroma on the original Benchmark, the results of matchers vary of 11, 9 and 8 percentage points respectively.

Similarly, the order between matchers observed with the original Benchmark seems to be preserved in four out of six data sets. Surprisingly, the main outlier is the reproduced Benchmark. However, the few percentage point difference that is observed do not allow us to conclude, especially with respect to the 24 percentage points observed for the original Benchmark and the 10 percentage points in reproduced Benchmark.

What we observe is a relative homogeneity of these results: there is no more diversity across matchers than across data sets. In fact, the lack of discriminability observed in Benchmark is even reinforced in the other tests: the original Benchmark has 24 percentage points span while the reproduced biblio has only 10 points and the other data sets are lower. Hence, this is a property of the alterations generating Benchmark, thus another type of generation should be used.

Conclusion

In this paper we have looked for improving the tools available for evaluating ontology matchers. For that purpose, we have developed a test generator which follows a simple modular architecture and API. This generator does not depend on the seed ontology. It allows different modifications at each run of the program and the set of input parameters can be adjusted in order to cover the problem space with any precision. The generator can be extended by adding new ontology modifier modules and it can be used for generating individual tests with controlled characteristics as well as full data sets. Thus, we have largely improved the variability of generated tests.

The test generator was used to reproduce the Benchmark dataset not only for the bibliographic ontology, but for other ontologies with different structures. We observed that the obtained results are not better on original Benchmark than on new and different ontologies. This contradicts the assumption that there is a systematic positive bias towards Benchmark.

We observed that for the same type of seed ontology, each matcher has homogeneous results and that the order between matchers obtained on the original Benchmark (Aflood, Falcon, Aroma) was preserved in four cases out of six. However, the difference between systems is too small to draw definitive conclusions. The new tests still lack discriminability. It is thus a feature of the Benchmark generation modalities.

We plan to improve these experiments by using other matching systems. This can be achieved using the SEALS platform and it is planned for the OAEI 2011 campaign for which the generator will be used. We may also use different more difficult generation modalities, in order to increase discriminability. Another perspective is to use the test generator for exploring the notion of test hardness, that could help to better approach the lack of discriminability.

Fig. 3 :

 3 Fig. 3: Modular structure of test generators.

Fig. 4 :

 4 Fig. 4: Modular one-shot test generation.

Fig. 5 :

 5 Fig. 5: Random (left) and continuous (left) test suite generation.

Fig. 6 :

 6 Fig. 6: Test dependency.

Table

  Aflood .99 .87 .78 .75 .67 .59 .95 .72 .58 .95 .72 .58 .94 .76 .62 .96 .78 .66 .75 Aroma .79 .63 .53 .86 .68 .55 .92 .65 .50 .96 .68 .52 .85 .74 .64 .94 .73 .60 .68 Falcon .83 .76 .70 .85 .77 .70 .82 .69 .59 .89 .70 .57 .83 .73 .65 .92 .77 .66 .74

		original	biblio	cmt	ekaw	tourism	finance	Σ
		P F R P F R P F R P F R P F R P F R F
	Average	.74	.71	.69 .	.70	.74	.76	72

http://oaei.ontologymatching.org/

One reviewer argues that we currently consider an alteration space, instead of a problem space, which assumes some realism, i.e., that these problems actually occurs. Moreover, (s)he write that we choose the kind of alteration and the granularity. This is right. But this alteration space is our attempt to cover, and not to represent, the problem space.

http://jena.sourceforge.net/ontology/index.html

http://www.bltk.ru/OWL/tourism.owl

http://www.fadyart.com/ontologies/data/Finance.owl

Acknowledgements

This work has been partially supported by the SEALS project (IST-2009-238975).


Franc ¸ois Scharffe
email: francois.scharffe@lirmm.fr

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

LINKED DATA MEETS ONTOLOGY MATCHING Enhancing data linking through ontology alignments

Keywords: semantic web, linked data, data linking, ontology alignment, ontology matching, entity reconciliation, object consolidation

The Web of data consists of publishing data on the Web in such a way that they can be connected together and interpreted. It is thus critical to establish links between these data, both for the Web of data and for the Semantic Web that it contributes to feed. We consider here the various techniques which have been developed for that purpose and analyze their commonalities and differences. This provides a general framework that the diverse data linking systems instantiate. From this framework we consider the relation between data linking and ontology matching activities. Although, they can be considered similar at a certain level (they both relate formal entities), they serve different purposes: one acts at the schema level and the other at the instance level. However, they would find a mutual benefit at collaborating. We thus present a scheme under which it is possible for data linking tools to take advantage of ontology alignments. We present the features of expressive alignment languages that allows linking specifications to reuse ontology alignments in a natural way.

INTRODUCTION

The Web of data is the network resulting from publishing structured data sources in RDF and interlinking these data sources with explicit links. Web datasets are expressed according to one or more vocabularies or ontologies, which range from simple database schema exposure to full-fledged ontologies.

The Web of data requires to interlink the various published data sources. Given the large amount of published data, it is necessary to provide means to automatically link those data. Many tools were recently proposed in order to solve this problem, each having its own characteristics.

In many cases, datasets containing similar resources are published using different ontologies. Hence, data interlinking tools need to reconcile these ontologies before finding the links between entities. This could be done automatically, but more often this is done manually and built in the link specifications. This has two drawbacks: (a) this prevents to reuse the work made in ontology matching for reconciling ontologies and (b) the information about reconciling the ontologies is mixed with the information about how to identify entities.

Hence, the goal of this work is to consider data interlinking and ontology matching and to determine how these two activities are related and how they could better cooperate.

For that purpose, after briefly introducing the challenges of data interlinking and ontology matching (Section 2), we provide a general framework for data interlinking (Section 3). This framework clearly separates the data interlinking and ontology matching activities and we show how these can collaborate through three different languages for links, data linking specification and ontology alignment. We provide examples of an expressive alignment language and a modified linking specification language that can implement this cooperation (Section 4).

An extended version of this paper is available as a technical report [START_REF] Scharffe | MeLinDa: an interlinking framework for the web of data[END_REF].

WEB OF DATA, DATA INTERLINKING, AND ONTOLOGY ALIGNMENT

We briefly introduce the data interlinking problem. We provide examples of this problem and why it would require specific linking tools. We then present why these tools could take advantage of ontology matching and alignments.

The main problem on the Web of data is to create links between entities of different datasets. Most often, this consists of identifying the same entity across different datasets and publishing a link between them as a sameAs statement. We call this task data interlinking and summarize it in Figure 1. Once identified, the links discovered between two datasets must also be published in order to be reused. The VoiD vocabulary [START_REF] Alexander | Describing linked datasets -on the design and usage of void, the 'vocabulary of interlinked datasets[END_REF] allows for describing linksets as special datasets containing sets of links between resources of two given datasets. Once linksets are constructed, two approaches are proposed to retrieve equivalences between resources: it is possible to assign to each real world entity a global identifier that will then be related to every URIs describing this entity. This is the approach taken in the OKKAM project [START_REF] Bouquet | An Entity Naming System for the Semantic Web[END_REF] that proposes the usage of Entity Name Servers taking the role of resource name repositories. The other approach uses equivalence lists maintained with interlinked resources across datasets. There is thus no global identifier in this approach but equivalence links can be followed using a third-party Web service, e.g., http://sameas.org, or a bilatteral protocol [START_REF] Volz | Web of data link maintenance protocol[END_REF].

The data interlinking task can be achieved manually or with the help of data interlinking tools. These tools take as input two datasets and ultimately provide a linkset. In addition, they use what we call a linking specification, i.e., a "script" specifying how and/or what to link. Indeed, given dataset sizes, the search space for resources interlinking can reach many billion resources, e.g., DBPedia. It is thus necessary to use heuristics giving hints to the interlinking system where to look for the corresponding resources in the two datasets. These linking specifications can be specific to a pair of datasets and can be reused for regenerating linksets (we provide an example of such a specification in the Silk language in Section 4).

Mining for similar resources in two Web datasets raises many problems. Each datasets having its own namespace, resources in different datasets are given different URIs. Also, although naming conventions exist, there is no formal nor standard way of naming resources. For example, if we take the URI for the fa-mous musician Johann Sebastian Bach in various Web datasets we obtain very different results even though they all represent the same real world object.

Fortunately, dereferencing URIs can be used for retrieving more information about entities: property values and related resources can be observed. But for a same real-world entity, the same property can take different values, making the interlinking process more difficult. This can be because of varying value approximations across datasets, because of different units of measure, because of mistakes in the datasets, or because of loose ontological specifications. For instance, the property foaf:name does not specify in what format should the name be given. "J.S. Bach", "Bach, J.S." or "Johann Sebastian Bach" are possible values for this property. Hence, data interlinking tools have to compare property values in order to decide if two entities are the same, and must be linked, or not. For that purpose, tools use similarity measures based on the type of values (e.g., string, numbers, dates) and aggregate the results of these measures. This activity is reminiscent of record linkage which has been given considerable attention in database [START_REF] Fellegi | A theory for record linkage[END_REF][START_REF] Winkler | Overview of record linkage and current research directions[END_REF][START_REF] Elmagarmid | Duplicate record detection: A survey[END_REF].

Another problem is caused by the usage of heterogeneous ontologies for describing datasets. In this case, a same resource is typed according to different classes and described with different RDF predicates belonging to different ontologies. For example, a name in a dataset can be attributed using the foaf:name data property from the FOAF ontology while it is attributed using the vcard:N object property from the VCard ontology in another dataset.

Hence, for the interlinking techniques to work, it is necessary that the datasets use the same ontology or that data interlinking tools are aware of the correspondences between ontologies.

The goal of this paper is to investigate the relationships between data interlinking and ontology matching [START_REF] Euzenat | Ontology matching[END_REF]. In particular, we want to understand if these two activities would benefit to be merged into a single activity and sharing the same formats.

A FRAMEWORK FOR DATA INTERLINKING

We provide in this section a general framework encompassing the various approaches used to interlink resources on the Web of data. We first consider each case that may happen when interlinking data and describe them abstractly and through an example. In the end, we unify all this cases in a common framework.

In the first case resources are manually interlinked. Manually linking resources can be performed using collaborative tools in the case of large datasets. In some cases, illustrated below, resources can be trivially linked using a simple transformation of their URIs. A set of rules can be defined to identify equivalent resources from their identifier. For example, in the dataset LastFM 1 , the URI representing an artist is built on the pattern "First name+Last name". Person URIs in DBPedia 2 are built around the pattern "FirstName LastName". A trivial algorithm can be developed to find equivalent artists based on their URIs.

Further that the URIs, it may be necessary to consider the ontologies in order to identify entities. In a first case, the two datasets to interlink are described by the same ontology. The role of the interlinking system is to analyze resources of the same type in order to detect the equivalent ones. To do this, the system compares resource properties with a similarity measure. Systems in this category take as input the properties to compare, the type of comparison algorithm to use for each property, and the method to aggregate the similarity measures of the various properties in order construct a measure between two resources. For example, Jamendo and MusicBrainz, two datasets containing musicological data, are both described according to a common music ontology [START_REF] Raimond | The music ontology[END_REF]. The artist J.S. Bach can be identified in both datasets by observing the first name and 1 http://last.fm 2 http://dbpedia.org last name properties of the class MusicArtist. It is not possible in this case to identify the equivalence of resources based on their URIs. This example is illustrated in Figure 4. Datasets can be described by different ontologies. This case is illustrated in Figure 5. In order to know which types of entities have to be linked together, the system needs to know the correspondences between these types of entities. Then it can work similarly as if there were a single ontology.

We represent this case in Figure 5 by introducing the correspondences between ontology classes as an alignment. This alignment is presented as implicit because it does not exist as such, but it is mixed with the data interlinking specification or system. For example, OpenCyc3 represents the artist J.S. Bach using a different ontology than the one used to describe MusicBrainz. The properties "firstname" and "lastname" correspond to a property "EnglishID" in which both names are concatenated. The class Mu-sicArtist in the Music Ontology corresponds to a class Classical Music Composer in OpenCyc. An alignment between classes and properties needs to be specified in order to find an equivalence between the two resources. This example is illustrated in Figure 6. Another approach, illustrated in Figure 7, takes advantage of an already existing explicit alignment between the two ontologies used by the datasets. An additional possibility, not found in existing systems, would be for the data linking system to first match the two ontologies before using the resulting alignment for supporting data interlinking. In such a system, ontology matching and data interlinking would be merged.

Figure 8 unifies all these processes in a single description. This framework leads to clarify interactions between data interlinking and ontology matching. It would be useful to use it in order to make tools interoperate. This would present many advantages, in particular the possibility to share, distribute and improve link specifications, as well as reuse them or extend them instead of computing them again whenever a dataset is modified. This would also allow to compose linking specifications such that it would be possible to go from one dataset to another without going through an intermediary. We consider below many possible ways to realize this integration.

The next section discusses how using ontology alignments could lead to more automation for the interlinking task, as well as how linked data could provide evidence for obtaining better ontology alignments.

DATA INTERLINKING USING ONTOLOGY ALIGNMENTS

Although ontology matching and data interlinking can be similar at a certain level (they both relate formal entities), there are important differences as displayed by the the previous framework. Indeed, one acts at the schema level and the other at the instance level. These differences are reflected in the types of specification involved in these processes -asameAs statement tells which City in wikipedia correspond to which P (place) in geonames, -a linking specification tells how to find the former, an ontology alignment tells which components from one ontology corresponds to which components in the other. This results in two process specifications -interlinking and matching -and their results -linksets between data and alignments between ontologies. By clearly establishing these differences, we obtain a natural partitioning between data links, linking specifications and ontology alignments:

The assertion expression language allows for representing equivalence between resources in datasets, e.g., RDF and VoiD;

The linking specification language allows for defining how to search for equivalence between resources, e.g., Silk;

The alignment representation language allows for specifying equivalence rules between ontological entities, e.g., the Alignment format or EDOAL (see below).

However, data interlinking and ontology matching could find a mutual benefit at collaborating. We propose a scheme under which it is possible for data linking tools to take ontology alignments as a way to constrain their solution space. The of Section 3, as displayed in Figure 8, provides a natural way to implement this collaboration.

EDOAL (Expressive Declarative Ontology Alignment Language) is the new name of the OMWG map-ping language for expressing ontology alignment (Euzenat et al., 2007) that has been available through the Alignment API since version 3.1. This language is an extension of the Alignment format [START_REF] David | The Alignment API 4.0[END_REF] that can be generated by most matchers. Its main purpose is to offer more expressiveness in the way alignments are expressed so it can represent complex alignment patterns [START_REF] Scharffe | Correspondence patterns for ontology mediation[END_REF][START_REF] Scharffe | Correspondence Patterns Representation[END_REF]. It presents the advantage to be declarative and also to specify transformations like those needed in order to construct links between resources.

In particular, EDOAL allows for expressing contextual relations between elements. For instance, the typical example in Silk documentation is the linking of DBpedia cities and geoname P(laces) through comparing their names and populations. Expressing this with a simple alignment does not express the expected meaning because, of course, rdfs:label is not equivalent to gn:name. One could consider expressing that gn:name is more specific than rdfs:label. This is correct but still not precise enough. The intended meaning is that, in the context of dbpdia:City and gn:P, these two properties are equivalent. This is what EDOAL can express through the following alignment: Even if such an alignment would provide information to data interlinking tools, this is still not suf-ficient. Of course, it tells which properties should be equivalent and thus can be used for identifying entities. But it does not tell how to take them into account. So, this alignement would be sufficient to link entities if the values of rdfs:label were exactly the same as those of gn:name and the values of populationTotal were exactly the same as those of population, but not otherwise.

EDOAL provides more features for transforming this information. This could be helpful but the problem is deeper: data interlinking is a decision problem rather that just a transformation. It is the role of the data linking specification to tell when a dbpedia:City and a gn:P should be considered the same. This is why we propose to use data interlinking specifications together with alignments.

Indeed, using an explicit alignment, provided that it is expressive enough, can serve two functions:

1. narrowing the search space through pointing to equivalent concepts, and 2. providing the properties that can be used for identifying concepts.

A link specification like Silk-LSL [START_REF] Bizer | Silk -a link discovery framework for the web of data[END_REF] fulfills two roles: -it is an alignment: it specifies the classes in which entities to link can be found, it specifies how to link entities. It could be possible to refer to an external alignment between the two underlying ontologies instead of specifying it in the linking specification. This approach would present obvious reuse advantages when other datasets requiring the same alignment, i.e., using the same ontologies, need to be interlinked.

Given that the alignment is available, it is possible to simplify the Silk specification and refer to the alignment, by introducing three types of information: which alignments to use (UseAlignment), entities of which correspondences must be linked (LinkCell) and which matched properties can be compared for identifying entities (CellParam).

<UseAlignment rdf:resource="#dbp-geo" /> <Interlink id="cities"> <LinkType>owl:sameAs</LinkType> <LinkCell rdf:resource="#map1" /> <LinkCondition> <AVG> <Compare metric="jaroSimilarity"> <CellParam rdf:resource="#map2" /> </Compare> <Compare metric="numSimilarity"> <CellParam rdf:resource="#map3" /> </Compare> </AVG> </LinkCondition> <Thresholds accept="0.9" verify="0.7" /> <Output acceptedLinks="accepted_links.n3" verifyLinks="verify_links.n3" mode="truncate" /> </Interlink>

The specifics of the data interlinking task remain in this specification: how to compare values, how to aggregate their results and when to issue the link or not.

This approach presents several advantages:

1. The link specification is simplified, reducing the manual input; 2. The alignment can be reused for linking any two datasets described according to these two ontologies; 3. There is a clear separation between links, linking specification, and ontology alignments.

CONCLUSION

We have proposed an architecture based on three different languages having each its own precise purpose: expressing links, expressing linking specifications, and expressing ontology alignments. This architecture can be used in order to organize a better collaboration between ontology matchers and data interlinking tools. This can be with only minimal extensions to existing languages. In particular, we have illustrated the ontology alignment part with EDOAL, an expressive ontology alignment language that offers the necessary concepts for being used in data interlinking. On the data interlinking side, we have focussed on the Silk-LSL language which seems to be at once declarative and powerful enough to express a wide range of constraints on data interlinking. Extending it with the capacity to benefit from ontology alignments would allow tools using it to benefit from the wide range of ontology alignment techniques and tools.

Figure 1 :

 1 Figure 1: The data interlinking problem.

  Figure 2: URI transformation.

Figure 3 :

 3 Figure 3: Matching two datasets described according to the same ontology.

Figure 4 :

 4 Figure 4: Example of matching two datasets described according to the same ontology.

Figure 5 :

 5 Figure 5: Two datasets matched using an implicit alignment.

Figure 6 :

 6 Figure 6: Example of two datasets described with heterogeneous ontologies.

Figure 7 :

 7 Figure 7: Two datasets matched using an explicit alignment.

Figure 8 :

 8 Figure 8: General framework for data interlinking involving ontology matching.

sw.opencyc.org

Acknowledgements

This work was conducted in the context of the Datalift project funded by the French ANR (Agence Nationale de la Recherche) under grant ANR-10-CORD-009.