Ashish Karmacharya

Christophe Cruz
email: christophe.cruz@u-bourgogne.fr

Frank Boochs

Franck Marzani
email: franck.marzani@u-bourgogne.fr

Integration of Spatial processing and knowledge Processing through the Semantic Web Stack

Keywords: Spatial processing, Knowledge processing, OWL Ontology, Rule language, Query language, SPARQL, SWRL

This paper presents the integration process of spatial technologies and Semantic Web technologies and its associated tool. The result of this work is a spatial query and rule engine of spatial. To do so, existing ontology with spatial elements is adjusted in order to process the spatial knowledge through spatial technologies. This paper outlines the methods and the processes of these adjustments and how results are returned by our tool. The SWRL and the SPARQL language are extended for spatial purpose and the existing OWL ontology wine is used as an application example.

Introduction

The Semantic Web is a set of technologies complementing the conventional Web tools proposed by Sir Tim Berners-Lee. It is seen as the most likely approach to reach the goal of semantic interoperability. The Semantic Web is envisaged as an extension to the existing web from a linked document repository into the platform where information is provided with the semantic allowing better cooperation between people and their machines. This is to be achieved by augmenting the existing layout information with semantic annotations that add descriptive terms to web content, with meaning of such terms being defined in ontologies [START_REF] Horrocks | OWL: a Description Logic Based Ontology Language for the Semantic Web[END_REF]. Ontologies play crucial role in conceptualizing a domain and thus play an important role in enabling Web-based knowledge processing, sharing and reuse between applications. This research attempts to contribute through including the functionalities of the spatial analysis within the Semantic Web framework. Moving beyond the semantic information, it has opened the chapter of inclusion of other form of information within the Semantic Web framework. It is important in the sense of the development of the technology itself. This work should at least provide a certain vision towards the direction the technology should take to integrate new forms of data. It discusses the direction in terms of spatial integration [START_REF] Karmacharya | Use of Geospatial Analyses for Semantic Reasoning, Knowledge-Based and Intelligent Information and Engineering Systems -14th International Conference[END_REF][START_REF] Karmacharya | ArchaeoKM: Managing Archaeological data through Archaeological Knowledge, Computer Applications and Quantitative Methods in Archeology -CAA[END_REF].

The Semantic Web stack (e.g. fig. 1.) can be adjusted with a layer of that contains spatial information. The research proposes such an arrangement in the stack. A layer of spatial data mixing seamlessly with the semantic proposition in the layer Ontology through its OWL/RDF based syntax can be envisaged. This layer since uses the standard syntax of OWL/RDF can perform spatial queries through SPARQL or infer rules through standards as SWRL. The integration process of the spatial technologies into the Semantic Web stack is undertaken by defining a new kinds of FILTERs for SPARQL queries and new kinds Built-ins for SWRL rules. These new FILTERS and Built-ins allow to process queries and rules with spatial data related to semantic data. The next chapter discusses this adjustment in the Semantic Web stack. Section 3 presents the top level ontology which enables the use of spatial technologies for any OWL ontology. Section 4 presents the translation engine which allows the translation of spatial queries and rules into standard queries and rules. Section 5 gives the complete process of extending an existing ontology in order to take into account the spatial technologies by using the famous wine ontology. Section 6 concludes this paper.

Background

The research project of Klein E. M. [START_REF] Klien | Semantic Annotation of Geographic Information[END_REF] in a certain degree follows the pattern of existing studies in geo-ontology research domain by focusing on the use of ontology for achieving data interoperability. It follows the pattern through defining the problems of data discovery in WFS (Web Feature Services) and the semantic differences in the data though the features associated to the data have same naming conventions. The problems follow even after the data discovery due to the nature of information that data represents is not explicitly stored. The research hence plans a mechanism of match making of different SDIs (Spatial Data Infrastructure) through the mediation of semantic rich domain ontology designed through the consultation of the experts. The Domain Ontology as it terms contains explicit information which capture the meanings of real world entities.

As with the case of this research, the research [START_REF] Klien | Semantic Annotation of Geographic Information[END_REF] utilizes the inference capabilities of the description logics in the ontology representation language of OWL-DL through inference rules. In addition, it uses a simple hydrological example to semantically annotate the data through the spatial rules. The SWRL representations of the rule are given:

Region(?x) ^ hasSlope(?x, Flat)  Lowland(?x) (1)
Lowland(?x) ^ River(?river) ^ adjacentTo(?x,?river) ^ hasAltitude(?x, ?xAlt) ^ hasAltitude(?river, ?riverAlt) ^ swrlb:subtract(?diffAlt, ?xAlt, ?riverAlt) ^ swrlb:lessThan(4, ?diffAlt)  Floodplain(?x)

(2)

Region, Lowland, River and Floodplain are the concepts and hasSlope, adjacentTo and hasAltitude are the object properties in both feature type's ontology and domain ontology. The idea consists to semantically annotate the concept Floodplain with the rules. The first rule represented by equation 1 forms the lowland if the slope of a region is flat. There are many constraints of a region being lowland but the research uses this rule to demonstrate the usability. A Digital Elevation Model (DEM) is used in background which intersects the inferred information and the dataset is annotated as lowland. In short the object property hasSlope is intercepted and run through an algorithm which combines the DEM dataset to determine the flat slope. Regions inferring these flat slops are then annotated as lowland. Extending the rule to equation 2, it uses object property adjacentTo and built-ins of SWRL to annotate the floodplain. The object property adjacentTo again needs to run an algorithm in collaboration to the spatial dataset to provide the result. This result again infers with the other axioms in the knowledge base to enrich itself. The adjacentTo object property utilizes buffer operation to determine the objects close to it. However, the operation is hidden from the users and is executed inside the algorithm. This execution enriches the knowledge base which could be inferred through standard rule of SWRL. The execution of buffer or any spatial operations are carried out through the spatial operations of ArcGIS. The semantic annotation through these rules is carried out to enrich the Domain Ontology thus negating any short coming of explicit semantics in feature type's ontology.

The method of inferring the rules first through execution of spatial operations at database or application level and then enriching the knowledge base matches with the current research work. However, the implications in both researches are different. The approach that current research undertakes is to enhance the Semantic Web technologies through integrating spatial components into the technology. It differs significantly with the former research [START_REF] Klien | Semantic Annotation of Geographic Information[END_REF] as it was conducted to use semantic web tools and techniques to answer specific GIS problems. Hence, the scale of application of Semantic Web techniques is relatively low in the previous research [START_REF] Klien | Semantic Annotation of Geographic Information[END_REF]. In other hand, it could be seen that the spatial operations and functions are used implicitly through object properties like hasSlope or adjacentTo which are terms of natural language. This might give ambiguity to the interpretations of these terms. For example the term adjacentTo can have two or more meanings as rightly quoted in the thesis report. It can be near to each other either through touching or not touching. So, the utilization of spatial operation should be based on these factors. If the adjacent to means that the objects are touching then the spatial operation "Touch" could be directly used instead of Buffer which is more resource dependent.

Contrary to [START_REF] Klien | Semantic Annotation of Geographic Information[END_REF], this research has taken the works forward to address these concerns. Instead of using the commonly used terms, it uses the spatial operations and functions terminology standardized by OGC [START_REF]The Open Geospatial Consortium[END_REF]. Standard terms are proposed to formulate rules rather than using domain based terms.

The equation 3 illustrated the adjustment of object property adjacentTo directly through SWRL rules through spatial built-ins, which means that the individuals of River which are in the Buffer of 50m of a individual of the concept Lowland possesses a relationship (ObjectProperty) named adjacentTo that link the Rivers and Lowlands.

River(?x)^Lowland(?y)^Buffer(?x, ?y, 50) adjacentTo(?x,?y)

(3)
Thus, it could be seen that there is much more flexibility concerning the definition of spatial rules through standard spatial built-ins proposed here. Besides the spatial built-ins for SWRL, this research adds on spatial built-ins to SPARQL, the query language of semantic web tools which is not explicitly researched before. However, before using these spatial built-ins in an existing ontology, it is first necessary to adjust this one with top level concepts. This integration process allows the linking of spatial data to ontologies. This ontology adjustment process is a generic process which allows the adjustment of any existing ontology in order to process spatial queries and rules on it.

The Top Level Ontology

This ontology serves as a foundation ontology to which objects can be instantiated during the identification process of spatial elements. The axioms are the building blocks of ontology and hence these axioms in the context of top level ontology of the application should be discussed to provide an overview of the system. The main axioms of this top level ontology are: Semantic -spatial:Feature Geometric -shp:Shape Geometric Relationship -shp:hasShape Spatial Relationship -sa:hasSpatialRelations Spatial Database Relationship -doc:hasDBDetails A shape has a definition in a spatial database. An individual has a shape and has spatial relationships with other individuals which have a shape.

