Na Pathathai
email: pathathai.na-lumpoon@imag.fr

Mu Lumpoon

Teerawat Lei

Ahmed Kamnardsiri
email: teerawat.kamnardsiri@imag.fr

Marie-Christine Lbath

Fauvet

Illustrating some issues raised when designing context-aware personalized services for mobile users

Keywords: Mobile Computing, Recommendation Systems, Context Aware and Personalized Services, Mobile Tourism, Users' Privacy

When travelling people might seek for help or any sorts of information. For example, travelers might need suggestions about accommodation, transportation, activities, food, etc. while they are travelling. Moreover, they expect to get suggestions which are personalized according to some specific criteria such as preferences, age, location, etc. This paper sketches a framework named Context-Aware Recommender for Mobile Users that is responsible for providing users with personalized recommendations in order to deliver them the right service to the right user at the right time with the respect of their privacy.

I. INTRODUCTION AND MOTIVATING EXAMPLE

With the advent of pervasive computing, several research fields and directions have emerged in computer science. One of them is about context-aware and personalized applications or softwares that are meant to fulfill mobile users' needs. These applications and softwares are challenged to locate and deliver the right service to the right person, at the right time and location, with the appropriate rendering. We adopt the definition of service given by the W3C [START_REF] W3c | Web services glossary[END_REF]: A service is an abstract resource that represents a capability of performing tasks that form a coherent functionality from the point of view of providers entities and requesters entities. To be used, a service must be realized by a program acting on behalf of a person or organization (i.e. the provider).

The study reported in this paper is a part of a broader project which aims at designing and implementing a framework which provides context-aware personalized services for mobile users. To achieve such a goal, issues to be addressed are related to system design, software architecture, distributed and heterogeneous resource access and integration, quality of service requirements, and information synchronization when switching between connected and disconnected mode.

As an illustrating example, we consider the following scenario: Peter is traveling in Chiang Mai Province, Thailand. He is standing near by the monument of Three Kings. Using his smart-phone and logged on our recommendation system, he enters the query: I would like to know whether there are any places of interest located around here. I am interested also in booking a 2 day-tour starting tomorrow. The result returned to Peter is: i) a list of points of interests (museums within Three King monument area) and ii) a two day-tour booking in the bush around Chiang Mai City, resulting from some interactions with the appropriate tour operator company.

Processing Peter's query involves the selection, integration and orchestration of web services that meet the most Peter's needs according to his context and profile. Here we consider the following definitions for context, profile and web service concepts. A context includes spatial, temporal, physical and environmental properties that could be collected by sensors embedded in the devices used to submit the queries. Such properties are for example: GPS location, timestamp, external temperature, screen size, etc. A profile captures users' personal details, preferences and centers of interest. For instance, a profile could contain information about users' age, citizenship, gender, occupation, favorite recreational activities, etc. Back to our motivating example, the context of Peter's query is [city: Chiang Mai, location: the monument of Three King, coordinates: 18 • 50'14"N 98 In this paper, we consider the concept of web service as defined by the W3C [START_REF] W3c | Web services glossary[END_REF]: A Web service is a software system designed to support interoperable machine-to-machine interaction over a network. It has an interface described in a machine-processable format (specifically WSDL 1 ). Other systems interact with the Web service in a manner prescribed by its description using SOAP 2 messages, typically conveyed using HTTP with an XML serialization in conjunction with other Web-related standards.

The remainder of this paper is organized as follows. First we give an overview of the system functionalities and architecture in Section II. Next, in Section III, we introduce our approach to recommendation. Section IV discusses service integration and orchestration. Finally, section V gives a brief overview of related work and provides some concluding remarks.

II. ARCHITECTURE

As shown in Figure 1, the system we propose is composed of two main components: (1) MS-S Mobile Server which is 1 Web Service Description Language 2 Simple Object Access Protocol responsible for accepting requests from users, processing requests (e.g. finding a composition of services that fits the most the request), and binding the resulting composition with the requester; (2) M-App an application running on users' mobile device which is responsible for collecting and maintaining information users accept to store and disclose to MS-S Mobile Server.

Fig. 1. Push and pull interaction modes between users and MS-S Server

We assume that users' mobile devices are capable of running a browser for accessing MS-S Server and a mailer for receiving notifications. Using the browser users can access the MS-S Mobile server in order to submit requests. This communication mode between users and the server is called "pull mode". The server can also contact users by proposing services that might be useful. This latter communication mode is called "push mode". Figure 2 illustrates the architecture we propose for our context aware recommendation system. Components are described below.

The component Portal is a web application providing the needed functionality to support the proper method to interact with users. The Portal builds the query Q (the requested query from users), and analyses Q with User and Context Management component to generate Q' (the detailed query with user information).

The Recommender is a matching component which offers the prediction techniques to provide a list of recommended services discovered in Service Description matched on users' profile and context. However, the system keeps recommendation patterns to be used for machine learning in Recommendation Management component. Consequently, the actual output of Recommender is a list of service, service control flow and recipient noted as R in the architecture.

The Binder is a component which uses semantic technique to R to generate a list of service orchestration models noted as O. O is a group of codes later sent to M-App to be executed.

The recommendation management component handles a set of recommendation and orchestration models. Service Description handles a set of business services such as hotel, restaurant, shopping and etc.

As already said, there are two delivery service approaches which are pull and push services. The workflow of pull and push services is displayed in the architecture. To achieve the first one, mobile user submits query Q through his browser to The Recommender processes Q" to conduct a list of services R' used to deliver to mobile users later on. The more information regarding to Recommender is discussed in the next section.

III. RECOMMENDATION

The component recommender in the architecture we proposed in this paper works as a matching component, with the help of the component Service Management, it's responsible for searching web services to answer queries submitted by users, their context and users' profile.

