Copyright
is held by the author/owner(s).
WWW2003, May 20-24, 2003, Budapest, Hungary.
ACM 1-58113-680-3/03/0005.
We formalize general properties a matchmaker should have, then we present a matchmaking facilitator, compliant with desired properties.
The system embeds a NeoClassic reasoner, whose structural subsumption algorithm has been modified to allow match categorization into potential and partial, and ranking of matches within categories. Experiments carried out show the good correspondence between users and system rankings.
Categories and Subject Descriptors
H.4.2 [Information Systems Applications]: Decision
Support;
I.2.4 [Knowledge Representation Formalisms and
Methods]: Representation languages;
General Terms
Algorithms, Languages, Economics
E-commerce, Matchmaking, Knowledge Representation, Description Logics.
Widespread availability of resources and services enables - among other advantages - the interaction with a number of potential counterparts. The bottleneck is that it is difficult finding matches, possibly the best ones, between parties. Matchmaking is more difficult, yet challenging, when counterparts are peer entities, users or agents. As pointed out in [1] it is clear that bringing electronic commerce to its full potential requires a Peer-to-Peer (P2P) approach: anybody must be able to trade and negotiate with anybody else. The scenario envisaged by the Semantic Web initiative is one where peer entities may propose their goods and services and dynamically deal with counteroffers or further specifications, through the mediation of a matchmaking infrastructure. The infrastructure should receive and store advertisement descriptions by both demanders and suppliers and, as dynamically new demands or supplies are submitted, find the most satisfying matches and return them. The infrastructure has to treat in a uniform way suppliers and demanders, and base the matches on common, extensible, ontologies for describing both supplies and demands [15].
The uniform treatment of supplies and demands calls for technical solutions that must be quite different from the database ones usually employed in the Business-to-Consumer (B2C) scenario. In P2P matchmaking, the choice of which is the data, and which is the query depends just on the point of view - maybe, on who is more willing to actively find the other partner.
Knowledge representation (KR) - in particular, Description Logics (DL) - can deal with this uniform treatment of knowledge from suppliers and demanders, by modelling both as generic concepts to be matched. In fact, the logical approach allows for an open-world assumption. Incomplete information is allowed (and can be filled after a selection of possible matches), and absence of information can be distinguished from negative information, allowing to discard offers/requests without the necessary properties, and to ask for missing information in the potential matches.
Matchmaking infrastructures have been proposed in the literature (see Section 2 for a survey), but they lack a formal framework to logically classify and rank matches. The importance of ranking can not be underestimated, as it is of extreme importance for a practical use of the approach. The key questions that have to be answered in a dynamic framework are how far is a given demand (supply) from a potential counterpart? And which are the requirements that would eventually fulfill it? Such questions have to be answered also relying on publicly available algorithms, to encourage trust, and prevent arising of doubts on fairness of the proposals returned by the matchmaking facilitator.
If supplies and demands are simple names or strings, the only possible match would be identity, resulting in an all-or-nothing approach to matchmaking. Although effective for fixed technical domains, such an approach misses the fact that supplies and demands usually have some sort of structure in them. Such a structure could be exploited in order to evaluate ``interesting" inexact matches. Vector-based techniques taken by classical Information Retrieval (IR) can be used, too, thus reverting matchmaking to similarity between weighted vectors of stemmed terms, as proposed in the COINS matchmaker [27] or in LARKS [38]. Obviously lack of document structure in descriptions would make matching only probabilistic and strange situations may ensue, e.g., consider a simple demand ``apartment with two Rooms in Soho pets allowed no smokers" and a supply ``apartment with two Rooms in Soho, no pets, smokers allowed". They would correspond to a perfect match although being in obvious conflict.
Our setting allows one to categorize and rank matches according to their logical relation. In particular, we distinguish between Exact match: all requests in Demand are available in Supply (or vice versa); Potential match: some requests in Demand are not specified in Supply (and further action - inquire - can be taken); Partial match: some requests in Demand are in conflict with Supply (and further action - retract - can be taken). Though our logical setting is basically independent from the application adopted, our infrastructure is strongly related to CLASSIC [6,7]. CLASSIC is a knowledge representation system that, although not endowed of a language as expressive as more recent reasoners, e.g., FaCT and Racer, has polynomial-time inferences and, most important, is a real system, with a rich API and concrete datatypes that can be wrapped into a host system. The infrastructure currently embeds a modified version of NeoClassic, a CLASSIC implementation, to carry out the matchmaking process.
The rest of the paper is organized as follows. In the next section we report on relevant work. Then, to make the paper self contained, we present basic notions on on DLs. In Section 4 we present a formal framework for semantic-based matchmaking, and highlight properties that a matchmaker should have. In Section 5 we propose the architecture of an infrastructure we built, implementing the devised framework. Conclusion and future work are outlined in Section 6.
Throughout the paper, we refer to an apartments rental electronic marketplace, which was chosen as case study. A subset of the ontology used as reference in the examples is reported in Figure 1.
(createRole LOCATION) (createRole HASPETS) (createRole HASSERVICES) (createRole OCCUPANTS) (createRole HASROOMS) (createRole HASPLACES) (createRole COST true)[*] (createConcept ROOM TOP true) (createConcept PERSON TOP true) (createConcept NEWYORK TOP true) (createConcept SERVICES ROOM true) (createConcept KITCHEN SERVICES true) (createConcept WORKER PERSON true) (createConcept STUDENT PERSON true) (createConcept BATHROOM SERVICES true) (createConcept SMOKER PERSON smoke) (createConcept NON-SMOKER PERSON smoke) (createConcept BED (and (at-least 1 OCCUPANTS) (at-most 1 OCCUPANTS) (all OCCUPANTS PERSON)) true) (createConcept BEDROOM (and ROOM (all HASPLACES BED) (at-least 1 HASPLACES)) true) (createConcept SINGLE-ROOM (and BEDROOM (at-least 1 HASPLACES) (at-most 1 HASPLACES)) false) (createConcept DOUBLE-ROOM (and BEDROOM (at-least 2 HASPLACES) (at-most 2 HASPLACES)) false) (createConcept MULTIPLE-ROOM (and BEDROOM (at-least 3 HASPLACES)) false) (createConcept APARTMENT (and (at-least 1 OCCUPANTS) (all OCCUPANTS PERSON) (at-least 1 HASROOMS) (all HASROOMS ROOM) (at-least 2 HASSERVICES) (all HASSERVICES SERVICES)) true)
Earliest matchmakers, based on the KQML, were proposed in [16] and [27]. In these works matchmaking was introduced as an approach whereby potential producers / consumers could provide descriptions of their products/needs, either directly or through agents mediation, to be later unified by a matchmaker engine to identify potential matches. Nevertheless the proposed solutions to this challenging issue reverted to either a rule based approach using KIF (the SHADE prototype) or a free text comparison (the COINS prototype), which basically deals with descriptions as free-text retrieval tools do. Standard Information retrieval techniques have been also used in the recently proposed GRAPPA matchmaking framework [40]
Approaches similar to the cited ones were deployed in SIMS [2], which used KQML and LOOM as description language and InfoSleuth [21], which adopted KIF and the deductive database language LDL++. LOOM is also at the basis of the subsumption matching addressed in [17].
More recently there has been a growing interest towards matchmaking engines and techniques, with emphasis placed either on e-marketplaces or generic Web services, in view of the promised transformation of the Web from human understandable to the Semantic, machine understandable, Web. Significant examples include [38] and [31] where a language, LARKS, is proposed specifically designed for agent advertisement. The matching process is carried out through five progressive stages, going from classical IR analysis of text to semantic match via Q-subsumption. The notion, inspired by Software Engineering, of plug-in match is introduced to overcome in some way the limitations of a matching approach based on exact match. No ranking is presented but for what is called relaxed match, which basically reverts again to a IR free-text similarity measure. So a basic service of a semantic approach, such as inconsistency check, seems unavailable with this type of match.
In [39] and [18] a matchmaking framework is proposed, which operates on service descriptions in DAML+OIL and is based on the FaCT reasoner. Unfortunately as the authors admit, though very expressive, FaCT lacks of concrete datatypes, which are obviously extremely useful for, e.g., e-commerce applications, and their prototype is incomplete.
Semantic service discovery via matchmaking in the Bluetooth [4] framework is investigated in [34]. Also here the issue of approximate matches, to be somehow ranked and proposed in the absence of exact matches, is discussed, but as in the previous papers no formal framework is given. Instead a logical formulation should allow to devise correct algorithms to classify and rank matches.
Also various current commercial electronic marketplaces try to provide some matchmaking capabilities between demand and supply. Jango [22] provides a system that basically only allows comparison, in terms of price, of goods available in on-line stores on the Internet. Obviously the description of the product to be matched has to be complete and consistent and no reasoning on set containment or inconsistency check can be carried out. PersonaLogic [32] allows customers to impose constraints for alternatives seeking. It must be pointed out that constraints cannot be dynamically placed but have to be taken from a pre-determined category set. Kasbah [25] is a more effective system, which allows to dynamically set constraints, yet it does not allow handling of inconsistency and partial or potential matches. A similar approach is also deployed in Tete-a-Tete [28].
A more advanced constraint based approach is proposed in [24], able to to handle conflicting preferences in demands / supplies. Consistency check of preferences is accomplished visiting an offer synthesis graph with path consistency algorithm each time a new offer is entered. A further example is Smartclient [33], a system that allows users basic criteria adjustment, by presenting an interface that shows the initial search space, which can be reduced by further user interaction with the results. The underlying system basically relies on partial constraint satisfaction techniques. A recent proposal along the same lines is in [41] where negotiation agents are formally modelled using an object-oriented constraint language.
IBM's Websphere matchmaking environment is, to our knowledge, the first example of commercial solution that places an explicit emphasis on the matchmaking between a demand and a supply in a peer-to-peer way, which is referred to in [19] as symmetric matchmaking. As we will point out, the notion of symmetric matchmaking is questionable. The environment is based on a matchmaking engine that describes supplies / demands as properties and rules. Properties are name-value pairs constructed using an extension of Corba Trading service language. Rules are basically constructed using a generic script language. Matching is then accomplished by simply comparing properties and verifying rules. No notion of distinction between full, partial potential and inconsistent matches are present.
A similar approach, with descriptions defined in XML and again a rule based decision system is in [9]. Here descriptions of supply / demand can be stored in the e-service platform when a match is not available for further processing should a counterpart become available. In [37] an extension to the original Websphere matchmaker is proposed, which introduces users' specification of negotiable constraints when no total match is available. So the approach aims at some of the issues also addressed in this paper, but with a different, constraint based, perspective.
In [12] an initial setting for logical matchmaking was presented in a person-to-person framework.
It is noteworthy that matching in DLs has been widely treated in [3] although with no relation to matchmaking. In fact, in that work expressions denoting concepts are considered, with variables in expressions. Then a match is a substitution of variables with expressions that makes a concept expression equivalent to another. Also the more general setting of concept rewriting in DLs has no direct relation with matchmaking.
More formally, a semantic interpretation is a pair Á =(D, ·Á), which consists of the domain D and the interpretation function ·Á, which maps every concept to a subset of D, every role to a subset of D×D, and every individual to an element of D. We assume that different individuals are mapped to different elements of D, i.e., aÁ ¹ bÁ for individuals a ¹ b. This restriction is usually called Unique Name Assumption (UNA).
Basic elements can be combined using constructors to form concept and role expressions, and each DL has its distinguished set of constructors. Every DL allows one to form a conjunction of concepts, usually denoted as ⊓; some DL include also disjunction ⊔ and complement Ø to close concept expressions under boolean operations. Roles can be combined with concepts using existential role quantification, e.g., book ⊓$author. italian which describes the set of books whose authors include an Italian, and universal role quantification, e.g., product ⊓"supplier. japanese, which describes products sold only by Japanese suppliers. Other constructs may involve counting, as number restrictions: apartment ⊓( £ 1 hasRooms) expresses apartments with just one room, and book ⊓( ³ 3 author) describes books written by at least three people. Many other constructs can be defined, increasing the expressive power of the DL, up to n-ary relations [8].
Expressions are given a semantics by defining the interpretation function over each construct. For example, concept conjunction is interpreted as set intersection: (C ⊓D)Á = CÁÇD Á, and also the other boolean connectives ⊔ and Ø, when present, are given the usual set-theoretic interpretation of È and complement. The interpretation of constructs involving quantification on roles needs to make domain elements explicit: for example, ("R.C)Á = { d1 Î D | "d2 Î D:(d1,d2) Î RÁ® d 2 Î CÁ}
Concept expressions can be used in inclusion assertions, and definitions, which impose restrictions on possible interpretations according to the knowledge elicited for a given domain. For example, we could impose that books can be divided into paperbacks and hardcover using the two inclusions book ⊑paperbacks ⊔hardcover and paperbacks ⊑Ø hardcover. Or, that books have only one title as book ⊑( £ 1 title). Definitions are useful to give a meaningful name to particular combinations, as in doubleRoom º room ⊓(= 2 hasPlaces) . Historically, sets of such inclusions are called TBox (Terminological Box). In simple DLs, only a concept name can appear on the left-hand side of an inclusion.
The semantics of inclusions and definitions is based on set containment: an interpretation Á satisfies an inclusion C ⊑ D if CÁ Í DÁ, and it satisfies a definition C = D when CÁ=D Á. A model of a TBox T is an interpretation satisfying all inclusions and definitions of T.
In every DL-based system, at least two basic reasoning services are provided:
The CLASSIC system [6,7] has been developed at AT&T Bell Laboratories, where it has been applied in several projects for configuration [42] and program repositories [11]. Its language has been designed with the goal to be as expressive as possible while still admitting polynomial-time inferences. So it provides intersection of concepts but no union, universal but not existential quantification over roles, and number restrictions over roles but no intersection of roles, since each of these combinations is known to make reasoning NP-hard [13]. Classic obviously provides subsumption and satisfiability reasoning services. Being a complete knowledge representation system (and not just a reasoner), Classic provides also data types as numbers and strings, and other services which are useful in a deployed prototype. Every Classic concept has an equivalent normal form, hence using such a normal form ensures syntax independence. In our current setting we use just a subset of CLASSIC constructors, i.e., those needed in a ALN logic.
Example Demand: (and APARTMENT (all HASROOMS BEDROOM) (at-most 0 HASPETS))
POST /soap/servlet/rpcrouter HTTP/1.0 Host: localhost:8070
Content-Type: text/xml Content-Length: 597 SOAPAction: ""
<SOAP-ENV:Envelope
xmlns:SOAP-ENV="http://schemas.xmlsoap.org/soap/envelope/"
xmlns:xsi="http://www.w3.org/1999/XMLSchema-instance"
xmlns:xsd="http://www.w3.org/1999/XMLSchema">
<SOAP-ENV:Body> <ns1:translate xmlns:ns1="urn:demo1:Translator"
SOAP-ENV:encodingStyle="http://schemas.xmlsoap.org/soap/encoding/">
<text xsi:type="xsd:string">(and APARTMENT (all HASROOMS BEDROOM)
(at-most 0 HASPETS))</text> <uri
xsi:type="xsd:string">http://www.example.org/rent-toy-ontology#</uri>
<requestType xsi:type="xsd:string">demand</requestType>
</ns1:translate> </SOAP-ENV:Body> </SOAP-ENV:Envelope>
Property 1 [Open-world descriptions] The absence of a characteristic in the description of a supply or demand should not be interpreted as a constraint of absence. Instead, it should be considered as a characteristic that could be either refined later, or left open if it is irrelevant for a user.
This property states that on one side, the interface for describing requests to the matchmaking facilitator should be liberal enough about details, and on the other side, that the algorithm employed for matchmaking should take this issue into account.
Property 2 [Non-symmetric evaluation] A matchmaking system may give different evaluations depending on whether it is trying to match a supply S with a demand D, or D with S - i.e., depending on who is going to use this evaluation.
This property was evident in the above example, where all constraints of D were fulfilled by S but not vice versa. Hence, S should be among the top ranked supplies in the list of potential partners of the demander, while D should not appear at the top in the list of potential partners of the supplier.
Of course, the sets-of-words approach would be too sensitive to the choice of words employed, to be successfully used - it misses meanings that relate words. In the apartments rental scenario, a matching facilitator should take into account that ``boiler" is a form of heating system, or that a constraint ``no-pets" applies also to a dog. Obviously such fixed-terminology problems are overcome if terms have a logical meaning through an ontology [15].
Hence, from now on we suppose that supplies and demands are expressed in a description logic DL, equipped with a model-theoretic semantics. We note that this approach includes the sets-of-keywords one, since a set of keywords can be considered also as a conjunction of concept names, e.g., the set { apartment,soho,twoRooms } can be equivalently considered as apartment ⊓soho ⊓twoRooms - without modelling the structure of concepts. Obviously, entering into the structure of concepts may yield to apartment ⊓"location. soho ⊓(= 2 hasRooms), while a keyword ``noPets" can be given a logical meaning as "occupants.( £ 0 hasPets).
We suppose also that a common ontology for supplies and demands is established, as a TBox in DL. Now a match between a supply S and a demand D could be evaluated according to T. Let T ⊧¼ denote logical implication (truth in all models of T), and let ⊑ (subsumption) denote also implication between constraints of S and D. There are three relations between concepts expressing supplies and demands, that we consider meaningful in matchmaking:
Implication. If T ⊧ (D ⊑S), then every constraint imposed by D is fulfilled (implied) by S, and vice versa if T ⊧(S ⊑D). This relation extends the previous set-based inclusion to general concepts. If both T ⊧ (D ⊑S) and T ⊧ (S ⊑D), then D and S should be considered equivalent in T. This relation extends exact matching by ruling out irrelevant syntactic differences.
Consistency. If D ⊓S is satisfiable in T, then there is a potential match, in the sense that the constraints of neither proposal exclude the other. This relation has been highlighted also by other researchers [39]. However, that proposal lacks a ranking between different potential matches, which we believe is fundamental in order to support a user in the choice of the most promising partners, among all potential ones.
Inconsistency. Otherwise, if D ⊓S is unsatisfiable in T, some constraints of one proposal are in conflict with the properties of the other one. However, when (say) a demand D has no potential matches, also supplies S which are inconsistent with D may be reconsidered, if the demander accepts to revise some of D's constraints. The point of course is in revising not too much. Hence, also in this case a ranking - different from the one of potential matches - is fundamental, in order to highlight the least unsatisfactory proposals, that we call near miss or partial match.
We now highlight some properties that - we believe - every ranking function should have in logical matchmaking. We state these properties in form of definitions, since we distinguish between rankings having the property from rankings that do not.
First of all, if a logic is used to give some meaning to descriptions of supplies and demands, then proposals with the same meaning should have the same ranking, independently of their syntactic descriptions.
Definition 1 (SYNTAX INDEPENDENCE IN RANKING POTENTIAL MATCHES) A ranking of potential matches is syntax independent if for every pair of supplies S1 and S2, demand D, and ontology T, when S1 is logically equivalent to S2 then S1 and S2 have the same ranking for D, and the same holds also for every pair of logically equivalent demands D1, D2 with respect to every supply S.
For example, an apartment S1, described as available for the summer quarter, should have the same rank - with respect to a request - as another S2, identical but for the fact that it is described to be available for June-July-August.
A similar property should hold also for ranking incoherent pairs of supplies and demands. The rationale of this property is that, in looking for least unsatisfactory proposals - when recovering from an initial ``no potential match" - a partial match should be as ``not-so-bad" as any equivalent one.
Definition 2 (SYNTAX INDEPENDENCE IN RANKING PARTIAL MATCHES) A ranking of partial matches is syntax independent if for every pair of supplies S1 and S2, demand D, and ontology T, when S1 is logically equivalent to S2 then S1 and S2 have the same ranking for D, and the same holds also for every pair of logically equivalent demands D1, D2 with respect to every supply S.
Clearly, when the logic admits a normal form of expressions - as CNF or DNF for propositional logic, or the normal form of concepts for the DL of CLASSIC mentioned earlier - using such a normal form ensures by itself syntax independence.
We now consider the relation between ranking and implications. We go back to the descriptions with sets of words, since they are easy to read through. Let D be a demand and S1, S2 be two supplies defined as follows:
|
|
Definition 3 (MONOTONICITY OF RANKING POTENTIAL MATCHES OVER SUBSUMPTION) A ranking of potential matches is monotonic over subsumption whenever for every demand D, for every pair of supplies S1 and S2, and ontology T, if S1 and S2 are both potential matches for D, and T ⊧ (S2 ⊑S1), then S2 should be ranked either the same, or better than S1, and the same should hold for every pair of demands D1,D2 with respect to a supply S.
Intuitively, the above definition could be read of as
A ranking of potential matches is monotonic over subsumption if the more specific the better.Observe that we use the word ``better" instead of using any symbol £ , ³ . This is because some rankings may assume that ```better" means ``increasing" (towards infinity, or 1) while others may assume ``decreasing" (towards 0).
When turning to partial matches, in which some properties are already in conflict between supply and demand, the picture reverses. Now, adding another characteristic to an unsatisfactory proposal may only worsen this ranking (when another characteristic is violated) or keep it the same (when the new characteristic is not in conflict). Note that this ranking should be kept different from the ranking for potential matches. After all, accepting to discard one or more characteristics that we required is much worse than deciding among a ranked list of potential matches.
Definition 4 (ANTIMONOTONICITY OF RANKING PARTIAL MATCHES OVER IMPLICATION) A ranking of partial matches is antimonotonic over implication whenever for every demand D, for every pair of supplies S1 and S2, and ontology T, if S1 and S2 are both partial matches for D, and T ⊧ (S2 ⊑ S1), then S2 should be ranked either the same, or worse than S1, and the same should hold for every pair of demands D1,D2 with respect to a supply S.
Intuitively, the above property could read as: A ranking of partial matches is antimonotonic over subsumption if the more specific, the worse.
We remark that the properties and definitions we stated in this section are independent of the particular DL employed, or even the particular logic chosen. For instance, the same properties could be stated if propositional logic was used to describe supplies, demands and the ontology. In this respect, we believe that this section keeps its significance also if one chooses more expressive DLs like SHOQ(D) [20] or even logics for which representation and reasoning system are not yet fully available, like DAML [31].
Using the highlighted properties as a formal specification we designed and implemented a prototype facilitator. The system embeds a modified NeoClassic reasoner. NeoClassic is a C++ implementation of the original Classic. The changes affected the structural subsumption algorithm, which was modified to compute matches classification and ranking, as will be shown later on.
The general architecture of the facilitator is pictured in Figure 3; its main components are the MatchMaker service (MMS) and the Communication Service (CS). The system can accept requests by a heavy weight client a light weight client and a generic user agent.
The heavy weight client is a Java applet that allows advertisement description in natural language. The client is anyway strongly dependent on the reference ontology, because of the inherent contextualization. Currently the only supported ontology is the apartments rental one, used in our case study. The input for the Natural Language Interpreter (NLI) module is a free text description of an advertisement for apartment rental. The output is a string formatted in KRSS (Knowledge Representation System Specification) [26] of the input sentence. To perform a better natural language semantic analysis using context information, the grammar rules contain the SEM feature, whose values refer to a set of fundamental categories identified within the reference ontology, e.g., AP for apartment, ROOM for rooms ACC for accessories. In this way, the grammar simultaneously represents both syntactic and semantic behavior of the analyzed context. The computational approach is a chart-based one. The algorithm can recognize unknown terms and ask for synonyms. If the new terms introduce new information in the system, i.e. information not described in the ontology, this last is updated. The unique constraint is that new information has to be related to accessories, in our current settings. Once the ontology has been updated, the system lets advertisers know that they can update their advertisements using the new available information.
The light weight client is still a Java applet, but an extremely light one, in view of application on devices such as PDAs that sends, via SOAP [36], an advertisement i.e., a description of the request to be matched, as a string in KRSS syntax. Figure 2 shows an example advertisement in KRSS.
The SOAP packet contains the string and the URI of the reference ontology. The CS module is a web service (registered with XMethods) whose main purpose is the translation of KRSS descriptions in portable DAML+OIL ones. The module, upon receipt of the packet, transforms the string in a DAML+OIL formatted description, using Jena APIs [23]. Figure 4 shows the corresponding packet.
Advertisements can be received by the system also through a generic agent. In this case they are accepted only if expressed in DAML+OIL. The CS translates the demands and supplies from KRSS to DAML+OIL.
The description is forwarded to the Matchmaking service, which is the principal module of the architecture. It receives the SOAP packet, extracts the code and the URI that references the requested ontology. The matchmaking engine preliminarily checks for satisfiability w.r.t. the referenced ontology. If the check succeeds it carries out the matchmaking process with all descriptions in the repository corresponding to the given ontology, as will be described in detail in the next subsection.
The system accepts two types of requests, advertisement and query. For the first one, the system will store the request. In this way satisfiable queries/demands that remain unmatched will be automatically reexamined when new supplies are provided, and notification will be provided for successful match. The same service is available for unmatched supplies. The query service, instead, does not permanently store demand/supply descriptions. The matchmaker output is forwarded according to specifications included in the SOAP packet and can be formatted as an e-mail, a GSM SMS (Small Message System) or a JSP, if the request has been submitted by a client. If the request has been submitted by an agent the response will be sent to the communication service for translation from KRSS to DAML+OIL.
POST /soap/servlet/rpcrouter HTTP/1.0 Host: localhost:8070
Content-Type: text/xml Content-Length: 1979 SOAPAction: ""
<SOAP-ENV:Envelope
xmlns:SOAP-ENV="http://schemas.xmlsoap.org/soap/envelope/"
xmlns:xsi="http://www.w3.org/1999/XMLSchema-instance"
xmlns:xsd="http://www.w3.org/1999/XMLSchema">
<SOAP-ENV:Body> <ns1:matchMake xmlns:ns1="urn:demo1:Matchmaker"
SOAP-ENV:encodingStyle="http://schemas.xmlsoap.org/soap/encoding/">
<text xsi:type="xsd:string"> <rdf:RDF
xmlns:rdf='http://www.w3.org/1999/02/22-rdf-syntax-ns#'
xmlns:daml='http://www.daml.org/2001/03/daml+oil#'
xmlns:rdfs='http://www.w3.org/2000/01/rdf-schema#'>
<daml:Datatype rdf:about='http://www.example.org/rent-toy-ontology#HASROOMS'/>
<daml:Datatype rdf:about='http://www.example.org/rent-toy-ontology#BEDROOM'/>
<daml:Datatype rdf:about='http://www.example.org/rent-toy-ontology#HASPETS'/>
<rdfs:Class rdf:about='http://www.example.org/rent-toy-ontology#APARTMENT'/>
<daml:Property rdf:about='http://www.daml.org/2001/03/daml+oil#maxCardinality'/>
<daml:Property rdf:about='http://www.daml.org/2001/03/daml+oil#onProperty'/>
<daml:Property rdf:about='http://www.daml.org/2001/03/daml+oil#toClass'/>
<daml:Restriction>
<daml:onProperty rdf:resource='http://www.example.org/rent-toy-ontology#HASROOMS'/>
<daml:toClass rdf:resource='http://www.example.org/rent-toy-ontology#BEDROOM'/>
</daml:Restriction>
<daml:Restriction daml:maxCardinality='0'>
<daml:onProperty rdf:resource='http://www.example.org/rent-toy-ontology#HASPETS'/>
</daml:Restriction>
</rdf:RDF> </text> <uri
xsi:type="xsd:string">http://www.example.org/rent-toy-ontology#</uri>
<requestType xsi:type="xsd:string">demand</requestType>
</ns1:matchMake> </SOAP-ENV:Body> </SOAP-ENV:Envelope>
Potential and partial matches can also trigger further communication services 1. For partial matches, on the basis of the matchmaker response, a demand can be revised, e.g., relaxing (retracting) some constraint. For potential matches the system can ask the supplier of the advertisement whether some features although not advertised are anyway available. It should be noticed that the architecture can simply be modified to host other reasoners, such as FaCT or Racer. The rationale of the choice of the Classic system, apart from the obviously useful availability of concrete datatypes and the possibility to extend its functionalities through test functions, is that its polynomial time inference allows practically synchronous operations, even with large ontologies.
The system receives the KRSS string describing the demand/supply and the URI referencing the proper ontology. The Reasoner checks the description for consistency; if it fails, based on the reasoner output, the system returns an error message that is forwarded to the client/agent originating the request. Otherwise the proper matchmaking process takes place. To this aim we devised two algorithms, based on a modification of the original CLASSIC structural [7] subsumption algorithm, to classify and rank matches. The rationale and the structure of the algorithms are described hereafter.
A CLASSIC concept C can be put in normal form as Cnames ⊓C# ⊓Call. Without ambiguity, we use the three components also as sets of the conjoined concepts. Moreover, recall that the TBox in CLASSIC can be embedded into the concepts, hence we do not consider explicitly the TBox, although it is present.
The algorithm easily follows a structural subsumption algorithm, except for the treatment of universal role quantification, that we explain now with the help of an example. Suppose a demand D = apartment ⊓"hasRooms.( singleRoom ⊓nonSmokerRoom) and two supplies C1, C2, defined as follows:
|
Algorithm rankPotential (C, D);
input CLASSIC concepts C, D, in
normal form,
such that C
⊓ D is satisfiable
output rank n ³ 0 of C
w.r.t. D, where 0 means
that C
⊑ D (best ranking)
begin algorithm
let n : = 0 in
/* add to n the number of concept names in D */
/* which are not among the concept names of C */
1. n : = n + |Dnames+
- Cnames+
|;
/* add to n number restrictions of D */
/* which are not implied by those of C */
2. for each concept (
³ x R)
Î D#
such that there is no concept (
³ y R)
Î C# with y
³ x
n : = n + 1;
3. for each concept ( £
x R) Î
D\sharp
such that there is no concept (
£ y R)
Î C# with y
£ x
n : = n + 1;
/* for each universal role quantification in D */
/* add the result of a recursive call */
4. for each concept
"R.E
Î Dall
if there does not exist
"R.F
Î Call
then n : = n + rankPotential(T, E);
else n : = n + rankPotential(F, E);
return n;
end algorithm
It is easy to modify the algorithm if weights on subconcepts of D are taken into account: instead of adding 1 to n for each D's concept missing in C, one just adds the corresponding weight. In this way, when the proposal concerns apartments, the concept apartment gets the highest weight, and minor characteristics get lower weights. Then, a far rank would mean that either many minor characteristic, or a very important one, are left unspecified in C.
We implemented also a version of the algorithm in which weights are learned by the system, upon repeated analysis of proposals. In this case, of course, the learned weights are absolute ones, and not relative to a particular actor.
The algorithm for ranking partial matches follows the partition of CLASSIC concepts into names, number restrictions, and universal role quantifications. However, this time we are looking for inconsistencies. Hence, when a universal role quantification is missing in either concept, the recursive call is unnecessary. In fact, suppose that "R.E Î Dall while no quantification on R is present in Call. No quantification is equivalent to the concept "R.T, and a recursive call yields a comparison between T and E, which can only yield a 0-rank since T is consistent with every concept. Recall also that an inconsistency arising from ( ³ x R) with x ³ 1 in one concept, and "R.^ in the other concept, is already evidenced in the comparison of number restrictions, because ( £ 0 R) has been added to the normal form of the latter concept.
Algorithm rankPartial (C, D);
input CLASSIC concepts C, D,
both in normal form
output rank n ³ 0 of C
w.r.t. D,
where 0 means that C
⊓D is satisfiable
begin algorithm
let n : = 0 in
/* add to n the number of concept names in C */
/* which are disjoint from the concept names of D */
for each concept name A
Î Cnames+
if there exists a concept
ØA
Î
DnamesØ
then n : = n + 1;
/* add to n number restrictions of C */
/* which are in conflict with those of D */
for each concept ( ³
x R) Î
C#
such that there is a concept (
£ y R)
Î D# with y <
x
n : = n + 1;
for each concept ( £
x R) Î
C#
such that there is a concept (
³ y R)
Î D# with y >
x
n : = n + 1;
/* for universal role quantifications in C and D */
/* which are triggered by an at-least number restriction on
either concept */
/* add the result of a recursive call */
for each concept
"R.F
Î Call
if either (there exist both
( ³ x R)
Î C# with x
³ 1 and
"R.E
Î Dall with E
¹
^)
or (F ¹
^ and there exist
both ( ³ x R)
Î D# with x
³ 1
and "R.E
Î Dall)
then n : = n + rankPartial(F,E);
return n;
end algorithm
Obviously also in this case weights could be added to subconcepts of D, where the greater the weight, the more that characteristic is important, making the rank of C far off when in conflict.
It should be noted that for both algorithms, weights can be determined according to their relevance/probability with various approaches, including, e.g., utility theory based approaches [10]. In this perspective our framework can benefit of, rather than being alternative to, other methods for knowledge elicitation.
For both algorithms it can be proved they respect the properties highlighted in the previous section. With reference to complexity, it is well known [30] that the expansion of the TBox in the construction of the normal form can lead to an exponential blow-up. Nevertheless the expansion is exponential in the depth of the hierarchy of the TBox T; if the depth of T is O(log|T| ), then the expansion is polynomial, and so also the algorithm.
Each match can return a 0, which means exact match or a value > 0. Recall that returned values for partial matches and potential matches have logically different meaning and matching descriptions are sorted in different sets. The matching engine may return then up to three disjoint result sets, with results ranked in the potential and partial sets.
The matchmaker can also use weights to increase the relevance of concepts. The weight is a positive integer that keeps into account the occurrence of a role or a concept w.r.t. all Demands and Supplies available for a reference ontology. For each concept or role present in an advertisement, in normal form, that is A Î Dnames+ or a concept ( ³ x R) Î D# or ( £ x R) Î D# the corresponding weight is increased after each matching process. Obviously the matchmaking algorithm is modified in that increments are no more unitary but correspond to the assigned weights. To simplify the reading no weights are used in the following.
| match | rank |
| demand,supply1 | 0 |
| demand,supply2 | 0 |
| demand,supply3 | 1 |
| demand,supply4 | 2 |
| demand,supply5 | 0 |
This result points out that demand cannot be satisfied by supplies 3 and 4. The system provides a rank that indicates how far the demand is w.r.t. the supplies, i.e., how much should be revised in the demand. The system can also explicit unsatisfied concepts of the demand. In this way the user can decide to revise his/her demand advertisement.
Remaining supplies are all potential matches, i.e., there is nothing in conflict with demand in them. Yet it is obvious that a user needs to know those supplies that may best match the demand. The execution of rankPotential algorithm provides the answer.
| match | rank |
| demand,supply1 | 1 |
| demand,supply2 | 0 |
| demand,supply5 | 7 |
Results in Table 2 show that supply2 is an exact match w.r.t. the given demand. Supplies 1 and 5 are potential matches, i.e., there is no characteristic in conflict but some of the requests in demand are not explicitly available. The user may then, e.g., when no exact match is available, carry out further investigations on potential matches. In this process he/she is again helped by the system ranking, which represents the distance between the demand and supply.
It is noteworthy that the ranking also prevents advertisements from being submitted in an extremely generic way. Simple subsumption matching [39] without ranking, in fact, favors unfair generic advertisements, which will be present in practically any retrieved set. Instead in our system, though logically potentially matching, the generic supply5 is given an high rank, which penalizes it.
demand : (and APARTMENT (all HASROOMS BEDROOM) (at-most 0 HASPETS))
supply1: (and APARTMENT (all HASROOMS SINGLE-ROOM) (all OCCUPANTS SMOKER))
supply2: (and APARTMENT (at-least 2 HASROOMS) (at-most 2 HASROOMS) (all HASROOMS DOUBLE-ROOM) (at-most 0 HASPETS))
supply3: (and APARTMENT (at-least 1 HASPETS))
supply4: (and (at-most 1 HASSERVICES) (all HASSERVICES BATHROOM) (at-least 2 HASPETS))
supply5: (and APARTMENT)
demand NORMAL FORM
(APARTMENT , (at-least 1 OCCUPANTS) , (all OCCUPANTS PERSON) ,
(at-least 1 HASROOMS) , (at-least 2 HASSERVICES) , (all
HASSERVICES (SERVICES ,
ROOM)
) , (all HASROOMS (BEDROOM ,
ROOM ,
(all HASPLACES (BED ,
(at-least 1 OCCUPANTS) ,
(at-most 1 OCCUPANTS) ,
(all OCCUPANTS PERSON)) ,
)
(at-least 1 HASPLACES))
) , (at-most 0 HASPETS))
______________________________________________________________________________________
supply1 NORMAL FORM
(APARTMENT , (at-least 1 OCCUPANTS) , (all OCCUPANTS PERSON) ,
(at-least 1 HASROOMS) , (at-least 2 HASSERVICES) , (all
HASSERVICES (SERVICES ,
ROOM)
) , (all HASROOMS (BEDROOM ,
ROOM ,
(all HASPLACES (BED ,
(at-least 1 OCCUPANTS) ,
(at-most 1 OCCUPANTS) ,
(all OCCUPANTS PERSON)) ,
)
(at-least 1 HASPLACES)
(at-least 1 HASPLACES)
(at-most 1 HASPLACES))
) (all OCCUPANTS SMOKER ,
NONSMOKER))
________________________________________________________________________________________
supply2 NORMAL FORM
(APARTMENT , (at-least 1 OCCUPANTS) , (all OCCUPANTS PERSON) ,
(at-least 1 HASROOMS) , (at-least 2 HASSERVICES) , (all
HASSERVICES (SERVICES ,
ROOM)
) , (at-least 2 HASROOMS) , (at-most 2 HASROOMS) , (all HASROOMS
(BEDROOM ,
ROOM ,
(all HASPLACES (BED ,
(at-least 1 OCCUPANTS) ,
(at-most 1 OCCUPANTS) ,
(all OCCUPANTS PERSON)) ,
)
(at-least 1 HASPLACES)
(at-least 2 HASPLACES)
(at-most 2 HASPLACES))
) (at-most 0 HASPETS))
________________________________________________________________________________________
supply3 NORMAL FORM
(APARTMENT , (at-least 1 OCCUPANTS) , (all OCCUPANTS PERSON) ,
(at-least 1 HASROOMS) , (all HASROOMS ROOM) , (at-least 2
HASSERVICES) , (all HASSERVICES (SERVICES ,
ROOM)
) , (at-least 1 HASPETS))
________________________________________________________________________________________
supply4 NORMAL FORM
((at-most 1 HASSERVICES) , (all HASSERVICES BATHROOM SERVICES) ,
(at-least 2 HASPETS))
________________________________________________________________________________________
supply5 NORMAL FORM
(APARTMENT , (at-least 1 OCCUPANTS) , (all OCCUPANTS PERSON) ,
(at-least 1 HASROOMS) , (all HASROOMS ROOM) , (at-least 2
HASSERVICES) , (all HASSERVICES (SERVICES ,
ROOM)
)
________________________________________________________________________________________
The non-symmetric behavior of the matchmaking process can also be highlighted here by simply exchanging the arguments of the matchmaking algorithms. By taking, e.g., the description of supply1 and matching it against the example demand, the rankPotential algorithm returns a rank 4.
To evaluate the ability of the system to meet users' expectations we set up a little experiment.
We selected all apartments-rental advertisements from the dedicated section of a local newspaper on Oct. 6th, 2002. We subdivided them in two sets, demands (23 advertisements) and supplies (39 advertisements). We submitted to twenty volunteers of various sex and age, a questionnaire that included 12 items. Each item was one demand and a set of up to eight supplies, or one supply and a set of up to eight demands. Volunteers were asked to rank, according to their judgement, elements of each set with respect to the given advertisement, with the following question: Order the following Demands(Supply) with respect to the given Supply (Demands) as you would contact them had you issued the given Supply (Demand). Volunteers were given unlimited time and in average it took approximately half hour to complete the questionnaire.
Groups of advertisements where chosen by the authors so that items included only potential matches, only partial matches, and both potential and partial matches. It is noteworthy that, at least for the single-day pick we made, we were not able to detect any exact match. After that the same sets of items were submitted to the matchmaking engine.
As a general consideration, the system response was quite close to the users' ones, and considering average volunteers orderings the systems rankings was in agreement with the human judgement almost always. Standard deviation w.r.t. averaged users ranking was:
spotential matches=8.3%, spartial matches=9.7%, smixed=9.1%.
Figure 8 shows a single result, in a graphical form, for mixed potential and partial demands w.r.t. to a supply. Notice that, while volunteers gave strictly ranked orderings, the system could also provide equal ranking for various matches. It should be noticed that the main gap the system had with respect to users was its use of at-least at-most restrictions, especially on price. In other words the users evaluated proportionally the violation of the price constraint, while the system did not. We are hence introducing in the weighted version of the matchmaker a corrective to this issue, by proportionally weighting numerical roles w.r.t. the mean value of at-least at-most restrictions.
The core engine has been implemented modifying the NeoClassic subsumption algorithm in a way that allows categorization of match type and the ranking of matches. While large scale experiments are in progress, a simple experiment with a case study ontology has shown a good correspondence with human perception of the system provided rankings.
We are currently working on an extension of the system to DAML-S and UDDI, which will also feature a negotiation module. An application of the current approach to Bluetooth, with a stack modified to incorporate semantic descriptions along the lines highlighted in [34], has also been implemented and is being tested.
The kind of hypothetical reasoning used in evaluating potential matches gave us also the basic motivation to study abduction in DLs and relative computational complexity. A suitable theoretical framework has been devised and first results are forthcoming.
This work has been supported by MURST project CLUSTER22, by EU-POP project ``Negotiation Agents for the Electronic Marketplace", by project ``Tecnologie innovative per la valorizzazione e la fruizione dei Beni Culturali", by Italian CNR projects LAICO, and ``Metodi di Ragionamento Automatico nella modellazione ed analisi di dominio".
1These services are currently implemented only for the dedicated clients.
2A lodging
is considered as neither an apartment nor a room; advertisements
were drawn from actual newspapers announcements.
Copyright is held by the author/owner(s). WWW2003, May
20–24, 2003, Budapest, Hungary. ACM
1-58113-680-3/03/0005.