The class axiom spatial:Feature represents the spatial objects. This class axiom is the generalized class of any objects with spatial definition. This class is further specialized into classes representing the different objects such as vin:Winery or vin:Region for instance regarding the example at the end of this paper. The spatial:Feature has to be specialized classes into subclasses. This abstract class cannot be instanced but only the individuals which belong to a subclass of spatial:Feature can have a spatial attribute.

The next important class axiom is shp:Shape which stores the local coordinates of the objects identified in the excavation site. This generalized class is specialized into shp:_3D and shp:_2D sub classes to represent the dimensions of the coordinates. Currently, an orthophoto is used to identify objects on a map and hence the 2D coordinates are returned of the objects. Semantics of objects in the knowledge base are defined through object property feat:objRel. But before that they need to relate to their spatial signature that is to their coordinates. This is managed through the specialized object property of shp:hasShape. As mentioned the coordinate of the object is derived through the digitization are stored as an individual of shp:_2D. This instance stores the coordinate of object. Once both the object and its coordinates are enriched, shp:hasShape provides a relationship between them. For instance, the concept win:Region as a subclass of spatial:Feature has the property shp:hasShape which can be a shp:_2D or shp:_3D.

The annotations to the database are carried out through assigning semantics to the annotations as assigning the relevant database and its relevant table in which the data is stored. It also provides the connection to the spatial column in which geometries of the objects are stored. An object property doc:hasDBDetails under general class doc:hasDocumentDetails provides these attributive connections. The three data properties to address the semantics of spatial annotation part of connecting to the MBRs are doc:dbName, doc:spColumn and doc:tableName, three specialized classes of doc:hasDBDetails.

The spatial functions and operations return geometries on their executions. It is hence important to have provision to store these returned geometries in the ontology. A generalized class sa:spatialOperation is introduced in the top level ontology. Every spatial operation under geoprocessing functions is then adjusted as its subclass. The class hierarchy of sa:spatialOperation reveals that the subclasses within it are the classes which need to represent returned geometries in some form.

The four spatial processing functions which are discussed here are Buffer, Union, Intersection and Difference. These spatial functions compute new spatial geometries. These new geometries are also stored in the spatial database in order to be computed by future spatial functions. As a solution, we definition four new classes called sa:sp_Buffer, sa:sp_Union, sa:sp_Intersection and sa:sp_Difference which are of specialized classes of sa:spatialOperation. The classes here are instantiated when the spatial operation of this category is executed. The result of execution is stored within the instantiated individual as the data property feat:localPlacement.

The functions under this category need to take a feature to execute them. The feature are objects within class feat:Feature. In order to maintain a relationship between the spatial operations representing classes under sa:spatialOperation and features under feat:Feature in the ontology an object property sa:hasSpatialRelations is added in the top level ontology. The specialized property relates the individuals under sa:spatialOperation and feat:Feature. For example for every instance in class sa:sp_Buffer (sub class ofsa:spatialOperation) be a property sa:hasBuffer (specialized object property of sa:hasSpatialRelations) which relates the sa:sp_Buffer class to the classes specializing feat:Feature. There are also four sa:hasSpatialRelations defined corresponding to each geoprocessing functions (sa:hasBuffer, sa:hasUnion, sa:hasIntersection, sa:hasDifference). Besides theses object properties, data properties to correspond the attributive nature of the relationships are also adjusted in the top level ontology. A generalized data property sa:hasSpatialAttribute is introduced in the top level ontology. Other attributive properties as sa:hasBufferDistance (denotes the buffer distance of the buffer) are specialized properties of it. These functions demonstrate the spatial relations between objects hence they are very straightforward when adjusting in ontology. They can be directly adjusted through object properties within the top level ontology. These functions are adjusted as specialized object properties of sa:hasSpatialRelations. The execution pattern of every function in this category is executed in similar. The table 2 illustrates the steps of every spatial function following OGC spatial operation standards but this research thesis utilizes four operations to demonstrate the argument. Those functions are Disjoint, Touch, Within and Overlap which are represented through sa:hasDisjoint, sa:hasTouch, sa:hasWithin and sa:hasOverlaps subsequently.

Funtions

The translation engine

The translation engine allows the computation of spatial SPARQL queries and spatial SWRL rules. In both cases, the translation engine interprets the statements in order to parse the spatial components. Once the spatial components are parsed, they are computed through relevant spatial functions and operations by the translation engine through the operations provided at the database level. Then after, the spatial statements are translated to standard statements for the executions through their proper engine namely the SPARQL engine and the SWRL engine. Concerning the inference engine, the enrichment and the population of the ontology regarding the results of the inference process is possibly stored in the ontology.

Fig. 2. The spatial processing of the translation Engine translating SPARQL queries and OWL rules

The next sections presents in details the translation engine on more specifically the translation process of spatial SPARQL queries to regular queries. The following one presents the translation process of spatial SWRL rules to regular SWRL rules. These two processes have in common the use of SQL statements to query to the spatial database.

Spatial SPARQL Queries

The FILTER keyword in SPARQL queries is used to define spatial queries. A FILTER can be used to compare strings and derive results. The functions like regular expression which matches plain literal with no language tag can be used to match the lexical forms of other literals by using string comparison function. In addition, SPARQL FILTER uses the relational operators as = or > or < for the comparison and restrict the result. From this idea, the FILTER principle is extender in order to process georelationship functions.

Geoprocessing FILTER

The following example shows how to select Building which intersect the buffer of 200km of a River. In this example, the keyword FILTER is replaced by the keyword SPATIAL_FILTER in order to be processed by the translation engine This process is a selection process, and no inference process is engaged. Once the process is ended, the rule is translated to a standard given in the following example. It can be seen that the SPATIAL_FILTER is replace by standard RDF triples which. Any SPARQL engine is able to run this rule.

Georelationship FILTER

The following example shows how to select couples of features which are linked by a touch spatial relationship. In this example, the keyword FILTER is replaced by the keyword SPATIAL_FILTER in order to be processed by the translation engine. The name of features couples are selected with this restriction. The first feature has to be a feat:River which is of kind of feat:feature, and the second feature has to be a feat:Building which is also of kind of feat:feature. The SPATIAL_FILTER selects the couples which are touching spatially. This process is a selection process, and no inference process is engaged. The aim of the translate engine consists to compute the touches spatial process of the Cartesian production between the features of the kind feat:River and feat:Building. In the case of a positive result, this new link is stored in the ontology between the couple of feature with the help of a sa:hasTouches relationship which is of the kind of sa:hasSpatialRelations. Once the process is ended, the rule is translated to a standard In addition the spatial filter can be combined by the following manner. It consists to insert news filters and to use the same variable. The following example consists to select building which contains a chimney in order to see if it touches a river. Moreover, no spatial processing is done, only the existing knowledge in the ontology is used to process this query.

Inference Rules through SWRL

In an attempt to define the built-ins for SWRL, a list of eight built-ins was proposed during the research work. These eight built-ins reflect four geoprocessing functions and four georelationship functions that are discussed previously. The builtins reflecting geoprocessing functions are built up in combinations with the spatial classes adjusted in the ontology and their relevant object properties. The built-ins for georelationship functions are in contrast are just object properties and using these object properties in collaboration to the spatial functions in database system.

Geoprocessing Built-ins

The first set of built-ins is the built-ins for geoprocessing functions. They are functions returning geometries and adjusted in the ontology through feat:Feature sa:hasSpatialRelations sa:spatialOperation sequence. This class-property series is illustrated in table 5. The initial step consist the built-ins parsed to be processed by the translation engines. First the spatial built-ins are identified from the statement and parsed. Concurrently, the features on which these built-ins are applied are also identified.Then after, the SQL statementswith relevant spatial function on the relevantobjects of the featuresare executed at the database level. The results are then enriched in the knowledge base. Once, the knowledge base is enriched, the spatial built-ins are broken down into standard feat:Feature sa:hasSpatialRelations sa:spatialOperation sequence to generate the standard SWRL statement which is executed through standard inference engines. The execution of every built-in can be elaborated through first running down the spatial operation and then translating the statements with spatial built-in into standard SWRL statements. Simplifying the explanations with an example of feat:Feature(?x) ^ Buffer(?x, b, ?y) suggesting the use of built-in Buffer on objects within the specialized classes of feat:Feature with the buffer distance. This statement is elaborated first through running the SQL statement with the spatial function buffer on each objects of the class to which it meant to run. That is if the statement is related to buffering walls, then each instance of class feat:Wall is taken and buffered through the execution of the SQL statement. The SQL statement with spatial function Buffer would look like: SELECT Buffer(geom::Feature, bufferDistance)

