The Linked Open Data community continuously releases massive amounts of RDF data that shall be used to easily create applications that incorporate data from di erent sources. Inter-operability across di erent sources requires links at instance- and at schema-level, thus connecting entities on the one hand and relating concepts on the other hand. State-of-the-art entity- and ontology-alignment methods produce high quality alignments for two \nicely structured" individual sources, where an identi cation of relevant and meaningful pairs of ontologies is a precondition. Thus, these methods cannot deal with heterogeneous data from many sources simultaneously, e.g., data from a linked open data web crawl. To this end we propose Holistic Concept Matching (HCM). HCM aligns thousands of concepts from hundreds of ontologies (from many sources) simultaneously, while maintaining scalability and leveraging the global view on the entire data cloud. We evaluated our approach against the OAEI ontology alignment benchmark as well as on the 2011 Billion Triple Challenge data and present high precision results created in a scalable manner.
In 2006 Berners-Lee proposed the Linked Open Data (LOD) design principles1. These principles outline the vision of a global data cloud that can be used to build novel applications incorporating information about real-world entities from many sources. He suggests dereferencable HTTP URIs for naming things that return useful information when looked up on the web. Further, he encourages links to other URIs so that one can discover more information about things under consideration. The semantic web community adopted these suggestions and we are now witnessing the growth of a giant global data cloud comprising information form many sources using de-facto standards such as RDF, RDFS, OWL, etc. The pure availability of this data following a set of principles is a big win since, in general, the use of (nonlinked) open data requires source-speci c approaches to access, query and lter the data of interest. Instead, when published as LOD, one can leverage di erent sources through common mechanisms such as HTTP and SPARQL. Exam1http://www.w3.org/DesignIssues/LinkedData.html ples of such LOD applications are showcased on data.gov and data.gov.uk.
However, the LOD vision includes the connection of data
from di erent sources via links to facilitate an easy
integration. As of September 2011, the LOD cloud comprised 295
sources, which all ful ll the basic LOD principles2. In
contrast, the number and quality of links across these sources
are an ongoing issue since their discovery is a major
challenge [
State-of-the-art ontology matching has been designed to
cope with nicely structured and well de ned ontologies in
order to produce high-quality mappings for one pair of sources
from one speci c domain at a time. Instead, in the case of
data that stems from the web, we need approaches that can
(simultaneously) deal with heterogeneous and incomplete
vocabulary de nitions from many di erent sources dealing
with various topics. Further, the vocabularies from the LOD
cloud as a whole allow a holistic view on the web of
vocabulary terms and thus to create alignments depending on other
alignments and dependencies. Resulting alignment
information across many sources can be used for web query
answering or the discovery of sources with respect to speci c topics.
However, it is a major scalability challenge to deal with very
many vocabulary terms gathered from the linked data web.
Therefore, we tackle one the major challenges in ontology
matching, namely the matching at a very large scale [
In the following section we brie y review state-of-the-art techniques for aligning ontologies and then derive requirements for an approach the deals with heterogeneous vocabulary de nitions from the web of data (Sec. 1.1). Next, we outline our general approach for aligning multiple LOD vocabularies (Sec. 1.2), followed by a technical description of respective alignment phases (Sec. 2{4). Along with the technical details of our approach we present measurements to convince the reader of the respective phase's scalability. 2http://www4.wiwiss.fu-berlin.de/lodcloud/state/ 1.1
The matching of data models is an essential task for
various areas in the information science, e.g., information
integration, peer-to-peer data management, Web service
composition, etc. [
Nevertheless, the number of ontology matching
approaches dedicated to ontologies from the LOD domain has
grown recently. Those LOD approaches commonly use only
one (or few) basic matching techniques. Often, these
techniques utilize special RDF and LOD characteristics to
improve the matching result. For instance, Nikolov et al.
introduce an approach that utilizes owl:sameAs links between
data sets in the LOD cloud to derive concept overlaps [
However, there are hundreds of ontologies in the Web of
Data, which have been created for di erent use cases but
still contain many overlaps worth discovering. Therefore,
the ability to perform cross-domain matching is especially
important. Jain et al. introduced an approach that utilizes
Wikipedia categories for bootstrapping. This way, they can
cover knowledge from various domains [
Recently, Rahm surveyed di erent approaches to
largescale matching tasks [
The input for web-scale ontology alignments is a set C of concepts that has been gathered from the LOD cloud via web access methods. The concepts in C stem from many di erent ontologies. For each concept in C, there is at least a URI { its id. Preferably, there are further information, such as a label, a description, or a comment. Additionally, there can be further meta data like structural information. For the processing of these large amounts of heterogeneous ontological information we suggest the following properties for an alignment approach:
The approach must work with ontologies from diverse domains, i.e, the underlying concept matching strategy must be applicable to many domains.
Due to a large input concept set, the approach must perform automatic alignment in sub-quadratic runtime (in the number of concepts).
The approach should process concept de nitions only. That is, it can neglect instance data due to its immense size. Further, property de nitions can be ignored since we found that property de nitions and their actual usage di ers largely.
Ontology structures should not be used for the actual alignment creation (if available at all). This is for scalability reasons and since the structure across diverse ontology varies largely and is thus not bene cial. However, the approach can exploit structural information, such as subclass relationships, to verify derived alignments and nd semantic contradictions.
The approach must return equivalence relationships for vocabulary terms. These relationships can be fuzzy (depending on some parameter) since di erent ontologies have di erent granularities, e.g., umbel:SpacePlatform Manned dbpedia:SpaceStation. Please note that others might make other design decisions; however, due to the immense scale and a questionable quality of current general web data we follow these properties. 1.2
The aforementioned properties shall hold for an approach that can be applied to web-scale input data. However, at the same time we target an holistic view on the data to leverage the information at hand as a whole. Therefore, we propose the Holistic Concept Matching approach (HCM). To address the scalability challenge we group the input data by topic and thus create small groups of concepts that can be aligned locally. Since we group by topics, we can still infer relationships holistically, i.e., draw conclusions not only based on a pairwise similarity but additionally based on alignments and dependencies among other topically related members of the same group.
Consider for instance ve sources (A; B; C; D; E) and
let fa1; : : : ; am; b1; : : : ; bn; c1; : : : ; co; d1; : : : ; dp; e1; : : : ; eqg
be the concepts from these sources. Running a traditional
approach on all available pairs of ontologies would result in
up to 52 isolated runs, which is computationally infeasible
given that alignment approaches often base on complex
lexical and structural properties [
With the help of additional topic knowledge for the sources and their entities we are able to group them. For instance, given that the three sources (A; B; C) store media related entities and (D; E) provide information from the life sciences, we examine groups of concepts, e.g., fa1; : : : ; am; b1; : : : ; bn; c1; : : : ; cog and fd1; : : : ; dp; e1; : : : ; eqg { yielding fewer runs of the approach. Note that these groups must not directly relate to the input ontologies: For instance, if d1 = human, then it could also reside in the rst group. However, within these groups, we can then run computationally more complex approaches to take an holistic view based on multiple ontologies.
Speci cally, our general approach is shown in Fig. 1. Given the data from the LOD cloud, we extract a knowledge representation for all available concepts. This representation can be a simple descriptive string, a feature vector, or a more complex data structure. Next, we apply topical grouping in order to create smaller sets of concepts. Within knowledge extraction grouping alignment generation these sets, we then create alignments by identifying similar knowledge representations and reasoning among them using additional structural information from the input as well as further candidates from the same group.
Obviously, many techniques can be plugged into this
approach. Depending on the knowledge representation, one
can choose the speci c representation of a concept's topic,
speci c topic similarities as well as speci c concept
similarities in order to nd alignments. In the remainder of this
paper, we report on the adoption of the Wikipedia
category forest [
The comparison of di erent concepts requires an abstract representation of its semantic content, i.e., a knowledge representation. First we present our method to compute this representation, then we show our performance results. 2.1
Given a set C of concepts from many di erent ontologies
gathered from the LOD cloud, we now elaborate on the data
structure we use to represent a concept. To this end, we
chose Wikipedia Category Forests (WCF) as proposed for
the BLOOMS algorithm in [
f 1; : : : ; qg. (b) In recursion 2 f 1; : : : ; rg.
h determine p's categories h determine 's super-categories (c) In recursion 3
f 1; : : : ; sg. (d) etc.
h determine 's super-categories We now explain the three steps on more detail.
Step 1. To determine keywords kw(c) for a concept c we have tested several methods. In the following, we use two orthogonal base methods, namely the TFIDFn-extraktor and ConceptID -extraktor. The TFIDFn-extractor processes descriptions of concepts, i.e., comments and labels. For this, we merge description texts and tokenize them and neglect stop words3. Then, we determine the tf-idf-score for each token with respect to the overall corpus of concept descriptions. Finally, we select the top-n tf-idf-ranked tokens as keywords kw(c).
The ConceptID -extractor is solely based on the concept's URI. The concept id is the unique identi er of a concept in its ontology de nition. HCM uses a straight-forward approach to determine the concept id: We truncate the pre x of the URI until the last occurrence of either #, :, or /. The concept id must not contain any other character than letters or underscores. To extract tokens, we split the concept id at camel-case characters and underscores. After again removing stop words, this results in the set of keywords kw(c). For instance, the concept id for http://umbel.org/umbel/rc/ SpacePlatform_Manned would be SpacePlatform Manned . From this we create kw(c) = fspace; platf orm; mannedg.
Additionally, HCM supports the ConceptID TFIDFnextractor that combines both methods. First, ConceptID keywords are extracted. If no WCF can be constructed (see next steps) HCM tries to build a forest using TFIDFn keywords instead. Thus, the ConceptID TFIDFn-extractor maximizes the amount of concepts that can be represented by an WCF.
Step 2. Next, HCM performs a Wikipedia full-text search using a search query that is built by concatenating all keywords kw(c) (delimited by spaces). From the resulting Wikipedia pages we choose the top d pages as tree root for the creation of a WCF. The parameter d { the forest depth { in uences a WCF's coverage of conceptual meanings. To catch all potential meanings of a concept, several Wikipedia articles and their category hierarchies have to be considered, i.e., it requires a deep forest. On the other hand, a deeper forest has a higher risk to contain trees not related to the actual concept. Therefore, the selection of the forest depth parameter is a trade-o between semantic coverage and irrelevance.
Step 3. The tree construction builds trees recursively from the root to the maximal tree height h. The height mainly in uences the level of abstractness of a WCF. The higher the trees, the more category hierarchy layers are considered. This thus leads to more abstract categories in the WCF. Instead, the lower the trees, the less probable is a topical overlap among related concepts. We will discuss di erent parameter con guration in the experiments section.
For instance given resource umbel:MannedSpacecraft, the ConceptID-extractor yields fmanned; spacecraf tg, which 3using the English stop word lists of Apache Lucene (v2.3.0) and of the MediaWiki-plugin LuceneSearch (v2.1.3) with 33 respectively 121 words 2nd layer spaceflight 1st layer root node aerospace engin. vehicles by media space tech. pneuma#cs struct. engin. gas tech. aerospace engin. spaceflight
hydraulics pressure containers astronau#cs spacecra7
pressure vessels results in the following Wikipedia search result (d = 3): fHuman spacef light; Spacecraf t; Orion (spacecraf t)g. Figure 2 depicts the tree for the root article Spacecraf t (h = 2). As one can see, the higher the layer, the more nodes (Wikipedia categories) exist and the more abstract are these categories. Furthermore, we note that di erent tree nodes occur multiple times, e.g., \space ight" or \aerospace engineering". These nodes play an essential role in the next phase of HCM (Sec. 3). 2.2
Setup. All experiments were performed on a Windows 2008 R2 Enterprise Server with two quad-core Intel Xeon processors (2.66 GHz) and 30GB of memory. To evaluate the performance of our approach in a web scale scenario, we used the 2011 Billion Triple Challenge (BTC) data4. The BTC data is a crawl from the LOD cloud and consists of approximately 2:2 billion triples. We have implemented all described methods in Java.
The extraction of concept information can be done in linear time with Hdrs { a scalable distributed RDF store5 { that allows fast in-order index scans. HCM selects concepts by considering resources occurring in triples with different predicates: rdf:type, rdfs:subClassOf , rdfs:domain, rdfs:range, owl:equivalentClass, owl:disjointWith, rdfs:label , and rdfs:comment . In this manner HCM identi ed approx. 1M concepts in the BTC.
In contrast to the original BLOOMS algorithm [
As expected, the Wikipedia index query time (Step 2) is linear to the number of extracted keyword sets. For instance, given 293k keyword sets from the ConceptID TFIDF3extractor, querying took 64 minutes.
The input to the keyword set extractors comprises 1M concepts. However, the ConceptID-extractor cannot yield a result for all input concepts, since we do not deal with blank nodes10 and malformed URIs. Further, not all keyword sets created yield a query result; in the end 238k keyword sets could be used to build WCFs. Nevertheless, when additionally applying the TFIDF3-extractor we can further create another 55k WCFs.
The forest construction runtime mainly depends on forest depth d and tree height h. Table 1 shows runtimes for the forest construction algorithm with di erent parameters. Apparently, the runtime linearly depends on the forest depth d. An increase of the tree height h leads to an exponential runtime increase.
The previous step extracts WCFs, i.e., our knowledge representation of choice. Given these knowledge representations, we now need to nd topically related concepts in order to group them. Note that in the following we use the terms domain and topic interchangeably. A domain or topic is a eld of the real world where di erent concepts together play a role. The underlying intuition for the following is that a search for alignments among concepts within (and not across) topics should not cause a major loss of recall. Again, we rst present our method, followed by an evaluation. 3.1
In our approach, the grouping (by topic) shall reduce the runtime complexity of the alignment generation step by splitting the problem space into smaller independent tasks (Sec. 4). This procedure is often referred to as blocking or partitioning.
Next, we discuss the details of nding topically related WCFs from the previous step. Given a set F of WCFs, we need to identify disjoint groups G1; : : : ; Gn F of topically 10Approx. 50% of all input concept IDs are blank nodes related forests (topic group). In HCM we implemented the following procedure: 1. For each WCF f 2 F , extract topic(f ) = ft1; : : : ; tmg from f . We describe a topic of a WCF using a set of tree nodes extracted from the WCF. 2. Given a topic topic(f1), identify all forests f2 2 F with a high topical overlap (topic(f1) ' topic(f2)). 3. Given a set of pairs (f1; f2) with a high topical overlap, determine groups G of forests by associating topically overlapping forests transitively.
Step 1. The topic topic(f ) of a WCF f is a subset of its tree nodes (fp; 1; : : : ; q; 1; : : : ; r; : : : g). In the process of nding characteristic nodes that represent this concept's topic, we ignore very speci c categories like \Soviet manned space program" and very generic categories like \Humans" or \Wikipedia article lists". In this paper we report on a simple yet promising approach we have tested (among others) for the topic extraction: The TFIDFForestn-extractor again utilizes the tf-idf measure. Nodes common in a WCF are scored with a high term-frequency-value (tf), whereas nodes popular in many WCFs are scored with a low inverse-documentfrequency-value (idf). We rank a WCF's tree nodes in descending tf-idf order and select the top-n for representing the topic. The choice of n is crucial for the quality of the tree node set representing the concepts's topics. Experiments indicated n = 10 to be a reasonable choice. Higher values lead to very speci c topics, whereas smaller n lead to a low representativity.
Step 2. Next, we compare the topic sets to identify related
forests. We use the Jaccard coe cient J and a
corresponding threshold J to determine the similarity of topic sets
(J (topic(f1); topic(f2)) J ). The nave pairwise
comparison of all forest topic sets leads to a quadratic runtime
behavior with respect to the number of forests jF j. To
reduce this e ort we tested di erent set-based similarity self
join techniques and selected ppjoin [
Figure 3 depicts the WCF group distribution in the BTC data over the similarity threshold J . For one, we illustrate 11https://code.google.com/p/similarity-join-tools/ 300 )s d an250 s u o h t i(n200 s p u rgo150 n i tss reo100 ff o r eb 50 m u n 0 >100k ≤100k the number of forests that can be grouped for a given J (green graph, left axis). Shaded areas below the green graph depict the number of forests in groups of a given size, e.g., size = 2, size 5, size 25, etc. Also, we show the total number of groups over J (dashed red graph, right axis).
As for the fraction of WCFs that can be grouped, a higher J leads to a decrease since the higher J , the fewer WCF pairs have a su cient overlap to be grouped. The shaded areas further show that the higher J , the more WCFs fall in small groups, since a stricter overlap criterion induces more individual groups. Vice versa, a lower J results in larger groups since smaller groups are merged in this case.
As for the total number of groups for a speci c Jaccard threshold, there is a clear increase for higher J . This is due to the fact that there are more smaller groups for higher J . The gure shows that J = 1:0 leads to 138k (out of 293k) forests have at least one correspondence with an identical topic set. The majority (92k) appears in groups of size two.
For the following experiments we set J = 0:7 as default for three reasons: (1) This avoids very large WCF groups which would raise the runtime of the alignment generation phase. With J = 0:7, the maximal group size of 4k leads to a reasonable (and feasible) runtime. (2) J = 0:7 provides a signi cant topical overlap among forests and minimizes haphazard correspondences. (3) This threshold value enables the identi cation of groups for more than 55% of the available WCFs (162k). Remaining WCFs do not have a su cient topic overlap and can thus not be considered for the alignment generation.
In general, the runtime of the candidate group generation
depends on the number of input WCFs, the applied
selfjoin technique, and topic set homogeneity (within the input
set). Figure 4 compares the runtime of three di erent set
similarity join techniques with groups for TFIDFForest10
topics, J = 0:7, and varying number of WCFs. The red
graph (triangle markers) shows the quadratic runtime of the
nave baseline approach that compares all forests in a
pairnaive
mpjoin
ppjoin
0
50
100 150 200
forest set size (in thousands)
250
300
wise manner. The yellow line (rhomb markers) indicates
the performance of the mpjoin introduced by Ribeiro and
Harder [
Given the set of candidate groups the next task is to regard each group and nd alignments among their respective members independently. This leads to runtime reduction decreased due to the reduced input set size (jGj jF j) and the possible parallelization of alignment generation task for di erent groups In the following, we elaborate on our underlying matching strategy to identify relations among concepts, followed by an experimental evaluation. 4.1
Given a set G of topically related WCFs, we need to identify a set of alignments A. We propose a procedure that, again, consists of three steps: 1. Extend G by adding related WCFs. These relations originate from the original ontology de nitions. 2. Compare all forest pairs f1; f2 2 G using a forest overlap score function O. Extract all forest pairs with an overlap value exceeding a given threshold O(f1; f2)
O; add them to match candidate set M . 3. Create an alignment graph D by iteratively adding candidate matches M that neither semantically conict with ontology de nitions, nor with other candidate alignments. Finally, extract alignments A from the con ict-free alignment graph D.
Step 1. First, we extend each topic group G with further related WCFs in order to incorporate immutable axioms from the underlying ontologies. Speci cally, related WCFs f2 have an ontology-level relation in common with a WCF f1 2 G, i.e., owl:equivalentClass and owl:disjointWith relationships. We did not select other relations since we deem these two as most relevant to reveal semantic con icts of alignments while keeping the group size low (which is a desirable property). In the following, the topic group G refers to the extended topic group.
Step 2. Next, we compare all pairs of WCFs f1; f2 2 G
to determine the overlap of the forests. HCM uses the
tree overlap similarity of BLOOMS+ to compare
individual trees [
Overlap(t1; t2) = log Pn2(t1\t2) 1 + ed(n;t1) 1 1 log 2jt1j Thus, the tree overlap depends on the distance d of common nodes n 2 (t1\t2) to the root of t. The higher the node depth in t (d(n; t)), i.e., the more nodes are between n and the root page p of t, the smaller the in uence of the shared node. The depth of the root page is set to d(p; t) = 1. For instance, given the tree t1 with the root p = \spacecraft" (article) of our previous example (see Fig. 2) and an arbitrary tree t2. Assuming two overlapping nodes x = \astronautics" and y = \aerospace engin." between t1 and t2 such that t1 \ t2 = fx; yg, the resulting depths of the nodes in t are d(x; t) = 1 and d(y; t) = 2. Therefore, the resulting tree overlap of both trees in t1 is:
Overlap(t1; t2) = log
1 1 + e0 + 1 + e 2 log(2 14) 0:385 The tree overlap is not symmetric (Overlap(t1; t2) 6= Overlap(t2; t1)). With this asymmetry BLOOMS+ is able to identify parent-child relationships between concepts. The equivalence between concepts is derived if Overlap(t1; t2) = Overlap(t2; t1). However, we are interested in a similarity value for two WCFs instead of individual trees. Therefore, we compare all pairs of trees of di erent WCFs and select the best matching tree pair. Given two WCFs f1 and f2 (f1; f2 2 G; f1 6= f2), we de ne the forest similarity as the maximal harmonic mean for the overlaps of all tree pairs (8t1 2 f1; t2 2 f2): O (f1; f2) = arg max t12f1; t22f2 2Overlap(t1; t2)Overlap(t2; t1)
Overlap(t1; t2) + Overlap(t2; t1)
Then, we select relevant matches M by using an overlap threshold O(f1; f2) O. The selection of a good threshold is essential for the alignment quality, because a low O-value leads to a high amount of irrelevant candidates and thus a lower precision. The following semantic deduction might not be able to eliminate erroneous candidates. In addition, the run-time complexity in the semantic veri cation phase grows. A high O-value instead leads to fewer candidates and thus a low recall. In Sec. 4.2 we evaluate the di erent thresholds and their in uence on the alignment quality. Step 3. Next, HCM performs a logical reasoning to remove con icting matches from candidate sets and thus enhance the precision. HCM draws conclusions for matches contradicting each other. This is done using the holistic knowledge of all ontologies. Given a ranked set of forest match candidates M , the semantic veri cation will produce an alignment graph D = (G; E) with a set of WCF nodes G and a set of directed edges E G G representing the veri ed alignments. The edges are annotated with three di erent attributes: The certainty of an alignment cert : G G ! R01 speci es the con dence of a matching. The higher the value, the more reliable the match.
The alignment type classi es every matching pair in one of ve categories type : G G ! fequi , disj , parent , child , ontog. An equi edge connects two concepts identi ed to be equal, whereas a disj edge marks two concepts to be disjoint. A parent or child edge is a directed subset information representing an rdfs:subClassOf relationship. An onto labeled edge marks two concepts to originate from the same source ontology.
The alignment origin provides information about the edge's origin, origin : G G ! fdef , detect , infer g. A def edge is an axiom stated in the source ontology. A detect alignment pair is a veri ed concept alignment pair, i.e., O(f1; f2) O. An infer edge is a inference drawn from other matches with the help of transitive closures.
To populate the graph D, HCM performs the following: (a) Initialize the alignment graph D with no edges (E = ;). (b) Populate D with ontology constraint edges a (cert(a) = 1:0 and origin(a) = def ) derived from rdfs:subClassOf , owl:equivalentClass, and owl:disjointWith triples from the underlying RDF data. (c) Add relations a between WCFs originating from the same ontology with type(a) = onto, cert(a) = 1:0, and origin(a) = def . Here, we use the ontology id from a concept URI by removing the ConceptID (see Sec. 2, Step 1). (d) Finally, match candidates M (Step 2) are selected greedily: We add matches a = (f1; f2) from M with decreasing similarity O(f1; f2) to E. New edges in E comprise cert(a) = O(f1; f2), type(a) = equi , and origin(a) = infer as annotations.
When inserting an alignment { ontology constraints or candidate alignments (Step 2) { we perform three steps:
First, we check whether an alignment a contradicts the existing edges in D. To this end, HCM checks for four di erent types of contradictions: Con icting de nitions are alignments in the graph that are incompatible to an new alignment a = (f1; f2). A con icting de nition occurs, if there is an edge ex = (f1; f2); ex 2 E such that type(ex) 6= type(a), origin(ex) 6= infer , or cert(ex) cert(a). Furthermore,
equivalence af1 x ex ax' fx2 f3 x (b) x x disjointness iFnifgeequurivarleaencec5lx:odissjoFiuntnrieevseqsxueivaaplae0trnecynfetsrphioxpdeimssjointonaeesfqsxunivaaeplalewrniecngetshnaixpdmlisijogienntnneemstqsxuiveaiplannernecftneteshairxpdeisajnoinnctndeeesqssxuia,vapnlaetrnecnheetshaxixpdt-isjointnessx parents isting edge ex in the matching graph. (a) shows an eaqnudiv(acl)enshceowclodsff3i1usjroei nf2ftorcltoyspff31uer(eexsf)2f=ortytpyff31ep(ea()exf2=); etyqupeiff31(.a()b2)f2 ff31 fequi ; disj g; type(ex) 6= type(a). (d) and (e) show parentship and childship closures for type(ex); type(a) 2 fparent ; child g; type(ex) = type(a).
HCM checks alignments for multiple-entity
correspondences, crisscross correspondences, and
disjointnesssubsumption contradictions. These three types of
contradictions were originally introduced for the ASMOV
ontology alignment approach by Jean-Mary et al. [
If and only if no contradiction was found for the candidate alignment a, HCM adds the alignment candidate and its inverse a 1 to the graph's edge set E. The inverse alignment a 1 = (f2; f1) of a = (f1; f2) has got an analog alignment identi cation (origin(a 1) = origin(a)) and certainty (cert(a 1) = cert(a)) and the inverse adapted type (type(a 1) = type 1(a)):
8 equi if type(x) = equi type 1(x) = <>>> pdaisrjent iiff ttyyppee((xx)) == cdhisijld >> child if type(x) = parent >: onto if type(x) = onto
Second, HCM infers further alignments from a (a 1 respectively) by drawing conclusions with the help of existing alignments e 2 E. HCM supports ve types of inference types shown in Figure 5: Given an existing alignments (er=esp(fec1t;ifv2e)lye a2 E1 =an(df2th;fe3a))li,ganmcleonsturjuesat0a=dd(efd1;af=3) (cfa2n; fb3e) drawn.
Third, given the veri ed alignment graphs, HCM outputs all edges e 2 E with origin(e) = detect as alignment set A.
For instance, given a WCF group G = fdbpedia:SpaceStation; umbel:SpacePlatform Manned ; dbpedia:Spacecraft g the population of graph D works as follows: The only ontology constraint for G is the alignment aonto = (dbpedia:Spacecraft ; dbpedia:SpaceStation), with cert(aonto) = 1, origin(aonto) = def, and type(aonto) = onto in order to indicate that both concepts to originate from the same ontology. Both alignments aonto and the inverse aon1to are added to D. Afterwards the candidate set G = fa1; a2; a3g is processed. Assuming alignment certainties of: a1 = (dbpedia:SpaceStation; umbel:SpacePlatform Manned ) cert(a1) = 0:955, a2 = (dbpedia:Spacecraft ; dbpedia:SpaceStation) cert(a2) = 0:718, and a3 = (dbpedia:Spacecraft ; umbel:SpacePlatform Manned ) cert(a3) = 0:341 HCM proceeds as follows: First a1 is added to D with origin(a1) = detect and type(a1) = equi (and so a1 1). Afterwards, a2 is not added, due to the con icting de nition aonto, which marks both concepts to originate from the same ontology. Finally, due to a multiple-entity correspondence a3 is prevented too: umbel:SpacePlatform Manned is already matched to a concept from the dbpedia-ontology. 4.2
In the following section, we discuss the experimental
results of HCM for the BTC data as well as on the Ontology
Alignment Evaluation Initiative benchmark track [
Table 2 shows our manual evaluation results as well as their con dence intervals (con dence level of 95%). Additionally, it depicts absolute numbers of alignments found in the BTC data for varying thresholds. In the case of 1 > simforest 0:95, 57.5% of the alignments were labeled as equivalences and 15% as similar. The number of actual equivalences decreases for smaller forest similarities. When considering only the strict equivalence judgments as relevant alignment, the inter-annotator agreement for strict equivalences is very high = 0:909 (Cohen's kappa coefcient). By treating more fuzzy results (similar or equal alignments) as correct, the inter-annotator agreement decreases to = 0:817. This is due to a varying perception of a similarity or relatedness. It is much more subjective than a strict equivalence de nition. For instance, the concepts daml:Ammeters and umbel:Voltmeter are related due to their common purpose. On the other hand, from a taxonomic point of view, the instance sets of both concepts are probably disjoint. HCM discovered interesting matches such as: yago:PsychoactiveFungi and umbel:HallucinogenicMushroom dbpedia:BirdsOfAustralia and opencyc:Parrot umbel:AirConditioner and dbpedia:HeatExchangers Note that, due to diverse and non-trivial domains in the BTC corpus, these kind of matches are hard to identify, even for humans. Our algorithm can deal with these cases because it exploits broad knowledge for many domains present in Wikipedia.
Furthermore, it is interesting to see that even in case of false positives, the algorithm reveals interesting semantic relations between concepts. For instance, HCM aligns the concepts yago:Outlaws and umbel:MotorcycleClub due to a 1500 2000 2500 number of forests per group runtime Poly. (runtime) semantic relation via outlaw motorcycle clubs similar to Rivals Hells Angels and Bandidos.
Runtimes of the alignment generation phase is visualized in Figure 6 for di erent WCF groups (orange rhomb marker). Due to the pairwise comparison of trees of all WCFs in a group G to generate candidate alignments (see Step 2), the alignment generation phase has a quadratic runtime in the group size jGj. Furthermore, the e ort alignment veri cation is polynomial to the amount of alignment candidates. The blue dotted line indicates the polynomial regression of the forest match execution times. The amount of small groups is very high (see Figure 3), which is no problem, because of small run-times. A remaining issue is the large e ort of the matching step for large groups which is left for future work.
OAEI. In order to compare with other ontology alignment
approaches (e.g. [
In 2011 a new bibliographic benchmark data set was
generated [
In this paper, we tackle the problem of large-scale
concept matching { one of the major challenges in ontology
matching [
We have many ideas for future directions: For instance, we will look into other knowledge representations and matching techniques that can be plugged into the work ow. The chal12http://dbpedia.org/ 13http://www.mpi-inf.mpg.de/yago-naga/yago/ lenge here, is to identify approaches that can capture di erent semantic notions of an input concept and allow a useful grouping. Also, we plan to derive further relationship types - maybe with the help of instance data instead of Wikipedia categories. Last, we plan to experiment with other topical groupings that, e.g., allow overlaps across groups. Another grouping method could also support incremental updates and thus facilitate online ontology alignments for the growing web of linked data.