In the recommender, we aim to provide recommendation selected from existing Service Descriptions (denoted by S), according to the standardized user's query enriched with the context and user's profile (denoted Q'), the group profile (noted P) and group context (noted C) from the cluster which the user belongs to. The output of this component (noted R) contains Q' and a list of services. Finally, R is sent to the component "Binder" which is, in turn, 0responsible for integrating the returned services and orchestrating them (see Section IV).

The process of generating R from Q' is carried out respecting users' privacy.

In order to predict the user's potential interests properly, the components Profile Management and Context Management classify or cluster profiles and contexts stored in the database, dividing them into different groups by calculating the similarity. The recommender learns from Q' the user's profile and context, finds the group which is the most similar to the user, picks up the group profile (P) and group context (C). Q'+P+C works as a filter, to find the highly customized recommendation of services in the Services Description, by Services Description Management. Back to our motivating example, Peter is after places of his interests in the area of the Three King Monument as well as a 2 day-tour package starting June 26. Among all web services whose descriptions are managed by the component Service Management (see Figure 2), the recommender has selected 2 web services: (i) http://www.chiangmaitourism.org which exposes, among others, one operation that returns a list of points of interests located in a given area in Chiang Mai city; (ii) http://www.adventure.tour.th which exposes 2 operations: the first one returns a list of packages offered for a given duration and an area around Chiang Mai and the second one for booking a selected package, charged on a credit card given by its number.

While users are interacting with the system, their privacy has to be considered. Privacy may has different meanings to different users. For example, Peter does not want the others to know his current location, while Mary may consider that this is not an issue. Privacy requirements, specific to each class of users, have to be captured and stored by the system. Also, user's private information may be leaking during the processes of information collection, storage, and clustering/classification.

Conducting the storage and packaging of user profiles on the client side, and developing the privacy sensitive algorithm for users' profile clustering or classification to prevent users' privacy from disclosing will be explored in future work.

IV. INTEGRATION AND ORCHESTRATION

This section intends at introducing issues raised by integration, composition and execution of heterogeneous services that have been recommended. The services we consider could be either stateless or stateful and might offer more than only one operation. Among others, these issues are:

-Specification of an orchestration model according to the output of the recommender (e.g. descriptions of the selected services).

-Syntactic and semantic integration of these services.

The component Binder generates an orchestration model that specifies both control flow and data flow such as the services returned by the Recommender can be executed. The control flow is captured by an oriented graph whose nodes are web service operations and oriented edges from one node O1 to another O2 means that the operation associated with O2 has to be executed before the one associated with O1. The choice of the web service http://www.adventure.tour.th is driven by Peter's profile (Peter likes hiking and adventure). The duration and the choice of a list of POIs are deduced from the query. All others have to be given by the user via some interactions (see callouts in Figure 3). These later interactions are generated by the component Binder according to the descriptions of the participating services.

V. CONCLUSION Many of previous works are related to context recommendation services applied in travel and tourism domain. Murshid provides guidance using context model of user location, user profile, date, event information and user interaction to user visiting a country for tourism or business [START_REF] Echtibi | A servicebased mobile tourist advisor[END_REF]. LiveCities similar to Murshid focused on the push service notification to mobile device according to the visitors' context on a defined area [START_REF] Martin | A contextual geofencing mobile tourism service[END_REF]. However, [START_REF] Echtibi | A servicebased mobile tourist advisor[END_REF] and [START_REF] Martin | A contextual geofencing mobile tourism service[END_REF] are designed specifically for mobile service model in tourism domain. AIDAS is a middleware to support user-centric semantic service discovery based on user/device/service profile (meta data), which uses Semantic-based discovery to support mobile context-aware service access [START_REF] Toninelli | Semantic-based discovery to support mobile contextaware service access[END_REF]. Nevertheless, AIDAS middleware does not support automatic workflow generation. The last related work [START_REF] Bhuvaneswari | Reengineering semantic web service composition in a mobile environment[END_REF] is the closet to our work. The system has workflow process using semantic matching with evaluation of QoS and syntactic mapping to satisfy user query. However, [START_REF] Bhuvaneswari | Reengineering semantic web service composition in a mobile environment[END_REF] does not provide push service mode and focus less on user profile.

In this paper we have presented a framework dedicated to the design and development of Context-Aware Recommender for Mobile Users that aims to deliver the right service to the right user at the right time with respect of the users privacy.

Currently, we are working on the definition of the formal model supporting the framework including standardized architecture with a recommender system that takes into account the respect of users privacy. For experimental validation purpose, we plan to implement the framework presented here, and apply it to mobile tourism application domain.

Fig. 2 .

 2 Fig. 2. Context aware recommendation system logical architecture

Fig. 3 .

 3 Fig. 3. Orchestration model with user interactions

ACKNOWLEDGMENT This presented work is supported by European Commission in Sustainable e-Tourism: Erasmus Mundus Action 2 Program.


Trong-Ton Pham
email: ton.pham@imag.fr

Loïc Maisonnasse

Philippe Mulhem
email: philippe.mulhem@imag.fr

Jean-Pierre Chevallet
email: jean-pierre.chevallet@imag.fr

Georges Quénot
email: georges.quenot@imag.fr

Rami Al Batal
email: rami.albatal@imag.fr

MRIM-LIG at ImageCLEF 2009: Robotvision, Image annotation and retrieval tasks

This paper describes mainly the experiments that have been conducted by the MRIM group at the LIG in Grenoble for the the ImageCLEF 2009 campaign, focusing on the work done for the Robotvision task. The proposal for this task is to study the behaviour of a generative approach inspired by the language model of information retrieval. To fit with the specificity of the Robotvision task, we added post-processing in a way to tackle with the fact that images do belong only to several classes (rooms) and that image are not independent from each others (i.e., the robot cannot in one second be in three different rooms). The results obtained still need improvement, but the use of such language model in the case of Robotvision is showed. Some results related to the Image Retrieval task and the Image annotation task are also presented.

Introduction

We describe here the different experiments that have been conducted by the MRIM group at the LIG in Grenoble for the ImageCLEF 2009 campaign, and more specifically for the Robotvision task. Our goal for this task was to study the use of language models in the context where we try to guess in which room a robot is in a partially known environment. Language models for text retrieval where proposed ten years ago, and behave very well when all the data cannot be directly extracted from the corpus. We have already proposed such application for image retrieval in [START_REF] Pham | Visual language model for scene recognition[END_REF], achieving very good results. We decided to focus on this challenging task represented by the Robotvision task in CLEF 2009. We also participated to the Image retrieval and the image annotation task for CLEF 2009, and we discuss briefly, because of space constrains, some of our proposal and results.

The paper is organized as follows. First we describe the Robotvision task in section 2, our proposal based on language models and the results obtained. In this section, we focus on the features that were used to represent the images, before describing the language model defined on such representation and the post-processing that took advantage of the specificity of the Robotvision task. Because the MRIM-LIG research group participated in two other image related tasks, we propose in section 3 to describe shortly our main proposals and finding for the image annotation and the image retrieval tasks. We conclude in section 4.

Robovision Track

Task description

The Robotvision task at CLEF 2009 [START_REF] Caputo | Overview of the clef 2009 robot vision track[END_REF], aims at determining "the topological location of a robot based on images acquired with a perspective camera mounted on a robot platform." A robot is moving on a building floor, going across several (six) rooms, and an automatic process has to indicate, for each image of a video sequence shot by the robot, in which room is the robot. In the test video, a additional room (which was not given in the training set), unknown, is present and has also to be tagged automatically. The full video set is the IDOL video database [START_REF] Luo | Incremental learning for place recognition in dynamic environments[END_REF].

Image representation

We have applied a visual language modeling framework for the Robotvision task. This generative model is quite standard in the Information Retrieval field, and already lead to good results for visual scene recognition [START_REF] Pham | Visual language model for scene recognition[END_REF]. Before explaining in detail the language modeling approach, we fix some elements related to the feature extractions of images. To cover the different classes of features that could be relevant, we have extracted color, texture, and region of interest features in our proposal. These features are: HSV color histogram: we extract the color information from HSV color space. One image is represented by a concatenation of n×n histograms, according to non overlapping rectangular patches defined from a n×n grid applied on the image. Each histogram has 512 dimensions; Multi-scale canny edge histogram: we used Canny operator to detect the contour of objects as presented in [START_REF] Chee Sun Won | Efficient use of mpeg-7 edge histogram descriptor[END_REF]. An 80-dimensional vector was used to capture magnitudes and gradient of the contours for each patch. This information is extracted from a grid of m×m for each image; Color SIFT: SIFT features are extracted using D. Lowe's detector [START_REF] David | Distinctive image features from scale-invariant keypoints[END_REF]. Region around the keypoint is described by a 128-dimensional vector for each R, G, B channel. Based on the usual bag of visual words approach, we construct for each of the features above a visual vocabulary of 500 visual words using k-means clustering algorithm. Each visual word is designated to a concept c. Each image will then be represented using theses concepts and the language model proposed is built on these concepts.

Visual language modeling

The language modeling approach to information retrieval exists from the end of the 90s [START_REF] Ponte | A language modeling approach to information retrieval[END_REF]. In this framework, the relevance status value of a document for a given query is estimated by the probability of generating the query from the document. Even though this approach was originally proposed for unigrams (i.e. isolated terms), several extensions have been proposed to deal with n-grams (i.e. sequences of n terms) [START_REF] Song | general language model for information retrieval[END_REF][START_REF] Srikanth | Biterm language models for document retrieval[END_REF], and, more recently, with relationships between terms and graphs. Thus, [START_REF] Gao | Dependence language model for information retrieval[END_REF] proposes (a) the use of a dependency parser to represent documents and queries, and (b) an extension of the language modeling approach to deal with such trees. [START_REF] Maisonnasse | Revisiting the dependence language model for information retrieval[END_REF][START_REF] Maisonnasse | Multiplying concept sources for graph modeling[END_REF] further extend this approach with a model compatible with general graphs, as the ones obtained by a conceptual analysis of documents and queries. Other approaches (as [START_REF] Fergus | A sparse object category model for efficient learning and exhaustive recognition[END_REF][START_REF] Gosselin | Kernels on bags of fuzzy regions for fast object retrieval[END_REF]) have respectively used probabilistic networks and kernels to capture spatial relationships between regions in an image. In the case of [START_REF] Fergus | A sparse object category model for efficient learning and exhaustive recognition[END_REF], the estimation of the region probabilities relies on an EM algorithm, which is sensitive to the initial probability values. In contrast, in the model we propose, the likelihood function is convex and has a global maximum. In the case of [START_REF] Gosselin | Kernels on bags of fuzzy regions for fast object retrieval[END_REF], the kernel used only considers the three closest regions to a given region. In [START_REF] Pham | Visual language model for scene recognition[END_REF], we have presented the image as a probabilistic graph which allows capturing the visual complexity of an image. Images are represented by a set of weighted concepts, connected through a set of directed associations. The concepts aim at characterizing the content of the image whereas the associations express the spatial relations between concepts.

Our assumption is that the concepts are represented by non-overlapping regions extracted from images. In this competition, the images acquired by the robot are of poor quality, and we decided to not take into account the relationship between concepts. We thus assume that each document image d (equivalent each query image q) is represented by a set of weighted concepts W C . The concepts correspond to a visual word used to represent the image. The weight of concepts captures the number of occurrences of this concept in image. Denoting C the set of concepts over all the whole collection, W C can be defined as a set of pairs (c, w(c, d)), where c is an element of C and w(c, d) is the number of times c occur in the document image i. We are then in a context similar to usual language model for text retrieval. We rely then on a language model defined over concepts, as proposed in [START_REF] Maisonnasse | Model fusion in conceptual language modeling[END_REF], which we refer to as Conceptual Unigram Model. We assume that a query q or a document d is composed of a set W C of weighted concepts, each concept being conditionally independent to the others. Unlike [START_REF] Maisonnasse | Model fusion in conceptual language modeling[END_REF] that computes a query likelihood, we evaluate the relevance status value rsv of a document image d for query q by using a generalized formula, the negative Kullback-Leiber divergence, noted D. Such divergence is computed between two probability distributions: the document model M d computed over the document image d and the query model M q computed over the query image q. Assuming the concept independence hypothesis, this leads to:

RSV kld (q, d) = -D (M q M d ) (1)
∝ ci∈C log(P (c i |M q ) * P (c i |M d )) (2)
where P (c i |M d ) and P (c i |M q ) are the probability of the concept c i in the model estimated over the document d and query q respectively. If we assume a multinomial models for M d and M q , P (c i |M d ) is estimated through maximum likelihood (as is standard in the language modeling approach to IR), using Jelinek-Mercer smoothing:

P (c i |M d ) = (1 -λ u ) F d (c i ) F d + λ u F c (c i ) F c (3)
where F d (c), representing the sum of the weight of c in all graphs from document image d and F d the sum of all the document concept weights in d. The functions F c are similar, but defined over the whole collection (i.e. over the union of all the images from all the documents of the collection). The parameter λ u helps taking into account reliable information when the information from a given document is scarce. For this part, the quantity P (c i |M q ) is estimated through maximum likelihood without smoothing on the query. The final result L(q i ) for one query image i is a list of the images d j from the learning set ranked according to the RSV kld (q i , d j ) value.

Post-processing of the results

As we just mentioned, in this basic case we may associate the query image with the room id of the best ranked image. However, because we represent each image with several features and because we have several images of each room in the training set, we post-process this basic result:

-Fusion: an image is represented independently for each feature considered (color with a given grid, texture with a given grid, regions of interest). Each of these representations lead to different matching results using the language model. We choose to make a late fusion of the three results obtained using a linear combination:

RSV (Q, D) = i RSV kld (q i , d i ) (4)
where Q and D correspond to the image query and documents, and q i and d i describe the query and the document according to a feature i. -Grouping training images by their room: assuming that the closest training image of a query image is not sufficient to determine the room because of their intrinsic ambiguity, we propose to group the results of the n-best images for each room. We are then able to compute a ranked list of room RL instead of an image list for each query image:

RL q = [(r, RSV r (q, r)] with RSV r (q, r) = f n-best (q,r) RSV (q, d) (5)
where r corresponds to a room and f n-best is a function that select the n images with the best RSV belonging to the room r. -Filtering the unknown room: in the test set of the Robotvision task, we know that one additional room is added. To tackle this point, we assume that if one room r is recognized, then the matching value for r is significantly larger than the matching value for the other rooms, especially compared to the room with the lower matching value. So, if this difference is large (> β), we consider that there is a significant difference and then we keep the tag r for the image. Otherwise we consider the image room tag as unknown. In our experiment, we fixed the threshold β to 0.003 after experiments. -Smoothing window: we exploit the visual continuity in a sequence of images by smoothing the result across the temporal axis. To do that, we use a flat (i.e., all the images in the window have the same weight) smoothing window centered on the current image. In the experiments, we choose the width of window w = 40 (i.e. 20 images before and after the classified image).

Validating process

The validation aims at evaluating robustness of the algorithms to visual variations that occur over time due to the changing conditions and human activity. We trained our system with the night3 condition set and tested against all the other conditions from validation set. Our objective was to understand the behavior of our system with the changing conditions and with different types of features. We first study the models one by one. We built 3 different language models corresponding with 3 types of visual features. We noticed that, in the same condition (e.g. night-night), the HSV color histogram Mc outperforms the two other models. However, in different conditions, the result of this model dropped significantly (from 84% to 29%). On the other hand, the edge model (Me) and the SIFT color model (Ms) are more robust to the change of conditions. In the worst condition (night-sunny), it still obtains a recognition rate of 52% for Me and 55% for Ms. As the result, we choose to consider only the edge histogram and SIFT feature for the official runs. Then, we studied the impact of the post-processing on the ranked list of the models Me and Ms on the recognition rate in Table 2. The fusion of the 2 models leads to an overall 8% of improvement. The regrouping step helped to pop-up some prominent rooms from the score list by averaging room's n-best scores. The filtering, using the threshold β=0.003, eliminated some of the uncertain decisions. Eventually, the smoothing step with a window size of 40 helped to increase the performance of a sequence of images significantly, by more than 20% compared to the initial result.

Submitted runs and results

For the official test, we have constructed 3 models based on the validating process. We eliminated the HSV histogram model because of its poor performance on different lighting conditions and there was a little chance to have the same condition. We used the same visual vocabulary of 500 visual concepts generated for night3 set. Each model provided a ranked result corresponding with the test sequence released. The post-processing steps were performed similarly to the validating process employing the same parameters. The visual language models built for the competition are: Me1: visual language model based on edge histogram extracted from 10x10 patches division; Me2: visual language model based on edge histogram extracted from 5x5 patches division, and Ms: visual language model based on color SIFT local features. Our test has been performed on a quad core 2.00GHz computer with 8Gb of memory. The training took about 3 hours on a whole night3 set. Classification of the test sequence was executed in real time. Based on the 3 visual models constructed, we have submitted 4 valid runs to the ImageCLEF evaluation (our runs with smoothing windows were not valid).

-01-LIG-Me1Me2Ms: linear fusion of the results coming from 3 models (score = 328). We consider this run as our baseline; -02-LIG-Me1Me2Ms-Rk15: re-ranking the result of 01-LIG-Me1Me2Ms with the regrouping of top 15 scores for each room (score = 415); -03-LIG-Me1Me2Ms-Rk15-Fil003: if the result of the 1st and the 4th in the ranked list is too small (i.e. β = 0.003), we remove that image from the result list (score = 456.5); -05-LIG-Me1Ms-Rk15: same as 02-LIG-Me1Me2Ms-Rk15 but with the fusion of 2 types of image representation. (score = 25);

These result show that the grouping increases results by 27% compared to the baseline. Adding a filtering after the grouping increases again the results, gaining more that 39% compared to the baseline. The use of SIFT features is also validated: the result obtained by the run 05-LIG-Me1Ms-Rk15 in not good, even after grouping the results by room. Our best run 03-LIG-Me1Me2Ms-Rk15-Fil003 for the obligatory track is ranked at 12 th place among 21 runs submitted in overall. We conclude from these results that the use of post-processing is a must in the context of Robotvision room recognition.

Image retrieval and Image annotation tasks results

This paper focuses on the robovision task, but the MRIM-LIG group also submitted results for the image annotation and the image retrieval tasks. For the image annotation task, we tested a simple late fusion (selection of the best) based on three different sets of features: RGB colors, SIFT features, and an early fusion of hsv color space and Gabor filters energy. We tested two learning frameworks using SVM classifiers: a simple one against all, and a multiple one against all inspired from the work of Tahir, Kittler, Mikolajczyk and Yan called Inverse Random Under Sampling [START_REF] Tahir | A multiple expert approach to the class imbalance problem using inverse random under sampling[END_REF]. As a post processing, we applied on all our different runs a linear scaling in a way to fit the learning set a priori probabilities. We took afterward into account the hierarchy of concept in the following way: a) when conflicts occur (for instance the tag Day and the tag Night are associated to one image of the test set), we keep unchanged the larger value tag, and we decrease (linearly) the value all the other conflicting tags, b) we propagated the concepts values in a bottom-up way if the values of the generic concept is increased, otherwise we do not update the pre-existing values. The best result that we obtained was 0.384 for equal error rate (rank 34 on 74 runs) and 0.591 for recognition rate (rank 45 on 74). These results need to be studied further. For the image retrieval task, we focused on a way to generate subqueries, corresponding to potential clusters for the diversity process. We extracted the ten most cooccurring words with the query words, and used these words in conjunction with the initial query to generate sub-queries. One interesting result obtained comes from the fact that, for a text+image run, the result we obtained for the 25 last queries (the one for which we had to generate sub queries) was ranked 6th. This result encourages us to further study the behavior of our proposal.