Functions

Here, the geom are the geometries of the objects within specialized classes of feat:Feature. The result of this execution is then enriched in the knowledge base. Primarily, the rows in result are geometries which indicate the buffers of each object with certain buffer distance. The class sa:sp_Buffer is instantiated with objects representing every row and storing the buffer geometry and the buffer distance within them. Then after, it is time to translate the statement with the spatial built-in into standard form of SWRL statement which would be feat:Feature(?x)^sa:hasBuffer(?x,?y)^sa:sp_Buffer(?y)^ sa:hasBufferDistance(?y,b) Thus, the statement converts the spatial built-in into feat:Feature sa:hasSpatialRelations sa:spatialOperation sequence of standard SWRL statement. The complete list of SQL execution, the result enrichment and statement translation process is illustrated in table 6. knowledge base. Now, the statements are ready to get executed. The spatial built-ins are broken down into feat:Feature sa:hasSpatialRelations feat:Feature sequence by the translation engine which is now a standard statement so can be executed. It would be helpful to elaborate with an example of built-in Feat:Feature(?x) ^ feat:Feature(?y)^ Touch(?x,?y)

Built

It is a spatial operation to determine whether an object is touching another. Generally, the georelationship operations are binary operations and return Boolean values when is executed alone. However, when executed as a conditional parameter of the SQL statement, they yield results. That is if the statement SELECT Touch(geom::Feature1, geom::Feature2) is executed. It returns either true or false determining whether the geometry of feature1 touches geometry of feature2. But if the same operation is executed as SELECT Feature2 FROM spTable WHERE Touch(geom::Feature1, geom::Feature2) then it returns all the feature2 which touches feature1. Here spTable is the table where the geometries of the features are stored in the database system and has been spatially annotated. The results derived through the execution of the statement with Touch operation is then enriched against sa:hasTouch object property of the specified feature. The last step is to break down the Touch(?x, ?y) built-in into feat:Feature sa:hasSpatialRelations feat:Feature sequence to get the SWRL statement executed. The breakdown of the spatialbuilt-in Touch(?x, ?y) is given as feat:Feature(?x) ^ hasTouch(?x, ?y) ^ feat:Feature(?y)

It is a standard SWRL statement which can again be inferred by inference engines. The complete list of SQL statement execution is illustrated in table 7.

The wine example

The famous wine ontology is used here to present the principle of spatial ontology adjustment which allows the computation of spatial data on any existing OWL ontology. The wine ontology is selected for several reasons. The wine ontology appears frequently in the literature as an example to define tutorials.

The Existing Ontology Adjustment

In order to adjust the exiting ontology, two main steps are essential. First, the top level ontology has to be imported into the existing ontology. In this manner, all the components of the spatial layer are available for the existing ontology, which are the annotation and tagging principles of documents and more specifically the spatial definitions. The second step consists to specialized specific concepts of the exiting ontology which have possibly spatial signatures. In the wine ontology, wine regions can be defined as spatial region or polygons in a GIS system. In addition, the wineries can be geolocalized as points in the same GIS system. Since the existing ontology is adjusted, the feed of the spatial database regarding the concepts respectively, wine region and wineries, of the ontology can be undertaken with the help of the individual already defined in the ontology. For instance, the individual vin:ClosDeVougeot, which is a French winery localized in Burgundy, is defined by the geolocalized point 47.174835,4.95544 in the WGS84 coordinate system.

The following figure shows the adjusted wine ontology. On the left side, the tree viewer represents the hierarchy of concept with the top level ontology and spatial:feature concept with the wine ontology specialized concept vin:Region and vin:Winery. All the other concept of the wine ontology can by spatially defined. On the right side, the list of the vin:Winery individuals is given. The individual vin:ClosDeVougeot appears in this list. This list is composed of 43 individuals and the list of vin:Region is composed of 36 individuals.

Spatial Querying process.

This section presents the benefit of spatial querying on spatial data composed of semantic definition. In the figure 5.16, the individual vin:CoteDOrRegion has a relationship has:adjacentRegion. This relationship defines a symmetric relationship between two regions. In the wine ontology, this information is not feed. Currently, it is no possible to select adjacent regions and regions which are around of 200km to each other. In the case of a spatial definition in a Spatial GIS, the following queries are possible. The first query select all the adjacent regions to vin:CoteDOrRegion. The second query select all the regions which are around of 200km to the region vin:CoteDOrRegion. check the consistency of the knowledge base in the case that the links were not generated from the spatial processing.

Spatial Inference process.

With the help of the SWRL rules, the enrichment of the ontology is now possible. The following simple example underlines this idea. The winery Clos de Vougeot vin:ClosDeVougeot which is a located in the region of Côte D'Or vin:CoteDOrRegion, and this region is actually a region located in France vin:FrenchRegion. Consequently, the winery Clos de Vougeot vin:ClosDeVougeot is located in France vin:FrenchRegion. The transitive relationship vin:hasSubRegion allows the definition of relationships between regions vin:Region.

This first SWRL rule enriches the ontology with vin:hasSubRegion relations between regions.

vin:Region(?x) ^ vin:Region(?y) ^ spatialswrlb:Within(?y, ?x)  vin:hasSubRegion(?x, ?y)

This second SWRL rule enriches the ontology with vin:isLocatedInRegion relations between wineries and regions.

vin:Region(?x) ^ vin:Region(?y) ^ vin:Winery(?z) ^ vin:hasSubRegion(?x, ?y) ^ vin:isLocatedInRegion (?z, ?x)  vin:isLocatedInRegion (?z, ?y) This third SWRL rule does at the same time the first and the second rule by using spatial built-ins.

vin:Region(?x) ^ vin:Region(?y) ^ vin:Winery(?z) ^ swrlbspatial:Within(?y, ?x) ^ swrlbspatial:Within(?z, ?y)  vin:isLocatedInRegion (?z, ?y) ^ vin:hasSubRegion(?x, ?y)

After the execution of this third rule, new relationships vin:isLocatedInRegion and vin:hasSubRegion are created in the ontology in order to link . Consequently, the ontology is enriched with these new relationships.

Conclusion

This research attempts to highlight the possibilities to integrate spatial technology in semantic web framework. It moves beyond the scope of data interoperability while presenting the concept and makes efforts to utilize the potentiality in other areas of the Semantic Web technologies. The underlying technologies of knowledge processing provide to the semantic web the capabilities to process the semantics of the information through close collaboration with the machine. It makes not only the understanding of data easier for achieving interoperability among different data sources, but it also provides valuable knowledge which could enrich the knowledge

Fig. 1 .

 1 Fig. 1. Snapshot of the wine ontology adjusted with spatial component.

Table 1 .

 1 The Spatial Processing Functions

		Concept	ObjectProperty	Execution Method
	Buffer	sa:sp_Buffer	sa:hasBuffer(x,c)
				C is of float value providing the buffer
				distance
	Union	sa:sp_Union	sa:hasUnion(x,c)
	Intersection sa:sp_Intersection sa:hasIntersection(x,c)
	Difference	sa:sp_Difference	sa:hasDifference(x,c)
	Intersection sa:sp_Intersection sa:hasIntersection(x,c)
		Functions	ObjectProperties	Characteristics
		Disjoint	sa:hasDisjoint(x,y)	Symmetric
		Touches	sa:hasTouch(x,y)	Symmetric
		Within	sa:hasWithin(x,y)	Transitive
		Overlaps	sa:hasOverlaps(x,y)	
		Equals	sa:hasEqual(x,y)	Symmetric, Transitive
		Crosses	sa:hasCrosses(x,y)	Symmetric
		Intersects	sa:hasIntersect(x,y)	Symmetric
		Contains	sa:hasContain(x,y)	Transitive

Table 2 .

 2 The Georelationtionship Functions

Table 3 .

 3 The spatial SPARQL syntax and its translation into SARQL syntax.

Table 5 :

 5 GeoProcessing built-ins

Table 8 :

 8 SQL statements executions of georelationship built-ins for the spatial enrichment

	-ins	SQL Statements	Translated Built-ins
	swrlbspatial:Disjoint(?x, ?y) SELECT Feature2 FROM spTable	sa:hasDisjoint(?x, ?y)
		WHERE	Disjoint(geom::Feature1,
		geom::Feature2)
	swrlbspatial:Touches(?x,	SELECT Feature2 FROM spTable	sa:hasTouch(?x, ?y)
	?y)	WHERE	Touch(geom::Feature1,
		geom::Feature2)
	swrlbspatial:Within(?x, ?y) SELECT Feature2 FROM spTable	sa:hasWithin(?x, ?y)
		WHERE	Within(geom::Feature1,
		geom::Feature2)
	swrlbspatial:Overlaps(?x,	SELECT Feature2 FROM spTable	sa:hasOverlaps(?x, ?y)
	?y)	WHERE	Overlap(geom::Feature1,
		geom::Feature2)

