Most current approaches to matchmaking of semantic Web services utilize hybrid strategies consisting of logic- and non-logic-based similarity measures (or even no logic-based similarity at all). This is mainly due to pure logic-based matchers achieving a good precision, but very low recall values. We present a purely logic-based matcher implementation based on approximate subsumption and extend this approach to take additional information about the taxonomy of the background ontology into account. Our aim is to provide a purely logic-based matchmaker implementation, which also achieves reasonable recall levels without large impact on precision.
Web service discovery and matchmaking is a eld of ongoing research. For semantic web services, logic-based reasoning o ers the possibility of high precision. However, in general it achieves only poor recall levels. Due to this, most current matcher implementations utilize a combination of logic- and non-logic-based, or even only non-logic-based similarity measures.
The best performing matcher during 2009's Semantic Service Selection
contest3 S3, URBE [
LOG4SWS.KOM [
iSeM [
Another service matcher which directly takes the structure of the
taxonomy into account when computing matches is F-Match [
Our matcher is based on the notion of approximate subsumption as proposed
in [
This paper is structured as follows: In section 2 we de ne approximate subsumption and give an example of its usage. The concept of approximate subsumption as we applied it to semantic web services and our implementation is described in section 3. We evaluate our implementation in section 4 and conclude in section 5. 2
In this section we brie y describe approximate subsumption. In [
S
It is shown that this approach has the property of generalized monotonicity, making it possible to generate weaker version of the subsumption operator with every approximation step by decreasing the size of S. This allows to rank a result list based on the degree the operator had to be weakened to receive a speci c result. Possible strategies for altering S include contraction by removing concepts sequentially or permutation by creating every possible combination of concepts in S.
A great advantage of this approach is, that it can be implemented by
syntactic modi cations of concept expressions and then be evaluated by standard
description logic reasoners [
The de nition of the upper approximation (:)+ is analogous, only equations 1 and 2 are adapted:
Applying these rewriting rules to the approximate subsumption operator we get the following alternative de nition: So to check for approximate subsumption we have to create the lower approximation of a service o er and the upper approximation of the service request and test whether the intersection is equal to the empty set.
In our implementation we call this original de nition of approximate subsumption Simple strategy. The following gives an example of how this strategy (1) (2) (3) (4) (5) (6) (7) is carried out5: Lets consider a search application for pizza delivery services. The user may specify di erent toppings he likes to have on his pizza, and the search then returns a number of delivery services o ering pizzas with these ingredients. For example a user wants a vegetarian pizza with Broccoli and Artichoke. Unfortunately no delivery can satisfy this wish. Subsequently, the system approximates the request by creating two new request with Broccoli and Artichoke replaced with > respectively. Executing these two new requests, the system discovers pizza delivery services which o er Broccoli and Mandarine pizzas or Artichoke and Mushroom pizzas, which both might be relevant to the user. The next approximation step would approximate both Broccoli and Artichoke to > and subsequently return every pizza with two vegetarian toppings. 3
Applying Approximate Matching to Semantic Web Services This chapter explains in more detail how we applied approximate subsumption to semantic web services and how we implemented partial matchmaking for service discovery and which extensions we made.
The implementation consists of two parts: The rst part de nes the web service ontology, processes the service o ers and creates requests represented as concepts of the ontology. The second part, a generalized matchmaker, reasons on this ontology and computes matches to the request based on its subsumption relation to service o ers.
The typical usage of our matchmaker is divided into an o ine initialization and classi cation of service o ers, and the online processing of requests. During the initialization semantic annotations are extracted from SAWSDL services and added to a service ontology. This ontology is then classi ed with the help of a description logic reasoner. After the initialization any number of request can be issued to the matchmaker without further reclassi cation. 3.1
In order to build an ontology of all known web services the semantic annotations have to be extracted from the web service descriptions. A simpli ed version of a web service with SAWSDL annotation is shown in Fig. 1.
The concepts, which are extracted from the web service annotations, are
added to a service ontology. This is a minimal ontology for describing a service,
modelled in OWL [
(hasOperation some opSearchByTopping) opSearchByTopping SubclassOf (hasInput only Topping) and (hasOutput only Address) and (hasInput some Topping or hasOutput some Address) While loading a service, the approximator also counts the occurrences of each concept used to annotate its parameters, which is important when determining the order in which they should be approximated (cf. approximation strategies). Furthermore, it maintains a list of cumulated occurrences, which are the sum of a concept's and all of its sub concepts' occurrences throughout the whole service ontology. This number is a better indicator for how restricting a speci c constraint of the request is than the number of occurrences of a concept alone. For example, OWLThing (the super concept of all concepts) and OWLNothing (the sub concept of all concepts) will most likely never be used to annotate a Web Service, so they both have a number of occurrence of 0. However, the cumulated occurrence of OWLThing is the sum of all other concepts' occurrences, whereas the cumulated occurrence of OWLNothing is still 0. This means if a service parameter is enforced to be of type OWLNothing, this is much more restricting, than enforcing it to be of type OWLThing6. 6 Actually, a constraint for a parameter to be of type OWLNothing is unsatis able and a constraint for a parameter to be of type OWLThing is always ful lled
Query Creation A request is represented in the same way as a normal service o er (cf. section 3.1). There are two possibilities of creating a new request: { A Query-by-Example approach, by which an existing annotated service is used to create a request from it. This can be useful, if someone wants to nd a replacement for an existing service, or services with duplicate abilities should be found. { Input and Output parameters are speci ed directly and a request is built using these, for example when a user searches a service to ful ll a speci c task.
Query Approximation The Web Service Approximator creates queries using
permutations to change the S set. Two strategies de ne the approximation of
concept expressions: The rst strategy determines the order in which concepts
are approximated, depending on their cumulated number of occurrences. This
strategy supports three di erent variants, in uencing the ranking of the results
(cf. [
The second strategy de nes how ne grained the approximation should be.
The Simple variant approximates each concept of the request by replacing it
with OWLThing, which is the approach in [
(A) (:A) ! directsub(A) if A 2 S ! directsub(A) if A 2 S (A)+ ! directsuper(A) if A 2 S (:A)+ ! directsuper(A) if A 2 S (8) (9) (10)
The intention behind the Taxonomy strategy is to create a much more detailed ranking of results and therefore achieve a higher precision than with the Simple variant. This approach bene ts especially if ontologies with a deep taxonomy are used for annotations and if concepts from every level of the taxonomy are used.
Revisiting the example of the pizza delivery service search, the rst approximations according to the Taxonomy strategy are the following: instead of replacing Broccoli and Artichoke with >, we use their direct superconcept, which in this case is Vegetable for both. The search for pizzas with Broccoli and any other Vegetable or pizzas with Artichoke and any other Vegetable now only nds the delivery service o ering Artichoke and Mushroom pizzas. The service delivering Broccoli and Mandarine pizzas is not found during the rst approximation step, as Mandarines are a Fruit and no Vegetable. This pizza is found during the second step, when Vegetable is further approximated to VegetarianFood, of which Fruits are naturally are subconcept. Thus, the Broccoli and Mandarine pizza would be considered less relevant, as the request had to be further weakened to retrieve it.
Note that the approximator always generates all possible approximations of a request at once, avoiding duplicates by checking the parameters of each request. So for each super- or subconcept of a concept, respectively, a new request is generated. If the concept does not have a direct super- or subconcept, respectively, then no approximation is created. This is only the case for OWLThing and OWLNothing, as every other concept has OWLThing as superconcept and OWLNothing as subconcept.
Additionally, the approximator tries to avoid term collapsing [
During the creation of approximations, we generate a graph which captures the relations between the original request and its approximations. The root node of the graph is the original request, its direct children are the approximations created during the rst step, their children are the approximations generate from them during the second step, and so on. This graph is later used to optimize the execution time of the matchmaker, especially when approximating along the taxonomy, which produces a large amount of queries: Q 2 O(N P ), with Q being the number of created queries, P the number of parameters the request has and N the maximum number of superclasses a concept has. So the number of queries, and consequentially the execution time of the matcher, grows exponentially with the number of parameters. However, web service have mostly only a couple of parameters, so we hope to still calculate results in a reasonable amount of time.
The object representing an approximated query also stores the step in which it was approximated and the sum of the cardinalities of all concepts which were approximated to create this query. These two numbers are important to determine the position of each query's results in the nal aggregated result list, as the partial matchmaker may process queries out of approximation order, and thus their results can not simply be appended to the list.
Query-only Approximation A drawback of the de nition of approximate
subsumption in [
+ 8I : I j= C v D , CI \ (D)IS = ;
S
According to this de nition we only apply the upper approximation to the request and test for subsumption with the service o ers.
Optimizations During Query Execution As mentioned before, the approximation along the taxonomy produces a large amount of queries, leading to long delays until the matchmaker returns the results. To reduce the number of queries which have to be executed, we take advantage of the monotonicity property of the approximate subsumption and the graph structure created when approximating a request. The approach is based on the observation, that if two di erent queries, which were created during di erent steps and are related as ancestor / descendant, produce the same result lists, then, due to the monotonicity, every query between these two queries must produce the exact same result list and subsequently need not be executed. Our matchmaker utilizes this property by rst executing the root and leave queries of the graph, and compares their results pairwise. If the results of a pair are equal, every query between this pair are omitted, otherwise the graph is split in two parts, and again the top and the bottom queries of this subgraphs are executed and compared.
Intersection Query After having executed the original query and all of its approximations, we also add all service o ers to the result list, which have at least one concept in common with the request, no matter if it is used as input or output parameter. Surprisingly, this has a quite large impact on the precision of the Simple strategy, as we will show in the evaluation. 4
In this chapter we evaluate the performance of the implemented matcher. The following points are considered: { Retrieval performance of the implemented matcher compared to others { Response time to user requests
We conducted the performance tests on a Mac Pro 3,17 running Windows XP SP3 and Java 1.6.20. The Semantic Web Service Matchmaker Evaluation Environment8 (SME2) is a Java-based tool developed at the German Research Center for Arti cial Intelligence (DFKI) and is used during the Semantic Service Selection (S3) contest to evaluate and compare the performance of matchmakers. It supports the addition of matchmakers and test collections as a plug-in; currently collections for OWL-S and SAWSDL and the matchmakers written by the DFKI are publicly available.
SME2 evaluates the matchers' performance with standard performance
measures of information retrieval [
{ F-Measure: Weighted harmonic mean of Precision and Recall. Furthermore, the average precision for each query is computed and other statistics like execution time, query response time and memory consumption are recorded.
We use SAWSDL-TC9, which is supplied with SME2, as test collection for our matchmaker. It consists of 894 service o ers and 26 service requests. For each request the relevant service o ers are speci ed, allowing the calculation of the service measures mentioned above. The services are annotated with concepts from several di erent ontologies from di erent domains, ranging from military over education to health care and food.
The ontology with the extracted annotations of 894 services from SAWSDLTC contains 2149 named and 3261 anonymous classes (SubclassOf axioms). This ontology is then classi ed by the matcher using a description logic reasoner suitable for OWL. 4.2
This section compares the implemented matcher's retrieval performance to that
of SAWSDL-MX2, which is, like SME2, developed at the DFKI. It implements
several possibilities for calculating matches [
Additionally, SAWSDL-MX2 implements a machine learning feature to support the weighting of each of this properties, when it ranks the result list.
Table 1 gives an overview of the matchers' overall performance. The average precision is the average of the average precision for every query. The query response time is the time needed on average to execute a single query. The number of executed queries is the number of requests issued to the reasoner. This number is only available for our implementation. Overall Precision and Recall First, we will compare the overall precision and recall of our matcher utilizing the Simple and Taxonomy strategies and SAWSDL-MX2 (Fig. 3).
For every level of recall, Taxonomy achieves a higher precision than Simple. Because Taxonomy returns the same services as results as Simple does, and only re nes the ranking produced by it, both strategies deliver an almost identical performance at lowest and highest recall levels. Between those, Taxonomy shows the advantage of the ne grained approximation of concepts, achieving a precision which is up to 30% higher than Simple's. The Taxonomy approach also has the highest average precision of all 3 matchers. However, its precision is worse than that of SAWSDL-MX2 at the rst quarter of the result list, where SAWSDL-MX2 is able to reach a precision of almost 100%. Overall, the precision of both our implementations decreases slower than SAWSDL-MX2's, which drops below Simple's precision towards the end of the result list. Overall Recall and Fallout The recall/fallout diagram (Fig. 4) shows the same tendencies as the overall recall and precision, and again emphasizes the good proportion between precision and recall of the Taxonomy strategy. It returns less false positives than SAWSDL-MX2, which produces almost twice as much at full recall.
intersection query on the performance of the Simple and Taxonomy approach. The recall/precision curves for Taxonomy with and without the intersection query show only a slight di erence. For Simple, however, the intersection query increases the precision signi cantly; by up to 10% at full recall. The beginning of the curves is identical between the variants with and without intersection query, because it only adds o ers to the bottom of the result list, as mentioned before, and does not change the ranking of previous results. 4.3
Besides the retrieval performance, for a real world usage of the matcher, it is
also important to deliver results in a reasonable amount of time [
Table 2 shows the average value, median value, standard deviation and coe cient of variation of the response times the matchers need for evaluating a single request. These numbers show that a higher precision comes at the cost of longer wait time for the users. Simple is quite fast with about one second on average and SAWSDL-MX2 is not much slower, taking around three seconds to deliver results; Taxonomy uses a lot more time: 15 seconds on average.
Figure 6 and the median value, standard deviation and coe cient of variation show, that Simple and SAWSDL-MX have quite steady query response times, which do not vary wildly. For Taxonomy, however, the response times show huge di erences. Fortunately, most times are lower than the average, as indicated by the median value only being half of the average precision. For some queries, Taxonomy is faster than SAWSDL-MX, for others, there are some outliers for which execution took around two minutes.
In general, Simple is faster than SAWSDL-MX, which is in turn faster than Taxonomy, what corresponds directly with their average precision.
Taxonomy are already improved through the optimization described in Section 3.2. Without it, Taxonomy would need 20 seconds on average to answer a request (Table 3). The bene ts for Simple are minimal, as it only produces a small query graph. However, Taxonomy issues almost one third less queries to the reasoner, saving as much time for a request. We presented our implementation of a purely logic-based approximate web service matcher, which is based on approximate subsumption. The results of our evaluation are promising, especially for our goal to increase recall and still maintain a high precision. Considering the recall, our approach even performs better then all other matchers contending in the S3, and still achieves competitive precision. Our extensions aimed at decreasing query response time have generally helped to achieve a reasonable speed for our matcher, despite the additional executed queries. However, in some special cases our implementation still needs too much time for executing all approximations.
Future goals are to improve query performance, where we will consider several possibilities: As the approximated queries are independent from each other, they could be executed concurrently, but unfortunately parallelization is supported poorly by current reasoners. Another possibility to improve the perceived performance of the matcher is the implementation of an anytime behaviour, to show the user some rst results and then re ne or extend the list in the background.
Long term goals are the integration of user preferences in the approximation
and ranking process, e.g., black or white lists de ning which concepts should or
should not be approximated. Furthermore, the matcher could create proposals
for combining several services, which together can ful ll the users request. To
improve the matchers performance in a heterogeneous environment, where
service are annotated with concepts from di erent, not formally related ontologies,
an ontology alignment [