Conclusion

To summarize our work on the Robotvision task, we have presented a novel approach for localization of a mobile robot using visual language modeling. Theoretically, this model fits within the standard language modeling approach which is well developed for IR. On the other hand, this model helps to capture in the same time the generality of the visual concepts associated with the regions from a single image or sequence of images. The validation process has proved a good recognition rate of our system against different illumination conditions. We believe that a good extension of this model is possible in the real scenario of scene recognition (more precisely for robot self-localization). With the addition of more visual features and the increase of system robustness, this could be a suitable approach for the future recognition systems. For the two other tasks in which we participated, we achieved average results. For the image retrieval we will study in the future more specifically the diversity algorithm.

Table 1 .

 1 The training set used is night3 set. The model Mc and Me correspond to the color histogram and the edge histograms generated from a 5×5 grid. The model Ms corresponds to the SIFT color feature extracted from interest points. The recognition rates according to several validation sets are presented in Table 1. Results obtained with 3 visual language models (Mc, Me, Ms)

	Train Validation HSV(Mc) Edge(Me) SIFT color(Ms)
	night3 night2	84.24% 59.45%	79.20%
	night3 cloudy2 39.33% 58.62%	60.60%
	night3 sunny2	29.04% 52.37%	54.78%

Table 2 .

 2 Result of the post-processing step based on 2 models Me and Ms

	Train Validation Fusion Regrouping	Filtering	Smoothing
	night3 sunny2	62% 67% (n=15) 72% (β=0.003) 92%(k=20)