Ashish Karmacharya1,2, Christophe Cruz2, Frank Boochs2, Franck Marzani1 base in order to equip it with new knowledge. This helps the users understand the data better. The underlying knowledge technology makes stand out among its contemporaries.

It is important to have standard terms for every built-in that will be developed to process spatial knowledge. With other built-ins in the tools standardized by W3C, the spatial built-ins should also get standardized by the consortium. In addition to W3C, OGC should also get involved in standardizing the built-ins. An effort in this direction should be carried out.

given in the following example. It can be seen that the SPATIAL_FILTER is replace by the triple "feat1 sa:touch ?feat2". Thus this rule can be processed by a standard SPARQL engine.

Optimization

The translation engine is time consuming for large spatial database. In order to select the context of execution four options can be given to the SPATIAL_FILTER.

SPATIAL_FILTER_SELECT: No spatial operation is undertaken; the rule is translated without any spatial processing SPATIAL_FILTER_PROCESS: Spatial operations are processed only for the couples of features which don't have this relationship. If this relation already exists, this one is not computed. SPATIAL_FILTER_UPDATE: Spatial operations are processed only for the couples of features which have already this relationship in order to update these relationships.

SPATIAL_FILTER_ALL: This is the option by default which consists to compute all relationship for the Cartesian product in order to process it if it doesn't exist or in order or update it.

The following example shows that the selection of features which have the touches relationship is done with the option SPATIAL_FILTER_UPDATE. However, it is necessary to determine the nature of built-ins from the statement to determine what spatial operation needs to be performed at database level. These statements are hence parsed to identify the spatial built-ins from the statement. Then after, the SQL statement with related spatial operation is executed in the database level. The results are enriched against their specified object properties in the The first examples of queries are related to the same kind of individuals, the same can be undertaken on different kind of individuals. For instance, no spatial relationships are defined between regions and wineries. With the adjustment of the ontology and the spatial definition of wine regions and wineries, now the following query can be undertaken easily. I would like to know all the wineries in a specific region. If these relationships were defined in the ontology, then it would be possible to check the spatial consistency of the knowledge based. The individual vin:ClosDeVougeot is a winery located in vin:CoteDOrRegion. In the case of the definition of a symmetric relationship named vin:located between the concept vin:Region and the concept vin:Winery, the individual vin:ClosDeVougeot should be linked to the individual vin:CoteDOrRegion with the help of this relationship. The following query is able to validate this relationship from spatial point of view. If the result is false, but the spatial data define and correct than the ontology is inconsistent. The overlap between the semantic links and the spatial data permits to

Built


Thomas Cerqueus
email: thomas.cerqueus@univ-nantes.fr

Sylvie Cazalens
email: sylvie.cazalens@univ-nantes.fr

Philippe Lamarre
email: philippe.lamarre@univ-nantes.fr

Semantic heterogeneity measures of unstructured P2P systems

We consider P2P data sharing systems in which each participant uses an ontology to represent information. If all the partipants do not use the same ontology, the system is said to be semantically heterogeneous. Several methods have been proposed to reach a degree of interoperability but thorough evaluation of these methods is prevented by a lack of tools to describe the situations in which they have been tested. In this paper we identify components that impact on the semantic heterogeneneity, and we define several complementary measures to capture the different facets of heterogeneity. Proposed measures allow to characterize the situation in which a method is evaluated, or to measure the heterogeneity reduction produced by another method.

I. INTRODUCTION

In this paper, we are interested in data sharing peer-topeer (P2P) systems where each peer is an individual data source. We focus on systems in which each peer uses an ontology to represent its data and its queries. If all the participants use the same ontology, the system is semantically homogeneous. However when the number of peers is important, it is unlikely that they agree on the use of a single ontology.This leads to a situation of semantic heterogeneity of the system. Several methods have been proposed to reach a degree of interoperability using correspondences between ontologies [START_REF] Euzenat | Ontology matching[END_REF]. Most of them are translation-based solutions. Some proposals use similarity between concepts of a same ontology to better answer queries [START_REF] Ventresque | Improving interoperability using query interpretation in semantic vector spaces[END_REF]. These approaches can be classified into two classes (non necessarly distinct): those which try to cope with heterogeneity to obtain interoperability (noted CH-methods), and those which try to decrease heterogeneity (noted DH-methods).

Thorough evaluation of these methods is prevented by a lack of tools to describe the situations in which they have been tested (from a semantic viewpoint). It is generally limited to a specific configuration of a given system. Hence the problem is to define elements that might be useful to describe a given semantic state of the distributed system with respect to heterogeneity, just like the system load describes the global amount of work to be treated by the system.

Our approach consists in identifying components that impact on the semantic heterogeneneity of a P2P system, and defining several complementary measures to capture the different facets of heterogeneity. We underline that considering the problem from an evaluation perspective allows us, like for designers of the experiments, to have a global view of the P2P system. In that case, it is possible to assume knowledge that a given peer wouldn't have itself within the system. Proposed measures should allow to characterize the situation in which a given CH-method is evaluated. They should also enable to measure the heterogeneity reduction of a given DH-method.

The paper is organized as follows. Section II presents scenarios showing that heterogeneity is a multifaceted notion. Section III presents the formal model. Section IV defines several complementary measures of semantic heterogeneity. Section V discusses related work. Section VI concludes.

II. SEMANTIC HETEROGENEITY IS MULTIFACETED

In this section we present three scenarios that aim to identify several facets of heterogeneity.

Scenario 1: Let us consider a P2P system in which participants use different ontologies. Assuming data are uniformly distributed, each participant can potentially answer to queries. In this situation, the possibility for a participant to be understood when he sends queries depends on the number of ontologies used in the system, and the number of participants using the same ontology as he does. This scenario shows that it is crucial to consider the number of ontologies on use, and the number of participants.

Scenario 2: We now consider a P2P system in which some participants use an ontology o 1 and others use o 2 . In that case, the capacity to interoperate depends on the disparity between the ontologies o 1 and o 2 . More generally, it depends on the disparities between the participants (disparity between their knowledge and their perceptions). In order to measure heterogeneity of the whole system, it is necessary to consider the disparity between the couples of participants.

Scenario 3: Here we consider a P2P system in which participants use different ontologies. We also consider that queries are not sent to the whole system: a query issued by p is sent to a subset of the participants. The possibility for p to retrieve relevant documents depends on the capacity of its neighbourhood to understand his queries. So in order to measure the difficulty to interoperate, we have to focus on the neighbourhood of each participant by considering the disparity between them and their neighbourhood. These three scenarios identify different facets that should be taken into account: the contexts on use, the disparities between participants and the organization of the system.

III. MODEL

A. The basic P2P system An unstructured P2P system is defined by a graph S = P, N , where P is a set of peers (with |P| > 1) and N represents a neighbourhood relation. Each element in N is an ordered pair (p i , p j ) of P such that p j is one of p i 's neighbours.

Definition 1: The neighbourhood of a participant p within a radius n, denoted by N p n , is the set of participants accessible from p with l hops, where 1 l n. We consider that p does not belong to its own neighbourhood.

In the system of Figure 1, N p1 2 = {p 2 , p 3 , p 4 , p 5 }.

B. Semantic context of a participant

We consider that an ontology is composed of a set of concepts C o , a set of relations R o (linking the concepts) and a set of properties P o (assigned to the concepts). In practice OWL allows to represent ontologies by defining classes, datatype properties and object properties.

A function measuring the proximity between any two concepts of a same ontology is called an intra-ontology similarity measure: Some measures presented in the litterature could be used as disparity measure but they are limited to a single component of semantic contexts: the ontology [1] [START_REF] David | Comparison between ontology distances (preliminary results)[END_REF]. We think that it may be relevant to consider the differences that come from intra-ontology similarity functions. Indeed some methods of information retrieval use similarity values to extend queries. Thus two participants, using different contexts, could extend a query with different concepts, depending on their intraontology similarity. For example, Figure 2 illustrates the case of two participants who rank concepts with respect to their decreasing similarity with the concept Flower. Their rankings are different, so they would not extend a query about Flower with the same concepts.

sim o : C o × C o → [0,
dis φ,φ ′ (c) = 1 |E o ′ o | c0∈E o ′ o |rank c φ (c 0 ) -rank eq c o ′ φ ′ (eq c0 o ′ )| max(|S c φ |, |S eq c o ′ φ ′ |) -1
Applying dis φ,φ ′ for each concept of o having equivalent defines disparity as:

d disorder (φ, φ ′ ) = 1 |E o ′ o | c∈E o ′ o dis φ,φ ′ (c)

D. Semantic heterogeneity: definition and typology

Definition 5: Let us assume a set SM of models M = P, N , Φ, d , µ where P, N is a P2P system, Φ is a set of semantic contexts with a disparity function d and µ is a peer-to-context mapping.

A semantic heterogeneity function (or measure) is a function

H : SM → [0, 1] such that: • H(M) = 0 if |φ S | = 1 (minimality); • H(M) = 1 if ∀φ, φ ′ ∈ φ S , d(φ, φ ′ ) = 1 (maximality). where φ S = {φ ∈ Φ : ∃p ∈ P such that µ(p) = φ}.
Depending on the application domain, several functions might be necessary to capture all the facets of heterogeneity.

Based on the previous model, we propose a typology of heterogeneity measures. In our view, every measure should consider P, Φ and µ which are the basic components of the model. Then, we differentiate the measures which are:

• Structure aware/unaware: An heterogeneity measure is structure aware if its definition considers the neighbourhood relation N . Otherwise it is structure unaware. • Disparity aware/unaware: An heterogeneity measure is disparity aware if its definition considers the disparity function d on the set of semantic contexts Φ. Otherwise, it is disparity unaware. These two criteria can be combined, leading to four classes of heterogeneity measures. For each class, Table I enumerates the elements of the model that are considered.

IV. MEASURES OF HETEROGENEITY

A. Structure unaware measures 1) Disparity unaware measures: Notions of richness and evenness are commonly used to measure the heterogeneity of a population (e.g. in biology). Richness is the number of "species" present in a population. Evenness is the relative abundance or proportion of individuals among the "species". In our context, richness depends on the number of different semantic contexts used in the system. The more contexts there are, the more heterogeneous it is. This idea can be expressed by the following measure:

H Rich (M) = |φ S | -1 |P| -1
where |φ S | is the number of different contexts used in the system S, and |P| is the number of participants.

Example 1: In the system presented on Figure 1, four different contexts are used by ten participants:

H Rich (M) = 4-1
10-1 = 0.33. The richness measure does not give any indication on how contexts are distributed. However it is important to differenciate cases where contexts are evenly distributed across the system from cases where several contexts are used only once. To capture this aspect we can adapt the Simpson diversity index [START_REF] Simpson | Measurement of diversity[END_REF]:

D = 1 |P| 2 φi∈φ S |P φi | 2
where P φi is the set of peers using φ i . We define H Even as:

H Even (M) = |P| • (1 -D) |P| -1
Example 2: On the system presented on Figure 1, D = 0.34. Given |P| = 10, we find H Even (M) = 0.73. If H Even is close to 1, we can assert that some participants do not share their semantic context with anyone while others do share it with many others. Measures H Rich and H Even are complementary because they capture two aspects of the heterogeneity. Indeed a system can be rich (i.e. a lot of different contexts are used) and even (i.e. contexts are used in equal number), or poor and uneven, etc.

2) Disparity aware measure: On top of determining diversity, it is interesting to take into account disparity between contexts of the system. Indeed diversity measures do not make any difference between a system S 1 using η contexts between which disparities are weak, and a system S 2 using η contexts between which disparities are important. We propose to consider the disparity between participants rather than only consider the contexts they use. If the disparity between participants is globally important, it means that participants have important knowledge differences. As we do not take into account the system topology, we consider the disparity between each pair of participants:

H Disp (M) = 1 |P| 2 -|P| pi =pj ∈P d(µ(p i ), µ(p j ))
It determines if peers are globally disparate from each other.

B. Structure aware measures

In an heterogeneous P2P system, it is interesting to consider the participants' neighbourhood. If participants are globally far (semantically speaking) from their respective neighbourhoods, the system is highly heterogeneous. Starting from a participant p's neighbourhood N p n , we propose several measures.

1) Disparity unaware measure: First we can number the participants that do not use the same semantic context as p:

H n Rap (M, p) = |{p i ∈ N p n : µ(p i ) = µ(p)}| |N p n |
This measure gives basic information about a participant's neighbourhood, and could eventually be calculated by a participant itself. Indeed, it just requires to be able to determine if another participant uses the same context. Example 3: In Figure 1, N p1 2 = {p 2 , p 3 , p 4 , p 5 }. As p 3 and p 4 do not use the same context as p 1 , we find that H 2

Rap (M, p 1 ) = 2 4 = 0.5. We can use H Rap to get a global measure:

H n RapAvg (M) = 1 |P| p∈P H n Rap (M, p)
2) Disparity aware measure: The fact that two participants do not use the same context does not induce that they can not communicate together. So we refine the previous measure by considering a disparity measure:

H n Dap (M, p) = 1 |N p n | pi∈N p n d(µ(p), µ(p i ))
This measure focuses on a particular participant and determines how this latter is understood by its neighbours. Example 4: In Figure 1 Proposition 1: All the proposed measures satisfy both properties of minimality and maximality (proofs are trivial).

3) Using heterogeneity measures to evaluate system organization: Some measures defined previously enable to determine if a participant is well located in a system with regards to its neighbourhood. Intuitively, the neighbourhood of a participant p is "favorable" if it is composed of the participants from whom he is close semantically. The neighbourhood of a participant is favorable if considering a bigger neighbourhood increases the heterogeneity (around p). Given n hops, the neighbourhood of p is favorable if:

∀i n, ∀j > n, H i (M, p) H j (M, p)
where H is an heterogeneity measure centered on a participant (e.g. H Rap or H Dap ). Having a condition to determine if a participant's neighbourhood is favorable allows to determine how hard it will be for this participant to be understood: it gives information on its capacity to interoperate.

Given two systems S 1 and S 2 , we can say that p's neighbourhood is more favorable in S 1 than in S 2 if:

∀i ∈ [[1, n]] , H i (M 1 , p) H i (M 2 , p)
We can compare two systems' organization both way: we can use global measures, or we can rely on conditions relative to participants' placement. For instance, we could say that S 1 is better organized than S 2 if each participant's neighbourhood is more favorable in S 1 than in S 2 .

V. RELATED WORK

Our work assumes the existence of a disparity measure between two semantic contexts. Distance measures proposed in the field of ontology matching can be adapted and used. [START_REF] Euzenat | Ontology matching[END_REF] and [START_REF] David | Comparison between ontology distances (preliminary results)[END_REF] present a number of similarity measures between two ontologies based on terms associated to concepts and on the hierarchical structure of ontologies. In [START_REF] David | Ontology similarity in the alignment space[END_REF] authors propose measures of similarity between ontologies in the alignment space (this latter is defined as a set of ontologies, and a set of alignments between these ontologies). This work can be adapted to define disparity between two participants of a P2P system, but it does not aim to characterize heterogeneity of the whole system/space. All these measures can be used in our work if we assume that the participants' semantic contexts are only made of ontologies.

In [START_REF] Cudré-Mauroux | A necessary condition for semantic interoperability in the large[END_REF] authors define a necessary condition for semantic interoperability in P2P systems, but do not propose any measures. They assume that interoperability is ensured by the presence of correspondences between the different schemas (or ontologies) on use. In this context, two peers are said to be semantically interoperable if translation links exist between each other. Nevertheless this condition does not give information about the translation quality.

VI. CONCLUSION

In this paper we defined several complementary measures to capture different facets of heterogeneity. They are divided into different classes depending on the fact that they exploit the system topology and/or disparity measures. The proposed measures are meant to be used in an evaluation context, this is why we assumed global knowledge of the system. Depending on the application the designer of the experiments should choose those measures which, together best characterize the system semantic heterogeneity. They can also be used to instanciate P2P systems with specific (semantic) characteristics. Obviously, the proposed measures should be validated through extensive experimentations.

As future work, we plan to propose algorithms that reduce heterogeneity and to evaluate them in different situations of heterogeneity according to the proposed measures.

Figure 1 .

 1 Figure 1. Unstructured P2P system.

  1]. Several measures have been defined in the litterature[START_REF] Seddiqui | Metric of intrinsic information content for measuring semantic similarity in an ontology[END_REF].Definition 2: A semantic context is a couple φ = o, sim o where o is an ontology and sim o is an intra-ontology similarity measure. A semantic context enables to express the participant's perception of a domain in a more refined way. Indeed the ontology only reflects the relative organization of the concepts used to model the domain. An intra-ontology similarity brings an additional notion of proximity which expresses how close two concepts are according to the participant.Definition 3: Given a P2P system S = P, N , a peerto-context mapping is a function µ : P → Φ mapping each peer to one semantic context.C. Disparity between two semantic contextsDefinition 4: A disparity function d : Φ × Φ → [0, 1] is a function that assigns a real value in [0, 1] to a couple φ, φ ′ representing how much φ ′ differs from φ. It satisfies the minimality property: ∀φ ∈ Φ, d(φ, φ) = 0.