Acknowledgment

This work was partly supported by: a) the French National Agency of Research (ANR-06-MDCA-002), b) the Quaero Programme, funded by OSEO, French State agency for innovation and c) the Région Rhones Alpes (projet LIMA).


Y Taher

A Aït-Bachir

M.-C Fauvet

D Benslimane
email: djamal.benslimane@liris.cnrs.fr

Diagnosing Incompatibilities in Web service Interactions for Automatic Generation of Adapters

Interactions between two applications encapsulated into

Web services consist in series of message exchanges that must conform to service interfaces. The study reported in this text aims at dealing with the issues that arise when interactions between two services (a client and a provider) fail because their interfaces are incompatible. This may happen because the provider has evolved and its interface has been modified. It may also happen because the client decided to change for another provider which addresses the same needs but offers a different interface. The contribution of the proposed approach 1 is twofold. First, given two services, all incompatibilities that may exist between their interfaces are automatically detected and classified into patterns. Second, according to the patterns that have been recognised, an adapter is then automatically generated. This latter is intended to act as an intermediate between the client and the provider, therefore seamlessly reconciling interactions between them.

Introduction

Web service interactions are composed of message exchanges that trigger specific reactions from the underlying Web services. Accordingly, it is usual to describe a Web service in terms of the message exchanges it engages in, and the actions it performs in response to incoming messages. Service interfaces can be described both from a structural viewpoint (i.e. types of exchanged messages) and from a behavioural viewpoint (i.e. the flow of message exchanges). Thus, the interface of a Web service is defined as the set of messages it can receive and send and the inter-dependencies between these messages.

As a Web service evolves, its interface is likely to undergo changes. These changes may lead to the situation where the interface provided by a service no longer matches the interfaces that its peers expect from it. This may result in stopping relationships between the service provider and her/his clients. To enable clients to keep accessing the service despite mismatches introduced by changes in its interface, the provider has to supply an adapter or a mediator. On the other hand, incompatibilities may happen because a service, seen as a client, decided to substitute another service it is used to access, with another one which addresses the same needs but offers a different interface. Actually, each time an evolution or a substitution occurs a new mediator has to be implemented. Developing such pieces of software is a costly and tedious task.

In this paper, we propose an approach whose contribution is twofold: First, given two services, all incompatibilities that may exist between their interfaces are automatically detected and classified into patterns. Second, according to the patterns that have been recognised, an adapter is then automatically generated. The proposed process of adaptation inputs two service specifications and produces the adapter intended to act as an intermediate between the client and the provider, therefore seamlessly reconciling interactions between them. The originality of our approach is that of it addresses detection of all incompatibilities between two interfaces as well as their resolution when related work generally focuses on adaptation only (See [START_REF] Dumas | Adapt or Perish: Algebra and visual notation for service interface adaptation[END_REF][START_REF] Motahari Nezhad | Semi-Automated Adaptation of Service Interactions[END_REF]). Moreover, we have designed a boolean language to represent types of incompatibilities that may exist between two service interfaces (represented as automata). The idea is that for each type of incompatibility, we will perform a synchronous traversal of the two automata to determine whether or not this type of incompatibility exists between them. This paper is organized as follow. Section 2 introduces the approach principles. Section 3 presents the approach formal model. Section 4 discusses the implementation and design details. Section 5 presents the related work, and finally we

Background

In this section, we present motivating a scenario, a formal representation of Web service interfaces, as well we introduce language and operators we use farther to model and resolve types of incompatibilities between Web service interfaces.

Motivation

As an illustrating scenario we consider a service (the seller) which is intended to offer goods for sale. The consumer service is meant to place orders against the seller who in turn, returns a quote, obtains the client's details, the shipment and invoicing addresses, and finally the client proceeds the on-line payment. Figure 1 illustrates the Web servicebased process interactions of this example.