Figure 2 .

 2 Figure 2. Ranking of the concepts w.r.t. the concept Flower where Rose is ranked 4 th with simo 1 (left) and 2 nd with simo 2 (right). To capture this difference, we introduce the notion of rank of a concept c 1 with regards to another concept c denoted by rank c1 φ (c) where: rank c1 φ (c) = |{s ∈ S c φ : s sim o (c 1 , c)}|. For a concept c having an equivalent, S c Φ is defined by: S c φ = {s ∈ [0, 1] : ∃c ′ ∈ E o ′ o such that sim o (c, c ′ ) = s} where E o ′ o designates the set of concepts of o having equivalents in o ′1 . We propose to measure the disorder around each concept. For a concept c ∈ E o ′ o , disorder (denoted by dis φ,φ ′ (c) and normalized in [0, 1]) is defined as:

  , N p1 2 = {p 2 , p 3 , p 4 , p 5 }. As p 1 , p 2 and p 5 use the semantic context φ, and p 3 and p 4 use φ ′ , we find: H 2 DapAvg 's value is weak, it means that participants are surrounded by participants able to "understand" them.

	Dap (M, p 1 ) = 3 5 d(φ, φ) + 2 5 d(φ, φ ′ ).
	As for the disparity unaware measure, a global mea-
	sure H n DapAvg can be obtained (cf. definition of H n RapAvg ).
	If H

We do not formally define the notion of equivalence of two concepts. The interested reader is invited to consult a reference book like[START_REF] Euzenat | Ontology matching[END_REF].


Thomas Cerqueus
email: thomas.cerqueus@univ-nantes.fr

Sylvie Cazalens
email: sylvie.cazalens@univ-nantes.fr

Philippe Lamarre
email: philippe.lamarre@univ-nantes.fr

Gossiping correspondences to reduce semantic heterogeneity of unstructured P2P systems

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

We consider peer-to-peer (P2P) data sharing systems where semantic meta-data are used to represent information and to enhance search. This general setting can be instanciated in different ways depending on the kind of meta-data used. We focus on applications where each peer uses an ontology to represent the information it stores. Typical examples are indexing documents or data sets with respect to the concepts of the ontology, or annotating the elements of a database schema with entities of the ontology.

The use of different ontologies results in semantic heterogeneity of the system. Because some peers are unable to precisely understand each others, some semantic interoperability has to be reached in some way. It is generally assumed that neighbour peers use alignments between their ontologies [START_REF] Euzenat | Ontology matching[END_REF]. Then, knowing correspondences between entities of ontologies, each peer translates incoming queries before forwarding them. This kind of approach works well in some cases, although it suffers from information losses due to several translations [START_REF] Halevy | Piazza: data management infrastructure for semantic web applications[END_REF][START_REF] Cudré | A necessary condition for semantic interoperability in the large[END_REF]. Moreover, it mainly focuses on leveraging interoperability without considering reducing semantic heterogeneity. Our goal is to define a class of algorithms that reduce the semantic heterogeneity of the P2P system, thus leveraging interoperability as a consequence. We proceed in two steps.

The first step consists in characterizing semantic heterogeneity. Apart from some intuitions like "the more different ontologies are used in the system, the higher heterogeneity is", or "the more alignments are known, the lower heterogeneity is", no definition of semantic heterogeneity exists (at least to our knowledge). Based on the observation that the concept of heterogeneity has several dimensions (or facets), we propose several definitions to capture them.

The goal of the second step is to define algorithms that make semantic heterogeneity decrease along some dimensions. Of course, a simple way to decrease heterogeneity is having the peers use exactly the same ontology. We believe that this is not realistic when peers are numerous and with different backgrounds. Hence we focus on solutions that have the peers increase their knowledge of alignments. Assuming that they join the system with already known alignments, the probability that all of them know exactly the same alignments is very low. Thus the idea is to make the peers share their knowledge by disseminating correspondences between entities of different ontologies. We consider a case where peers trust each others: no correspondence should be disregarded because it has been forwarded by an untrusted peer.

In order to implement dissemination of correspondences we use a gossiping algorithm in the sense of [START_REF] Kermarrec | Gossiping in distributed systems[END_REF]: each peer regularly picks up some other peer for a two-way information exchange. In our case, each peer selects some correspondences to send to another peer. This latter also selects correspondences and send them to the former. After several rounds correspondences disseminate across the system. The CorDis protocol is based on this idea. In addition, because peers generally have limited local storage, a scoring function is used to order the correspondences and store the most relevant ones. Relevance is computed considering a history of the incoming queries. We propose to favour the correspondences that involve entities that appeared in recent queries, and, to some extent chosen by the programmer, those involving entities belonging to ontologies referred to in recent queries. The scores of the correspondences are regularly updated, so that the CorDis protocol adapts the information exchange to the current queries.

In this paper, we bring several contributions. After presenting our formal model (section 2), we first propose several definitions of semantic heterogeneity measures, corresponding to different facets of this notion (section 3). Second, we propose the CorDis gossip-based protocol to disseminate correspondences across the system (section 4). It considers a history of queries to score the correspondences. Thus it ensures some flexibility with respect to current queries. Third, we report on several experiments conducted with the PeerSim simulator and fifteen ontologies from OntoFarm (section 5). The CorDis protocol is evaluated with respect to the proposed measures of semantic heterogeneity. The results show that CorDis significantly reduces several facets of heterogeneity while the network traffic and the storage space are bounded. This work builds on previous results concerning ontology mapping, ontology distances and gossiping algorithms. However, it does not have any equivalent among the previously proposed solutions to improve semantic interoperability (section 6).

The P2P system

We assume that each peer p has a unique identifier, denoted by id(p). To ensure relationships with other peers, peer p maintains a routing table table(p), composed of a set of peer identifiers which are called p's neighbours. Definition 1 (Unstructured P2P system) An unstructured P2P system is defined by a graph S = P, N , where P is a set of peers and N represents a neighbourhood relation defined by: N = {(p i , p j ) ∈ P 2 : p j ∈ table(p i )}.

In the system presented in Fig. 1 the neighbourhood of p 1 within a radius equal to 2 is composed of p 2 , p 3 , p 4 and p 5 .

Ontologies and alignments

We consider that an ontology is composed of a set of concepts C o , a set of relations R o (linking concepts) and a set of properties P o (assigned to concepts). The union of these three sets of entities is denoted by E o . In practice OWL [START_REF] Mcguinness | OWL web ontology language overview[END_REF] allows to represent ontologies by defining classes, datatype properties and object properties. We assume that each ontology is uniquely identified by an URI. Thus two ontologies are equal if and only if their URIs are the same. We assume that a peer uses the same ontology during its life-time.

An alignment process aims at identifying a set of correspondences between the entities of two ontologies [START_REF] Euzenat | Ontology matching[END_REF].

Definition 2 (Correspondence) A correspondence is a 4-tuple e, e ′ , r, n such that e (resp. e ′ ) is an entity from o (resp. o ′ ), r is a relation between e and e ′ , and n is a confidence value.

An alignment between ontologies of Fig. 2 could contain the correspondences: T hing 1 , T hing 2 , ≡, 1 , F lower 1 , F lower 2 , ≡, 1 , odour 1 , f ragrance 2 , ≡, 1 and Edelweiss 1 , F lower 2 , isA, 1 . Notice that an alignment is not necessarly perfect in the sense that some correct correspondences may be missing and others may be incorrect. Here, we assume that an alignment does not contain incorrect correspondences. Definition 3 (Peer-to-ontology mapping) Given a P2P system S = P, N and a set of ontologies O, a peer-to-ontology mapping is a function µ : P → O, mapping each peer to one ontology.

In order to understand incoming queries each peer must know correspondences. We denote by κ p the set of correspondences stored by a peer p and κ p (o, o ′ ) denotes the subset of κ p concerning ontologies o and o ′ .

Disparity between two peers

We introduce the notion of disparity function to quantify the difference between two peers. Definition 4 A disparity function d : P × P → [0, 1] is a function that assigns a real value in [0, 1] to a couple p, p ′ representing how much p ′ differs from p. It satisfies the minimality property: ∀p ∈ P, d(p, p) = 0, but we do not assume it is a mathematical distance.

There are different ways to define disparity and several proposals exist [START_REF] Maedche | Measuring similarity between ontologies[END_REF][START_REF] David | Ontology similarity in the alignment space[END_REF]. Some consider the alignments between the peers' ontologies [START_REF] David | Ontology similarity in the alignment space[END_REF].

Semantic heterogeneity of a system

The following definition states what a semantic heterogeneity function is. It does not mean that heterogeneity can be captured by a single measure. Rather, depending on the application, several complementary measures could be used.

Definition 5 Let SM be a set of models M = S, O, µ, d where S is a P2P system, O is a set of ontologies, µ is a peer-to-ontology mapping, and d is a disparity function between peers. A semantic heterogeneity measure is a function

H : SM → [0, 1] such that: -H(M) = 0 if |{o ∈ O : ∃p ∈ P s.t. µ(p) = o}| = 1 (minimality); -H(M) = 1 if ∀p = p ′ ∈ P, d(p, p ′ ) = 1 (maximality).
The conditions express that (i) homogeneity occurs when the same ontology is used by all the peers and that (ii) maximal heterogeneity occurs when all the disparities between peers are maximal.

In this section, we propose measures which are general enough to be used in many application domains while still being meaningful.

Disparity unaware measure

Notion of diversity is commonly used to measure the heterogeneity of a population (e.g. in biology). Richness partly characterizes the diversity of a population. In our context it depends on the number of different ontologies used in the system. If all the peers use the same ontology, then the system is completely homogeneous. By cons, the more ontologies there are, the more heterogeneous it is. This idea can be expressed by the following measure:

H Rich (M) = |o S | -1 |P| -1
where |o S | is the number of different ontologies used in the system S, and |P| the number of peers. In the system presented on Figure 1, four different ontologies are used by the ten participants: H Rich (M) = 4-1 10-1 = 0.33. Measuring richness allows to draw preliminary conclusions. In particular it gives information about the need of alignments to reach interoperability. A richness value equal to 0 means that heterogeneity is null: no alignment is needed to ensure interoperability in the system. A value equal to 1 means that heterogeneity is total: alignments are needed between each pair of participants to communicate.

Disparity aware measures

Topology unaware measure We propose to consider disparity between peers rather than only consider the ontologies they use. If the disparity between peers is globally important, it means that peers have important knowledge differences. The more different their knowledge, the harder to communicate (i.e. answering queries). Indeed an important loss of information will occur during query translation. As we do not take into account the system topology, we consider the disparity between each pair of peers:

H Disp (M) = 1 |P| 2 -|P| pi =pj ∈P d(p i , p j )
The H Disp measure determines if peers are globally disparate from each other.

Topology aware measure We propose to take into account how disparate peers are with regards to their neighbourhoods. If peers are globally far (semantically speaking) from their respective neighbourhoods, the system is highly heterogeneous. Contrariwise, if peers are close to their neighbourhoods, the system is weakly heterogeneous, even if the diversity of the system is not null.

We denote by N r (p) the neighbourhood of a peer p within a radius r. It is the set of peers accessible from p with l hops, where 1 l r. We consider that p does not belong to N r (p). We first propose a measure that focuses on a given peer and determines how this latter is understood by its neighbours:

H r Dap (M, p) = 1 |N r (p)| pi∈Nr(p) d(p, p i )
A global measure can be obtained:

H r DapAvg (M) = 1 |P| p∈P H r Dap (M, p)
If H DapAvg 's value is weak, it means that peers are globally close to their neighbours: each peer is surrounded by peers able to "understand" it.

Proposition 1. All the measures introduced in this section satisfy both properties of minimality and maximality (proof is trivial).

4 Gossiping correspondences

Principles of gossip-based protocols

Our approach is based on a gossip-based protocol that disseminates data [START_REF] Kermarrec | Gossiping in distributed systems[END_REF].

In such a protocol, each peer consists of two threads: an active and a passive one. The active thread is used to initiate communications with another peer. We assume that the peer selection is ensured by a peer sampling service, allowing peers to uniformaly and randomly select another peer [START_REF] Jelasity | The peer sampling service: Experimental evaluation of unstructured gossip-based implementations[END_REF]. Thus, each peer regularly contacts another peer to exchange information. We consider that the size of a message does not exceed m max . When a peer is contacted by another one (through the passive thread), the former has to answer by sending some information. Thus, both peers treat the received information. This principle is explicited by algorithms 1 and 2. In these algorithms, peers have to process two crucial tasks: data selection and data processing.

The CorDis protocol

The main idea of this protocol is to disseminate information over the network to share correspondences known by some but ignored by others in order to reduce some facets of semantic heterogeneity of the system. In the remaining of this work, we do not make any assumption about the way queries are transmetted in the system, but we consider that they are unchanged during the propagation: each peer receives the same query, and is responsible to translate it if necessary. When the process starts, each peer p knows some correspondences, a subset of which involves its own ontology (noted init p ). This subset of o p -correspondences (correspondences that involve its own ontology) should always be recorded by the peer. The purpose of dissemination is that each peer learns additional correspondences that might be useful to it to translate the queries it receives into its own ontology. We disseminate the correspondences by gossiping: Each peer p regurlarly initiates an exchange of correspondences with another peer p ′ . It selects some correspondences it knows and sends them to p ′ . In turn, p ′ chooses among the correspondences it stores and send them to p.

Storage of correspondences

Each peer must store the correspondences it has been informed of in some cache, of limited size, thus preventing the peer from storing all the correspondences. Choice of the correspondences to keep is obtained by a scoring function which enables to order the correspondences: only the best ones are kept. In theory, the scoring function could be specific to each peer. Here we propose that each of them consider a history of the received queries.

A history of received queries is made of two lists L 1 and L 2 . List L 1 contains the entities used in the last k received queries, while L 2 contains the ontologies used to express the last k ′ received queries. Notice that an item can appear several time in a list if it has been involved in several queries. The intuition of the scoring function is that peers favour the correspondences that might be useful for translating queries (it can be useful locally, or for others). The coefficient ω ∈ [0, 1] is used for giving more or less importance to a correspondence involving entities that do not appear in recent queries, but that belong to ontologies used recently. If the focus of interest of the queries changes, the scoring values of the correspondences will change, giving more importance to relevant correspondences. Scores are regularly calculated to take dynamicity into account.

Because the correspondences involving its own ontology are of prime importance for the peer, we propose that it tries to store as much possible of them (or all of them if possible) in a specific repository, including init p , distinct from the cache which is then devoted to the other correspondences. If the repository is too small for storing all the o p -correspondences, the peer can use the scoring function to eliminate some of them. We denote by repository(p) the repository of a peer p, and by cache(p) its cache (respectively limited to r max and c max entries).

Data selection When a peer has to send correspondences, it selects them from both the cache and the repository. We introduce the number π ∈ [0, 1] to repre-sent the ratio of correspondences to select in both sets. Thus, a peer randomly selects [π • m max ] correspondences in its repository, and [(1π) • m max ] in its cache. Fig. 3 summarizes this process. Random selection is used to ensure that two correspondences of the repository (resp. the cache) have the same probability to be sent. Data processing When a peer p receives a message, it executes two main tasks. First it computes the score of the correspondences in msg and then merges them with its local data. It only consists in adding o p -correspondences in repository(p) and the others in cache(p) and re-order the correspondences. If a correspondence is already stored, the newest score is used. Then, the best r max (resp. c max ) correspondences are kept in the repository (resp. in the cache).

Preliminary experiments

In this section we study the performances of our protocol w.r.t. application parameters, initial heterogeneity, and dynamicity of the system. We used the PeerSim simulator [START_REF] Jelasity | The Peersim simulator[END_REF] to generate P2P systems as directed graphs. In order to simulate real-world situations we use the OntoFarm dataset [START_REF] Šváb | Ontofarm: Towards an experimental collection of parallel ontologies[END_REF][START_REF] David | Ontology similarity in the alignment space[END_REF]. It is composed of fifteen ontologies, expressed in OWL, dealing with the conference organization domain. Ontologies are composed of 51 concepts in average (between 14 and 141) and their average volume is 41.3 KB (between 7.2 KB and 100.7 KB). We use a Poisson law to distribute ontologies in the system. Thus some ontologies are more used than others. We consider it as a realistic situation. As we only have fifteen ontologies, we consider relatively small systems (i.e. with 100 peers) to ensure a sufficient degree of heterogeneity. Moreover each peer has three other peers as neighbours.

We set π = 0.5 so that correspondences are fairly kept from the repository and the cache. Furthermore we consider that histories constantly change over time: scoring function values vary continually. It is considered as a critical situation.