The seller service starts by waiting for the client to place an order; to do so, the client has to send as many messages as items to be ordered. To end an order the client sends a specific message. The service is then able to calculate the quote. If the client agrees, it is now required to get the client's details, as well as the shipment and invoicing addresses. The conversation is completed when the payment has been proceeded.

The first part of Figure 1 shows compatible service interfaces of the client and seller services, so interactions can successfully complete between the involved services.

As illustrated by the second part of figure 1, client and seller service interfaces are no more compatible (because, for instance, of an evolution of the seller), so that interactions fail.

The study reported in the following of this paper, aims to automatically detect such incompatibilities between different versions of Web services, and generate the necessary adapters to reconcile these incompatibilities.

Labelled Transition Systems

Since in our approach we need to reason on Web service interfaces to automatically capturing incompatibilities between them, it is tremendously recommended to model interfaces in a formal representation. That makes it easier to compare interfaces and to capture the existent incompatibilities. For this purpose we chose to model the interface of a Web service using automata (Labelled Transition Systems (LTS [START_REF] Haddad | Modelling Web Services Interoperability[END_REF])). LTSs are a fundamental modeling formalism in many areas of computer science where one needs to compare two or more such systems in applications. One of the main reasons for this is that LTSs are a well-known paradigm coming up with solid mathematical foundations that can be used to support rigorous analysis and verification. LTS consists of a finite set of states and transitions from state to state. In our context, states represent different phases a service may go through during its interaction with clients. Each interaction is considered as a state transition. Transitions are labeled with interaction messages. When a message is sent or received, the corresponding transition is fired. As an example, Figure 2 depicts the LTS modeling the previous interface version of the of the Seller Service from the illustrating scenario presented by Figure 1. As expected, the LTS captures the sequence of message interactions the service performs in this scenario. It specifies that the Seller Service is initially in the start state s 0 , and that a client begins using the service by sending one or more (One Order Item) messages, and the service remains in the same state. Once a message (Stop Mark) has been received, the service moves into the state s 1 , and so on. Indeed, the LTS depicts the fact that the Seller Service is capable of performing the sequence of message interactions : (< c :One Order Item) * , (< c :Stop Mark), (> c :Quote), (< c :Shipment&Invoice Addresses), (< c :Payment Info) . However, the service cannot perform sequences with prefix (< c :Order Item List) because the start state s0, does not have any outgoing transitions labelled (< c :Order Item List).

Expression language

In this subsection, we introduce a language including some important concepts and definitions that are used during the incompatibility detection and resolution process. Our language phrases model type of types of incompatibilities that may exist between two service interface LTSs. The idea is that for each type of incompatibilities, an algorithm that performs a synchronous traversal of the two LTSs is run to determine whether or not this incompatibility type exists between them. We made the assumption that each incompatibility could be captured by exactly one phrase of this language. Further study is already scheduled to assess the validity of this assumption in any situation. In this section, we first introduce this language, then we show how to apply it on the illustrating example given Section 3.1 and eventually we detailed the proposed algorithm.

To build expressions which model incompatibilities, that may exist between two LTSs, we adopt the following notations [START_REF] Djikman | Service-Oriented Design: A Multi-Viewpoint Approach[END_REF] (examples refer to the LTS depicted in Figure 2):

• s• is the set of outgoing transitions from s.

(e.g. S2• = { <c:Shipment&Invoice Addresses}).

• •s is the set of the incoming transitions for the state s.

(e.g. •S4 = {<c:Payment Info}).

• t• is the target state of the transition t.

(e.g. (<c:Shipment&Invoice Addresses)• = S3).

• •t is the source state of the transition t.

(e.g. •(<c:Shipment&Invoice Addresses) = S2).

The • operator (respectively •) is generalized to a set of transitions (respectively states). For example, if T is a set of transitions such as: T = n i=1 {ti} then T • = n i=1 {ti•}. Our language supports boolean operators (∧, ∨, =, etc.) and set operators such as:

• s• : set cardinality of outgoing transitions of s.

• s • -s ′ •: set difference between outgoing transitions of s and outgoing transitions of s ′ .

The language also supports filters which build sets of transitions or states satisfying one given property. For instance:

• The operator Polarity(t), applied to a transition t, returns a string denoting whatever the interaction message associated to the transition is to be sent (>c:) or received (<c:). (e.g Polarity(> c:Quote) = {>c:}; that means that the message associated to the transition (> c:Quote) is to be send. Polarity(<c:Payment Info) = {<c:}; that means that the message associated to the transition (<c:Payment Info) is to be received.

• The operator Message(t) returns the message (operation argument) to be sent or to be received during a transition t. (e.g Message(> c:Quote) = {Quote}).

• The operator Type(m), applied to a message m, returns its type structure.

(e.g Type(Quote) = {T1}, where: T ype T1 Amount : F loat Currency : String ).

• The Seq(s) operator, applied to a state s, returns a set of transition sequences. Each transition sequence is built starting from one transition ti ∈ s•. (e.g Seq(S2) = {T}, where: T = { <c:Shipment&Invoice Addresses, <c:Payment Info}).

To check whether or not changes will implie incompatibilities, it is necessary to identify situations when the version P ′ does not simulate its previous one P . If P ′ simulates P (denoted P P ′ ) then each interface R required by a client, which is compatible with P (denoted R ∼ P ) remains compatible with P ′ as shown below. We denote by R the opposite interface of R obtained by transforming each message being sent to a message being received and conversely. Given R ∼ P , thus R P [START_REF] Bordeaux | When are Two Web Services Compatible? In proc. of TES[END_REF]. Due to the transitivity property of the preorder relation of simulation, we have R P ′ (because R P and P P ′ ). Hence, R conforms to P ′ (R ∼ P ′ ). Thus, the detection and the resolution of incompatibilities are relevant only if P ′ does not simulate P . Section 3.2 below illustrates the language by introducing expressions to detect incompatibility patterns.

Incompatibility detection and resolution

In this section, we present our adaptation methodology which inputs two interface automata, detects types of incompatibilities between them, and finally builds (if possible) an automaton adapter.

In what follows, we model types of incompatibilities by formal expressions, so that incompatibilities could be automatically detected when comparing two automata modeling different versions of a service interface. To well illustrate the idea, we begin with an illustrating example in Section 3.1, afterward we introduce the principals of the approach in Section 3.2.

Illustration

Let P be the LTS modeling the interface of a provider service, a client service whose interface is modeled by the LTS P obtained from P by overturning the polarity of the interaction messages (i.e., received messages (< c :) becomes sent messages (> c :) and vice versa) can successfully interact with the provider service. In the sequel of this paper, we denote by P ′ the version of the interface resulting from the last modification while P denotes the previous version of that service interface.

Upon such a modification, the client service whose interface is modeled by R (where R = P) is no more compatible with P ′ . To deal with such a situation, we need first to detect incompatibilities between P and P ′ , and then generate an adapter for reconciling at runtime interactions between the Client and Seller services.

As a first step of the incompatibility detection and resolution process, Figure 3 captures some types of incompatibilities detected between P and P ′ . Namely a One * -to-One incompatibility type is detected at states s0 and s ′ 0 of P and P ′ respectively. Likely, a One-to-One incompatibility type is detected at states s1 and s ′ 1 , and so on. A more detailed discussion about each type of these incompatibilities is given in Section 3.2.

In the first step of the detection and resolution process we have focused on comparing the LTSs of the previous and current interface versions of the involved service. Now the objective is to build the LTS modeling the interface of the service adapter. We model an adapter as a service which sets between between two services to be adapted and imitates the required interfaces of both services from each other. That means that the adapter supports the LTS P ′ in its interactions with P ′ and the LTS R in its interactions with R. For this purpose, we have designed a set of resolution operators each of them is dedicated to handle a specific type of incompatibilities. Such operators, consume message in terms of the requester service interface and produce messages in terms of the provider service interface and vice versa. Figure 4 depicts the sequences of interactions to be performed by the intended adapter. Such a LTS is obtained by composing and wrapping into a map the resolution operators corresponding to types of incompatibilities detected between P and P ′ . Namely, the Aggregation resolution operator to reconcile the detected One * -to-One incompatibility. The Matchmake to deal with the detected One-to-One incompatibility, and so on. Section 3.2 details and specifies one by one each of these resolution operators.

Formalizing incompatibility detection and resolution patterns

To detect incompatibilities, P and P ′ are browsed synchronously from their respective initial states s0 and s ′ 0 . The search seeks out two states s and s ′ (belonging respectively to P and P ′ ) which are such as the sub-automaton starting from s in P and the one starting from s ′ in P ′ are incompatible. The test consists in applying a set of expressions, each of which capturing a specific type of incompatibility.

To each incompatibility type we associate a formal expression and a resolution operator. The formal expression models the incompatibility in terms of states and transitions, so that incompatibilities are likely to be detected when comparing P and P ′ automata. However, the resolution operator aims to reconcile the detected incompatibility at execution time. The purpose of this subsection is to sketch this detection and resolution process.

Pattern 1. One * -to-One Incompatibility:

• Description: Such a kind of incompatibility arises when an operation loop at a given service interface is replaced by only one operation at a new version. Figure 3 refers to a One * -to-One incompatibility detected between P and P ′ at states s0 and s ′ 0 . While the previous version was designed in a way an order of n items is realised by consuming n (<c:One Order Item) messages, the new version expects an order to be realised by consuming only one (<c:Order Item List) message.

• Detection: During comparing P and P ′ , a One * -to-One incompatibility is detected if and only if the following expression is evaluated to true:

∃{ti, tj} ⊆ s • ∧∃t ′ ∈ s ′ • | ti• = s ∧ tj• = s ∧ T ype(List(M essage(ti))) = T ype(M essage(t ′ )) P olarity(t ′ ) = {< c :} ∧ P olarity(ti) = {< c :} ∧ P olarity(tj) = {< c :}
This expression seeks out two sates s and s ′ from P and P ′ respectively, where the target state of one of the outgoing transitions of s is s in itself (ti• = s). Therefore, the test follows through comparing whether the type of the message structure obtained by creating a list of messages associated to ti transition is equivalent to the type of the message associated to t ′ transition. Finally, the test turns up by verifying that polarity of all messages associated to the of involved transitions is to be received.

• Resolution: To deal with One * -to-One incompatibility pattern, we have introduced the Aggregation resolution operator. This operator is intended to keep consuming and storing messages coming in terms of the previous service interface until receiving a stop mark message indicating that all messages belonging together have been already sent. At this point, the operator is enabled to aggregate stored messages into a single message list represented in terms of the current service interface. Figure 4, illustrates the use of Aggregation operator between R and P ′ . It starts in a consuming state (s0, s ′ 0 ), in which it is hanging about consuming and storing (<c:One Order Item) messages. It is remaining always in the same state unless it receives (<c:Stop Mark) message which allows it to move into the next state (s1, s ′ 0 ). At this state, the operator aggregates the set of individual messages into one message containing the order item list, produces the result message to the Seller Service and finally ends up into state (s1, s ′ 1 ).

Pattern 2. One-to-One Incompatibility:

• Description: When the structure of messages meant to be sent or received in an operation changes, a One-to-One incompatibility pattern arises between previous and current versions of that service interface. Referring to our illustrating example, Figure 3 captures One-to-One incompatibility between P and P ′ at states s1 and s ′ 1 . While the Quote message structure (T1) consists in two fields, called amount and currency, in the new interface version, such a message structure (T2) consists in only one field to store both the amount and the currency of the quote.

• Detection: a One-to-One incompatibility is detected between P and P ′ if and only if the following expression is satisfied:

∃t ∈ s • ∧∃t ′ ∈ s ′ • | t = t ′ ∧ T ype(M essage(t)) = T ype(M essage(t ′ )) ∧ P olarity(t) = P olarity(t ′ )
This expression seeks out two states s and s ′ , from P and P ′ respectively, whose outgoing transitions t and t ′ are labeled with the same message (t = t ′ ) but the message structure is changed (T ype(M essage(t)) = T ype(M essage(t ′ ))).

• Resolution: To deal with such a kind of incompatibility pattern, we have introduced the Matchmake resolution operator. Its main task consists in consuming a message of type T1 and producing a message of type T2. The message type transformation from T1 to T2 is subject to a structural transformation function F M atch , provided as a parameter by the adapter designer. Once a message m1 of type T1 is consumed by the operator, the function F M atch will be applied to in order to produce a message m2 of type T2. While a One-to-One incompatibility is detected between P and P ′ at the states s1 and s ′ 1 (Figure 3), we use the Matchmake operator to reconcile such a kind of incompatibility between R and P ′ . In Figure 4, the Matchmake operator starts in a message consuming state (s1, s ′ 1 ). Once a message Quote of a structure type T1 has been consumed (<c:Quote), the operator enters ). At this state, it is being able to apply the structural transformation function to the received message and produce a message Quote of structure type T2 (>c:Quote). Afterward, the operator enters into its final state (s2, s ′ 2 ).

Pattern 3. One-to-Many Incompatibility:

• Description: This kind of incompatibility arises when a given operation at a given service interface is changed into a sequence of operations at a new version of that interface. In this change pattern, the message parameter structure of each of the sequence operations is a sub-structure of the message parameter of the mentioned operation at the previous version. Figure 3 illustrates an example of this incompatibility pattern between state s2 from P and states s ′ 2 and s ′ 3 from P ′ . As captured by the figure, the operation (<c:shipment&Invoice Addresses) is changed into is changed into a sequence of two operations (<c:Shipment Address) and (<c:Invoice Address) at the current version of that service interface. • Detection: When comparing P and P ′ , a One-to-Many incompatibility is detected if and only if the following expression is satisfied:

∃t ∈ s • ∧∃e ∈ Seq(s ′ ) | T ype( e i=1 M essage(ei)) = T ype(M essage(t)) ∧P olarity(t) = {<: c} ∧ (∀ei ∈ e | i ∈ [1, e ], P olarity(ei) = {<: c})
The idea is to look for an operation sequence at the current version (e ∈ Seq(s ′ )) such as the union of all message structures of this sequence is the same as one of the previous operation message (T ype( e i=1 M essage(ei)) = T ype(M essage(t))). • Resolution: To handle such a type of incompatibility pattern, we have introduced the Split resolution operator. Such an consists in providing One-to-Many structural message transformations. Once a message m of type structure T has been consumed, a set of predefined functions F Split 1 , ..., F Split n , provided as parameters, are applied to m in order to extract and produce n sub-messages m1, ..., mn of type structures T1, ..., Tn respectively. These sub-messages are considered as input message parameters of the involved sequence operations at the current service interface. Figure 4 illustrates the principal of this solution. In this example, the Split operator starts at state (s2, s ′ 2 ) by waiting for a message from the R. Once, such a message has been received (<c:Shipment&Invoice Addresses), the operator stores it and move into the next state (s3, s ′ 2 ). At this state, F Split 1 will be applied to the stored message in order to extract the shipment address, trigger the corresponding operation (>c:Shipment Address) at the Seller Service interface, and enters then into state (s3, s ′ 3 ). Likely, at this state F Split 2 will be applied to the stored message in order to extract the Invoice Address, trigger the corresponding operation (>c:Invoice Address) at the Seller Service and then ends up into state (s3, s ′ 4 ).

Pattern 4. One-to-?(One) Incompatibility:

• Description: In this change pattern, one operation at a given service interface is changed into two or more operation branches at a new version of that service interface. While at the previous version, the mentioned operation is used to deal with different kind of cases such as achieving payment (<c:Payment Info) either by Credit Card or check (Figure 3), the new interface version provides multiple operations each of them is intended to deal with a specific kind of payments. We distinguish between an operation to process credit card payments (<c: CC Payment) and another to process check payments (<c:Check Payment).

• Detection: When comparing P and P ′ , a One-to-?(One) incompatibility is detected if and only if the following expression is satisfied:

∃t ∈ s • ∧∃e ⊆ s ′ • ∧ e 2 | ∀t ′ ∈ e : t ′ = t ∧ T ype(M essage(t ′ )) = T ype(M essage(t))
∧P olarity(t) = {< c :} ∧ P olarity(ei) = {< c :} This expression looks for a set of two or more operation branches (∃e

⊆ s ′ • ∧ e 2)
, where each branch operation (in the new version) is different from the previous operation (∀t ′ ∈ e : t ′ = t). However, the message structure of each branch operation matches the message structure of the previous operation (T ype(t ′ ) = T ype(t)).

• Resolution: To deal with such a type of incompatibility pattern, we have introduced the Switch resolution operator. This operator is used to map a message issued from a requester service to the right operation at the provider service interface. The behavior of the Switch operator is depicted in Figure 4. It starts in the consuming state (s3, s ′ 4 ), and keeps waiting for receiving the payment message (<c:Payment Info) issued from R. When this happens, the operator moves into the next state (s4, s ′ 4 ). At this state, one of the outgoing transition branches (>c:Check Payment or >c:CC payment) should be fired, and then enters into the final state (s4, s ′ 5 ). Firing one of these transitions depends on the outcome of guard conditions associated to each of those transitions. If the guard associated to the check payment transition is evaluated to true, this transition will be fired and the check payment operation is then triggered at P ′ . Otherwise, the the other transition will be fired and the credit card operation will be triggered at P ′ . Indeed, such guard conditions are evaluated by observing dynamically the message content in order to verify what kind of payments it is.

Pattern 5. Many-to-One Incompatibility:

• Description: In this change pattern, a sequence of operations at a given service interface are modified into one single operation whose message structure can be computed from the structure union of the messages related to the mentioned sequence of operations. This pattern principal can be considered as the reverse of the One-to-Many pattern principal.

• Detection: When comparing P and P ′ , a Many-to-One incompatibility is detected if and only if the following expression is validated to true:

∃e ∈ Seq(s) ∧ ∃t ∈ s ′ • | T ype( e i=1 M essage(ei)) = T ype(M essage(t)) ∧P olarity(ei) = {> c :} ∧ P olarity(t) = {> c :}
The expression looks for a sequence of operations at the previous version (e ∈ Seq(s)) such as the union of all message structures of these sequence of operations is the same as one of the new operation message (T ype( e i=1 M essage(ei)) = T ype(M essage(t ′ ))). • Resolution: To deal with such a kind of incompatibility pattern, we have introduced the Merge resolution operator. This kind of solution consists in providing Many-to-One structural message transformation. The resolution task consists in consuming n messages of different type T1, ..., Tn and produce one message of type T. The n-messages merging process is performed by a structural transformation function FMerge, which is provided as parameter by the adapter designer. Pattern 6. One-to-One * Incompatibility:

• Description: Such a kind of incompatibility arises when an operation at a given service interface is changed into an operation loop at a new version of that interface. This pattern principal can be considered as the reverse of the One * -to-Many pattern principal.

• Detection: a One-to-One * incompatibility is detected between P and P ′ if and only in the following expression is satisfied:

∃t ∈ s • ∧∃{t ′ i , t ′ j } ∈ s ′ • | t• = s ∧ t ′ i • = s ′ ∧ t ′ j • = S∧ T ype(M essage(t)) = T ype(List(M essage(t ′ ))) ∧P olarity(t) = {> c :} ∧ P olarity(ti ′ ) = {> c :}
This expression seeks out two sates s and s ′ from P and P ′ respectively, where the target state of one of the outgoing transitions of s ′ is s ′ in itself (t ′ i • = s). Moreover, the test follows through comparing whether the type of the message structure obtained by creating a list of messages associated to t ′ i transition is equivalent to the type of the message associated to t transition. Finally, the test ends up by verifying that polarity of all messages associated to the of involved transitions is to be sent.

• Description: To handle such a kind of incompatibility pattern, we have introduced the Iteration resolution operator. The main task of this operator consists in receiving a message of multiple elements coming in the same type and structure, and breaking it into a number of sub messages as much as the message element number. Afterward, the obtained set of messages are used then to trigger repeatedly the corresponding operation at the requester service interface.

Implementation and design details

As part of our contribution, we provide developers with a framework for performing the automatic incompatibility detection and resolution. The detecttion is processed by a module namely BESE-RIAL2 [START_REF] Ait-Bachir | BESERIAL: Behavioural Service Analyser[END_REF] and the resolution runs upon a CEP3 infrastructure [START_REF] Taher | Using CEP Technology to Adapt Messages Exchanged by Web Services[END_REF].

In what follows, we present the design and implementation details of our tool.

Algorithm of incompatibility detection

The algorithm implementing the detection phase is detailed in Figure 5. Given P ′ the new version of the service's interface and P the previous one, the principle of the algorithm is to browse synchronously both LTSs describing P ′ and P . It proceeds so, starting from s0 and s ′ 0 the initial states of P and P ′ LTSs respectively. The initial call of the algorithm is realized by the expression Detection(s0, P, s ′ 0, P ′ ). The algorithm aims at finding all pairs of states s and s ′ which satisfies one of the incompatibility expressions. It returns a set of triplets < t, s, s ′ > where t is the incompatibility pattern that has been captured between the sub-automaton of P starting in s and the one of P ′ starting in s ′ .

All expressions formalizing incompatibility patterns are first loaded from a database (see line 12). Then, each of which is evaluated considering the current values of the algorithm input data (socalled current configuration).

Figure 5. Algorithm of incompatibility detection

Lines 17 to 19 are dedicated to build the input data to be considered by the recursive call. A function named endLT S(P : LT S, S: State): LT S is introduced. Given an LTS P and one of its state S, endLT S(P, S) is the fragment (an LTS) of P starting from the state S.

For each detected incompatibility, the pair of LTSs to consider is built before the next recursive call (see lines 20, 20 and 21).

Finally, if no incompatibility is detected, the input data to be considered by the recursive call are target states of the equivalent outgoing transitions, in both LTSs, starting from si and sj (i.e. si • ∩sj•) (see lines 23, 24 and 25). Starting with the incompatibility detection phase, the Detection module hosting and implementing the aforemen- The Adapter Generator module operates upon results exported from the Detection module. For each incompatibility element detected between states from the previous and current versions, the Adapter Generator identifies the corresponding template resolution operator from the Resolution Operators Database. Eventually, the identified operators are then composed together and wrapped into a map. Since this map is a high level of abstraction describing how to adjust and adapt the interactions between the the interacting Web services, it is necessary to translate the template operators based map into an execution-time module and load it to the runtime environment when it comes to deploy the adapter. For this purpose, we have chosen to rely on the insight of CEP technology to implement our adaptation model.

Framework architecture

CEP is a new event driven architecture paradigm that allows of simple events to be aggregated into complex ones. More specifically, CEP is a platform for building and running event-based applications that could that could continuously process event streams to detected a specified confluence of events, and trigger a specific action when the events occur. Most of existing CEP platforms provide a continuous computation language [START_REF] Babu | Continuous queries over data streams[END_REF] for specifying queries each of which defining the schema of an event stream to be monitored, defining event patterns to be detected, specifying processing functions and sequencing, and finally declaring output to be generated.