We exploit the alignments used in [START_REF] David | Ontology similarity in the alignment space[END_REF] as reference alignments between ontologies. In average 98 correspondences are available from one ontology to others (altogether 1470 correspondences). As each correspondence is an equivalence between two concepts (with n = 1), we adapt the coverage measure presented in [START_REF] David | Ontology similarity in the alignment space[END_REF] as the measure of disparity between two peers. It is defined as:

d(p, p ′ ) = |{e ∈ E o : ∀e ′ ∈ E o ′ , ∄ e, e ′ , ≡, 1 ∈ κ p ′ (o, o ′ )}| |E o |
where o and o ′ are the ontologies of p and p ′ , and κ p ′ (o, o ′ ) is the set of correspondences that p ′ knows between o and o ′ . This definition expresses how p ′ can understand p's queries. In all experiments we measure the extent and speed of heterogeneity decrease enabled by CorDis considering H Disp and H DapAvg . Because of space limitation we only report on H Disp , as H DapAvg behaves the same way.

Impact of application parameters

In these experiments we study the impact of the volume of stored data (r max and c max ), the network traffic (m max ) and the initial knowledge of peers (we set different quantities of known correspondences: init p ). We consider five configurations (see Table 4). The configuration c ref serves as a reference. For these experiments we consider that fifteen different ontologies are used. Consequently H Rich equals 0.14.

Given the alignments of reference, the heterogeneity H Disp cannot be reduced below a certain theoric limit equal to 0.704 (cf. the solid black line on Fig. 5). This limit can be reached if the storage capacity of peers is unlimited, and if each peer p knows all the o p -correspondences available in the system. We anticipate that CorDis will not reduce the heterogeneity below this limit.

The graph of Fig. 5 shows that the CorDis protocol reduces H Disp in all the configurations we set. These results allows to draw (predictable) conclusions: (i) the less peers know initially, the harder it is to reduce the heterogeneity (cf. c 1 ), (ii) the more useful information peers store, the less heterogeneous the system becomes (cf. c 2 ), and (iii) the less information peers share, the slower the heterogeneity decreases (cf. c 4 ). Nevertheless we can see that the increase of peers' cache (cf. c 3 ) does not have an important impact on heterogeneity decrease. After 50 cycles, H Disp does not significantly vary anymore.

Impact of semantic richness

In these experiments we study the impact of richness heterogeneity. We vary the number of used ontologies in the system from 1 (homogenous system) to 15 (number of available ontologies in OntoFarm). As a consequence, the richness value H Rich varies between 0 and 0.14. We set the other parameters as in the configuration c ref of the section 5.1.

Fig. 6 shows that CorDis is efficient for all the situations considered in these experiments. We plan to conduce additional experiments to show that CorDis is also efficient in highly heterogeneous systems.

Impact of new arrivals

In these experiments we study the impact of peers arrival in an existing system. We consider four configurations. The first one (ref 1 ), represents a system of 100 peers (using 10 different ontologies: H Rich = 0.09) in which CorDis is running. The second configuration (ref 2 ) is similar to the first one but represents a system of 110 peers (using 15 different ontologies: H Rich = 0.14). They both serve as references. In the other scenarios, 10 peers join the system simultaneously at the 50 th cycle (c 1 ) or one after the other between the 50 th cycle and the 95 th cycle: every 5 cycle a new peer joins the system (c 2 ). In both configurations, arriving peers use ontologies that are not already used, so H Rich grows up to 0.14. Fig. 7 shows that when a group of peers join the system, an important disruption occurs. But after 40 cycles, arriving peers are integrated in the system as if they were in it from the beginning. When peers join the system progressively, they are quickly integrated (20 cycles). As a conclusion, we can say that CorDis is robust to new arrivals.

Related work

Our measures of semantic heterogeneity assume the existence of a disparity measure between peers. Distance measures proposed in the field of ontology matching [START_REF] Euzenat | Ontology matching[END_REF][START_REF] Maedche | Measuring similarity between ontologies[END_REF] can be adapted, even if they do not take into account alignments between ontologies. In [START_REF] David | Ontology similarity in the alignment space[END_REF] distances between ontologies are defined in the alignment space. They can be used if we consider that queries are translated at each hop. In [START_REF] Cudré | A necessary condition for semantic interoperability in the large[END_REF], authors define criteria to characterize the interoperability of a P2P system, but no measure is proposed to define the semantic heterogeneity of P2P systems.

CorDis aims to improve interoperability of the system by reducing some facets of the heterogeneity. Other methods have been proposed to improve interoperability. For instance in [START_REF] Aberer | A framework for semantic gossiping[END_REF] authors aim to achieve a form of semantic agreement to enable queries to be forwarded to the peers that understand them best, i.e. with a good degree of comprehension and with correct mappings. In order to build such a system, queries are enriched with the translations used during the propagation. It enables peers to assign confidence values to the mappings. In [START_REF] Aberer | A framework for semantic gossiping[END_REF][START_REF] Aberer | Gridvine: Building internet-scale semantic overlay networks[END_REF], the term semantic gossiping refers to the action of "propagating queries toward nodes for which no direct translation link exists". This is a very specific approach of gossiping which mixes both queries propagation and their translations dissemination. On the contrary our approach is independent of queries propagation and only focuses on the dissemination of correspondences. In [START_REF] Cudré-Mauroux | Self-organizing schema mappings in the GridVine peer data management system[END_REF] authors propose a system ensuring interoperability by offering several functionnalities to automatically organize the network of mappings at a mediation layer. Again this work can be considered as complementary to ours in the sense that the mecanism to detect the condition of strong connectivity [START_REF] Cudré | A necessary condition for semantic interoperability in the large[END_REF] could also be put in place in the systems we consider. Others try to improve interoperability by creating a global ontology that serves as an intermediary between all peers of the system [START_REF] Camargo | Integrating ontologies based on P2P mappings[END_REF]. Pires et al. [START_REF] Eduardo Pires | A semantic-based ontology matching process for PDMS[END_REF] present a semantic matcher which identifies correspondences between ontologies used in a PDMS. This method could be used in our context to discover correspondences, i.e. to initialize peers' alignments or to enrich them. In [START_REF] Penzo | Semantic peer, here are the neighbors you want![END_REF] authors propose to group related peers in SONs to improve interoperability. This approach is complementary to ours because they can be combined: one aims to reduce heterogeneity, and the other one aims to improve information retrieval performances.

Conclusion

With the aim of improving semantic interoparability in P2P data sharing systems we presented a new approach that consists in decreasing semantic heterogeneity. As none existed before, at least to our knowledge, we defined several measures to characterize different facets of the semantic heterogeneity of a P2P system. These measures are general enough to be used in several application domains. We proposed a new protocol, called CorDis, which relies on a gossip-based dissemination of correspondences across the system. It ensures some flexibility with respect to current queries. We conducted preliminary experiments which show that CorDis significantly reduces several facets of semantic heterogeneity. Finally, CorDis does not have any equivalent among the previously proposed solutions to improve semantic interoperability.

As future work, we first plan to conduct additional experiments with real query sets and more ontologies, as in some way, the number of ontologies limits the number of peers in the simulations. In addition, our proposal provides a basis that may be extended in several complementary directions. First, we could add a mechanism of deduction to discover new correspondences. Second, knowing correspondences might incite some peers to change their neighbourhood, thus leading to a dynamic evolution of connections. Finally, a good knowledge of alignments between its own ontology and another one might result in a peer to adopt an additional ontology, or to change it. All these directions may help in reducing more and faster some facets of heterogeneity.

Fig. 1 .

 1 Fig. 1. Unstructured P2P system.

Fig. 2 .

 2 Fig. 2. Two ontologies o1 and o2 composed of concepts, properties and relations.

Definition 6 (

 6 Scoring function) Given a set of correspondences C, we define the scoring function of a peer sc : C → [0, 1] as: sc( e, e ′ ) = ω • [f 1 (e) + f 1 (e ′ )] + (1ω) • [f 2 (o) + f 2 (o ′ )] where e ∈ o, e ′ ∈ o ′ , and f 1 (resp. f 2 ) measures the frequency of occurence of an element in L 1 (resp. L 2 ).

Fig. 3 .

 3 Fig. 3. Data selection process.

i n i t p r m a x c m a x m m aTab. 4 . 5 .

 45 Configurations studied in section 5.1, and theorical analysis of the local storage (LS) per peer, and the network traffic (NT) per cycle. Fig. Decrease of HDisp heterogeneity.

Fig. 6 .

 6 Fig. 6. Evolution of HDisp in different situation of semantic richness.

Fig. 7 .

 7 Fig. 7. Evolution of HDisp, and impact of peers arrival.