As our adaptation operators consist in consuming incoming messages, processing them, and finally producing adapted messages, we have modeled exchange messages as events, and encoded the message adaptation logic, performed by an operator, in terms of Continuous Computation Queries (CCQ). This allows a CEP infrastructure, combining a CEP Engine and SOAP integration layers, to acts as a Web service adapter. While the CEP Engine provides the core service of receiving, correlating, and processing messages against loaded CCQ, we have designed a SOAP integration layer model which is mainly intended to assure SOAP interactions between the CEP Engine and the involved services. That allows a CEP Engine to integrate to Service Oriented Architecture. Actually, a SOAP integration layer consists of Input and Output Wrappers. Since the CCQ subscribe to input streams to consume messages, and publish produced messages into output streams, an Input Wrapper is used to consume a SOAP message issued from the sender service, wrap it into a representation appropriate to the CEP Engine, and eventually transmit it to the right Input Stream. Likely, we associate an Output Wrapper to each Output Stream. When a request publish a message to a given output stream, the output wrapper gets such a message and bind it to specific SOAP plugin which is intended to trigger the corresponding operation at the current service interface.

Related work

The issues tackled in this paper have been partially addressed before, with various points of view. Web service interactions may fail because of interface incompatibilities according to their structural dimension. In this context, reconciling incompatible interactions leads toward transforming message types (using for instance Xpath, XQuery, XSLT). Issues that arise in this context are similar to those widely studied in the data integration area. A mediation-based approach is proposed in [START_REF] Altenhofen | An Execution Semantics for Mediation Patterns[END_REF]. While this approach relies, as ours, on a mediator (called virtual supplier) it focuses on structural dimension of interfaces only. An other drawback of this approach is that incompatibilities raised after changes and evolutions of interfaces could not be automatically resolved.

Compatibility test of interfaces has been widely studied in the context of Web service composition. Most of approaches which focus on the behavioral dimension of interfaces rely on equivalence and similarity calculus to check, at design time, whether or not interfaces described for instance by automata are compatible (see for example [START_REF] Foster | Model-based Verification of Web Service Compositions[END_REF][START_REF] Bordeaux | When are Two Web Services Compatible? In proc. of TES[END_REF][START_REF] Haddad | Modelling Web Services Interoperability[END_REF]). The behavioral interface describes the structured activities of a business process. Checking interface compatibility is thus based on bi-similarity algorithms [START_REF] Djikman | Service-Oriented Design: A Multi-Viewpoint Approach[END_REF][START_REF] Martens | Analyzing Compatibility of BPEL Processes[END_REF]. These approaches do not deal with reconciliation issues when incompatibilities occur.

To keep compatibility in a service composition, managing versions is one of the investigated paths in research field. Evolutions and changes are managed by the definition of new versions. In [START_REF] Kaminski | A design technique for evolving web services[END_REF], authors propose adapters to reconcile clients, which are compatible with both previous and new versions of the service interface. Nevertheless this proposal focuses on the structural aspects of services only.

Change patterns have been introduced in [START_REF] Weber | Change Patterns and Change Support Features in Process-Aware Information Systems[END_REF]. These patterns characterize different types of business process evolution. Each pattern models a set of rules which are used by the designer to decide whether or not to propagate changes on executing instances of the modified process or to abort them. As Web services are used as black boxes, this approach does not apply to our context.

Conclusion

We presented an approach to automatically detect and resolve incompatibilities that arise in Web services interactions. We studied and formalized incompatibilities that occurs when a provided interface of a Web service evolves and clients and partners can no longer correctly interact with it. Our framework relies on a language to build and to evaluate expressions each of which models an incompatibility pattern (see Section 3.2). These expressions are evaluated in the detection process and the result guides the resolution process. For each incompatibility pattern we associate one adapter pattern. Then we combine these adapter patterns to build one global adapter which is then translated in terms of continuous computation queries and deployed in a CEP engine. The adapter proceeds seamlessly and intercept messages between Web service and its environment and make the change completely transparent. The work presented in this paper opened several research directions. First of all, incompatibility patterns which are not presented in this paper will be investigated and formalized with our language. Some adapter patterns are semi-automatically generated as it require function definitions to model the semantic of the adapter behavior. This step could be performed by adding ontology definitions.

Figure 1 .

 1 Figure 1. Web service Interactions

Figure 2 .

 2 Figure 2. Formalising interfaces with LTSs

Figure 3 .

 3 Figure 3. Detection of incompatibility types

Figure 4 .

 4 Figure 4. Resolution of detected incompatibilities

Figure 6

 6 Figure 6 depicts our framework architecture, which consists of design and run-time environments. The design-time environment combines incompatibility detection and adapter generation tools. The runtime environment relies on a Complex Event Processing (CEP) infrastructure for messages processing and manipulating.Starting with the incompatibility detection phase, the Detection module hosting and implementing the aforemen-

1

  Detection (si: State; Pi: LTS; sj: State; Pj: LTS ): {Res} 2 { Detection(si,Pi,sj,Pj) is a set of tuples < t, s, s ′ > where t is the incompatibility type between P i and P j automata (whose initial states are respectively si and sj) located at s (one P i state) and s ′ (one P j state). } 3 setRes: {Res} { result variable }

	4 P1,P2: LTS ; s1,s2: State ; setRes1: {Res}
	5	{ intermediary variables }
	6 setProg : {coupleStates}
	7	{ pairs of states to consider next in the progression
		process }
	8 IE: {IncompExp} { set of incompatibility types }
	9 tEx: IncompExp
	10 setRes ← ∅
	11 setProg ← ∅
	12 IE ← LoadIE() { Loads from a database of expres-
		sions. }
	13 If si• = ∅ then	{ condition for no recursive call }
	14	For all tEx ∈ IE
	15	setRes1 ← Evaluate(tEx,si,Pi,sj,Pj)
	16	setRes ← setRes ∪ setRes1
	17	If setRes1 = ∅ then
	18	{ Incompatibilities exist.	Which sub-
		automata to consider. }
	19	setProg ← setProg ∪ Progression(tEx,si,Pi,sj,Pj)
	20	For all c ∈ setProg { Progress to next configura-
			tions }
	21	P1 ← endLTS(Pi,c.s1) ; P2 ← endLTS(Pj,c.s2)
	22	setRes ← setRes ∪ Detection(c.s1,P1,c.s2,P2)
	23	For all t ∈ si• ∩ sj• { No incompatibility detected }
	24	P1 ← endLTS(Pi,t•) ; P2 ← endLTS(Pj,t•)
	25	setRes ← setRes ∪ Detection(t•,P1, t•, P2)
	26 Return(setRes)

  Compiler by browsing synchronously the previous and current interface versions of the involved service. For each pairs of states at these interface versions, incompatibility expressions stored in the Incompatibility Expressions Database, are evaluated. This process ends up by detecting the set of incompatibilities occurring between the previous and current interface versions of that service.

	Service (A)	SOAP Integration Layer	CEP Engine	SOAP Integration Layer	Service (B)
		Input
		Wrapper			Output
	SOAP	Input			Wrapper	SOAP
	HTTP	Wrapper				HTTP
		Output			Input
		Wrapper			Wrapper
			Deploy
			CCQ Code Generation Tool
			Operator-based Map
					Resolution
			Adapter Generator	Operators
			Incompatibilities
		Service Interface			Incompatibility
		Automata	Detection		Expressions
			Compiler
		: Input stream ;	: Output stream ;	: Continuous Computation Queries (CCQ)
		Figure 6. Mediation framework
	tioned incompatibility detection algorithm, starts in conjunction
	with the

This work is partially funded by the project Web Intelligence granted by the French Rhône-Alpes Region. Part of it was done when Y.Taher was visiting the BPM Group at QUT, Brisbane under the supervision of Marlon Dumas.

http://www-clips.imag.fr/mrim/User/ali.aitbachir/webServices/webServices.html

3 http://www.complexevents.com/