It is evident from the recent growth in Geospatial Linked Data that even though the number of instances being generated and linked has increased drastically, the ontologies behind these sources remain disconnected. Though we can agree that the instances being linked are equivalent, the alignments that are extrapolated from these links between the concepts may or may not agree with our intuitions. It is important to investigate how the concepts in the sources are actually aligned. Our previous work was successful in nding alignments, such as equivalence and subset relations, between concepts of two sources, using the instances that are linked as equal. Such alignments need not be trivial, however, as a concept in the ontology might not have an exact equivalent class in the other source. In this paper we propose a method that uses the subset and equivalence relations between restriction classes found by our previous work to nd new alignments, where one (larger) concept of a source is aligned to the union of multiple (smaller) concepts from another source. We also show that we can use these alignments to nd inconsistencies and use them to identify the instances that may be erroneously aligned.
The Web of Linked Data has seen huge growth in the past few years. As of
September 2010, the size of the Linked Open Data Cloud was about 28.5 billion
triples with around 20.6% of the triples belonging to the geospatial domain.1 As
of June 2009, the cloud had recorded an overall growth of about 300% with 91%
growth in the geospatial domain.2 Out of the 16 geospatial data sources covered
in the September 2010 count, there are around 16.5 million outgoing links to
other sources. The sources of Geospatial Linked Data are most popularly
connected using the owl:sameAs property, linking instances that are the same. As
more alignments are generated in the Web of Linked Data at the instance level,
a pattern of inter-linked data arises where the ontologies behind the sources
1 http://www4.wiwiss.fu-berlin.de/lodcloud/state/
2 http://events.linkeddata.org/ldow2011/slides/ldow2011-slides-intro.pdf
remain un-linked. As described in our previous papers on Linking and
Building Ontologies of Linked Data [
Reviewing these subset relations we discovered that there are potential
equivalent alignments not found by our previous work, linking a larger concept to a
union or aggregation of one or more of its subsets. Using this as motivation,
the work described in this paper builds on the ontology alignment method of
[
The scope of this paper is in the domain of Geospatial Linked Data, where
we nd alignments between three sources: GeoNames, DBpedia and
LinkedGeoData. We rst nd equivalences and subset relations as described in our previous
work, and then use these to nd the new union alignments. The nature of each of
the three sources investigated is brie y mentioned here and they are described in
more detail in [
This paper is organized as follows. We rst describe brie y our alignment
algorithm from [
Aligning geospatial ontologies on the Web of Linked
Data The work described in this paper follows our previous work on aligning ontologies of Linked Open Data, which uses an extensional approach to nd alignments between restriction classes in two di erent sources. Though the results generated by our previous algorithm found equivalent alignments between the two sources, a large number of subset alignments were also found. A pattern was observed in these results, where a group of concepts from one source were subsets of the same larger concept from the other source. In many cases these smaller concepts taken together were able to completely explain the larger source. We used this insight as motivation for consuming the subset relations, which were too numerous to be useful by themselves, to nd alignments between the larger concept and the union of the group of concepts. Our approach uses this group of smaller concepts and introduces a disjunction operator on these subsets to try to de ne the common subsuming concept. 2.1
Our previous work on linking and building ontologies of Linked
Data Ontologies of Linked Data sources can be quite rudimentary. For example, GeoNames only has a single concept (Feature) to which all of its instances belong. On the other hand, in DBpedia, we nd a rich ontology with a hierarchy of concepts and well-de ned properties. In the traditional sense of ontology alignment, we would have found at most a single alignment between Feature on the GeoNames side and a similar broad concept from DBpedia. In order to get a richer set of alignments, we introduced the concept of a restriction class. A restriction class is a concept that is derived extensionally and de ned by the set of instances obtained by restricting a single property to a single value (called a property-value pair and represented by (pi = vi)) in a source. For example, a restriction class for schools can be constructed in GeoNames by forming a set of instances that have their geonames:featureCode restricted to `S.SCH '. This restriction class is represented as geonames:featureCode=S.SCH. The scope of the de nition of a restriction class includes the conjunction operator, which produces a more specialized set of instances, constructed using two or more restriction classes. Thus, a restriction class fgeonames:featureCode=S.SCH & geonames:countryCode=USg, built from the restriction classes geonames:featureCode=S.SCH and geonames:countryCode=US, can be de ned by the intersection of the two sets and forms a concept extensionally described by the set of schools in the US in GeoNames.
Our algorithm aligns restriction classes from two sources, using an extensional technique, as follows. A pre-processing step rst performs an inner-join on the two sources to be aligned based on an instance equivalence property like owl:sameAs. As inverse functional properties can only result in restriction classes with a single instance belonging to it, the pre-processing step eliminates them. The crux of the algorithm uses a top-down tree exploration of the space of alignment hypotheses. At the topmost level, a seed hypothesis is generated by aligning a restriction class with one property-value pair from the rst source with another restriction class with one property-value pair from the second source. At each level in the search space, a new restriction class is formed from one restriction class of one of the sources by adding another property-value pair constraint on that restriction class. A new alignment hypothesis is thus constructed from the new restriction class and the restriction class from the other source. Each alignment hypothesis is tested for set containment relations between the intersection set of the restriction classes from both sources. This is done with the help of two scoring functions - P & R. If r1 and r2 are the two restriction classes in the alignment hypothesis, we rst de ne Img(r1) as the set of instances in the second source that instances of r1 are linked to. We then de ne P as jImg(r1)\r2j , and R as jImg(r1)\r2j . We mark the relation of the jr2j jImg(r1)j alignment hypothesis as either i) equivalent (P = 1; R = 1), ii) subset, with the restriction class from the rst source as extensionally subsuming the restriction class from second source (R = 1), iii) subset, with restriction class from second source extensionally subsuming the restriction class from rst source (P = 1) or iv) no relation between the two restriction classes. To compensate for missing and misaligned instances, we relax our subset scores by de ning P 0 and R0 that reduce the required fraction of support to be greater than 0.9 instead of equal to 1. For an optimal exploration of the search tree, we employ certain pruning mechanisms that include i) using ordered exploration to avoid exploring a node twice, ii) pruning a node if the intersection set of the restriction classes of the hypothesis has size less than a minimum support size (we used 10 in our experiements), iii) pruning a node if the added restriction class does not change the set of instances, etc. After the brute-force exploration of the search space of alignment hypotheses, we use a post-processing step on the results generated, which removes redundant assertions by virtue of set containment of instances of two hypotheses where one is the immediate parent of the other in the search tree.
At the end of the above three steps of processing, the algorithm was able
to nd equivalent relations between restriction classes from two sources as well
as subset relations in either direction. As this algorithm was not speci c to
any particular domain, we explored candidate sources for alignments in three
domains: Geospatial, Genetics and Zoology. In these three domains, our
algorithm found alignments of 5 pairs of sources. For example, we were able to nd
alignments between GeoNames and DBpedia in the Geospatial domain. One such
alignment was the equivalent relation between fgeonames:countryCode=ESg and
fdbpedia:country=Spaing (i.e. correctly aligning the concepts for the country
Spain). We also found subset relations like fgeonames:featureCode=S.SCHg
subset of rdf:type=dbpedia:EducationalInstitution. More such results are described
in [
Identifying spatial concept coverings As explained above, we were able to identify a pattern where a group of restriction classes from one source were aligned as subsets of a common concept from the other source. By using these alignments as hints, we were able to construct the union of the smaller restriction classes and detect if the union was able to de ne the larger class entirely. The following section describes this method in detail. In those cases where we are not able to de ne the larger class entirely, our approach is also able to nd and explain the missing instances (outliers ). Mapping a restriction class from one source with a union of smaller restriction classes from the other source Since the problem of nding alignments with conjunctions and disjunctions of property-value pairs of restriction classes is combinatorial in nature, we focus only on subset relations where both restriction classes have a single property-value pair and where one is a subset of the other. This helps us nd the simplest de nitions of concepts and also makes the problem tractable. Alignments generated by our previous work that satisfy the single property-value pair constraint are rst grouped according to the subsuming restriction classes. We then identify a strategy for selecting the smaller restriction classes from within such a group to form the union that best describes the larger restriction class. Since restriction classes are constructed by forming a set of instances that have one of the properties restricted to a single value, aggregating restriction classes from the group according to their properties builds a more intuitive de nition of the union. We can now de ne the disjunction operator that constructs the union concept from the smaller restriction classes in these sub-groups. The disjunction operator is de ned for restriction classes, such that i) the concept formed by the disjunction of the restriction classes represents the union of their set of instances, ii) each of the restriction classes that are aggregated contain only a single property-value pair and iii) the property is the same for all those property-value pairs. We then try to nd the alignment between the larger common restriction class and a set of restriction classes from the other source that are aggregated by the disjunction operator by using an extensional approach similar to our previous paper. We call such an alignment as union alignment.
We rst build candidates for aggregation using the results from our previous algorithm as hints. We group alignments by the larger common restriction class. Grouping the subset relations is trivial. Equivalence relationships are subsets in both directions and thus are easily integrated into the groups. For each alignment, fp1=v1g is the r1 part and fp2=v2g forms the r2 part (each with a single property-value pair ) as explained in the previous section. Sub-groups are formed by aggregating according to the property of the property-value pairs of the smaller restriction classes. Such a sub-group is identi ed by fProperty of the larger restriction class(p1), Value of the larger restriction class(v1), property of the smaller restriction classes(p2)g. Values of the di erent smaller restriction classes can be denoted by a list List(v2s). The disjunction of the smaller restriction classes creates a set of instances that extensionally identi es the union concept. We can now either con rm or refute the hypothesis that the larger restriction class is equivalent to the union concept. We can do this by using a scoring mechanism similar to the use of P & R in our previous paper. Using the same terminology, UA is de ned as the set of disjunctive instances (i.e. Union(Img(r1) \ r2))), UL is de ned as the set of instances of the larger class taken by itself (i.e. Img(r1)) and US is de ned as the set of instances that is the union of individual smaller restriction classes (i.e. Union(r2)). The scoring mechanism de nes PU as UUAS and RU as UUAL . P U0 & RU0 are de ned as fractions with relaxed scoring assumptions similar to P 0 & R0 from our previous paper.
For example, our previous algorithm nds that fgeonames:featureCode = S.SCHg, fgeonames:featureCode = S.SCHCg, fgeonames:featureCode = S.UNIVg are subsets of frdf:type=dbpedia:EducationalInstitutiong. In this case, the subgroup can be identi ed as frdf:type, dbpedia:EducationalInstitution, geonames:featureCode g and list as (S.SCH, S.SCHC, S.UNIV). As can be seen in the Venn diagram of Figure 1, UL is the restriction classImg(frdf:type = dbpedia:EducationalInstitutiong), US is fgeonames:featureCode = S.SCHg [ fgeonames:featureCode = S.SCHCg [fgeonames:featureCode = S.UNIVg and UA is:
fImg(frdf:type = dbpedia:EducationalInstitutiong) \ fgeonames:featureCode = S.SCHgg [ fImg(frdf:type = dbpedia:EducationalInstitutiong) \ fgeonames:featureCode = S.SCHCgg [ fImg(frdf:type = dbpedia:EducationalInstitutiong) \ fgeonames:featureCode = S.UNIVgg
Ideally, for an exact equivalence alignment, P U0 & RU0 should both be 1.0, if the larger restriction class covers the union of the smaller restriction classes completely and vice-versa. However, similar to the relaxed score assumption from our previous paper to accommodate errors in the dataset, we consider it a complete coverage when the score is greater than a relaxed score of 0.9. (i.e. the union alignment is considered to be equivalent if P U0 > 0.9 & RU0 > 0.9). Due to the minimum support score constraint for subsets from our previous paper, we are assured that UUAS i.e. P U0 is always going to be greater than 0.9.4 Thus, we can say that a union alignment is equivalent if RU0 > 0.9. With the educational institutions example, RU0 for the alignment of dbpedia:EducationalInstitution to the union of S.SCH, S.SCHC & S.UNIV is 0.98. We can thus con rm the hypothesis and consider this union alignment equivalent. The scores for other union alignments found are described in the results section.
Key: S.SCH
Img(r1)
Union(r2)
Using mappings to identify outliers As mentioned above, the score for the alignment of frdf:type = dbpedia:EducationalInstitutiong to the union of fS.SCH, S.SCHC & S.UNIVg is approximately 0.98. For frdf:type = dbpedia:EducationalInstitutiong, 396 instances out of the 403 Educational Institutions were accounted for as having their geonames:featureCode as one of S.SCH, S.SCHC or S.UNIV to give this score. An interesting question to pose then is, how are the remaining 2% of the dbpedia:EducationalInstitution s (i.e. 7 instances) classi ed in GeoNames?
While calculating the disjuncted restriction classes, we also keep track of other instances with the same fp1; v1; p2g but not previously considered as subsets. These had been pruned in the exploration stage as they either had a size of less than the minimum support size constraint of ten instances or had P 0 less than 0.9. For the rst type of restriction classes, those with low support size but yet having P 0 greater than 0.9 are now re-classi ed as subsets. The 4 It should also be noted that each of the smaller subsets also satisfy the minimum support size of 10 instances. re-classi cation of the relation as a subset can now be justi ed due to increased evidence in suggesting subsumption as other values for the same property are also aligned as subsets of the larger restriction class from the rst source.
The second type of restriction classes that had P 0 less than 0.9 along with the ones that were not re-classi ed above (i.e. with less than 10 instances and P 0 less than 0.9) form the outliers. For example, as mentioned before, schools, colleges and universities from GeoNames make up 396 out of 404 Educational Institutions from DBpedia. From the other eight instances, 7 have their feature codes as either S.BLDG (3 buildings), S.EST (1 establishment), S.HSP (1 hospital), S.LIBR (1 library) or S.MUS (1 museum). The eighth instance does not have a geonames:featureCode property asserted. The P 0 score of these restriction classes is less than 0.9. One of the instances classi ed as dbpedia:EducationalInstitution in DBpedia is linked to an instance in GeoNames that has geonames:featureCode as `S.HSP'. 5 There are 31 instances in fgeonames:featureCode=S.HSPg, however, and because this restriction class does not meet the relaxed subset score threshold, it cannot be considered in the union of restriction classes. Another example of outliers was found in the fdbpedia:country = Spain geonames:countryCode = ESg alignment. This equality was found using the relaxed subset assumption, where 3917 of the 3918 instances of dbpedia:country=Spain were accounted for as having geonames:countryCode=ES, resulting in a subset score of 0.9997. The one instance not having country code ES was actually classi ed as having country code IT (Italy). This single instance needs to be inspected further and it needs to be determined if the owl:sameAs link is correct. It is evident from the above examples that the outliers help in understanding the nature of the sources more explicitly, showing why the alignments failed to completely describe the larger restriction class. These, along with a few other examples, are described in detail in the next section. 3
Experimental Results From the approach described in Section 2.2, we were able to get a total of 752 union alignments for the GeoNames -DBpedia alignment and 5843 for the LinkedGeoData-DBpedia alignment. From the 752 in GeoNames -DBpedia, 318 are such that the larger restriction class is from DBpedia, while the other 434 have the larger restriction class from GeoNames. Similarly, 3097 from the 5843 union alignments in LinkedGeoData-DBpedia have the larger restriction class from DBpedia, while the other 2746 have the larger restriction class from GeoNames. Tables 1, 2, 3, & 4 list a few interesting examples of these union alignments between GeoNames -DBpedia and LinkedGeoData-DBpedia (in either direction), which we describe here. The tables are organized as follows. Column 2 describes the sub-group, i.e. (p1,v1,p2). Column 3 contains the list of the value part of the property-value pairs in the restriction classes of the smaller sets (i.e. List(v2)). The score of the union is noted in column 4 (RU0 = jUAj ) followed by jUAj and jULj 5 Intuitively, it would make sense to the reader that this instance might perhaps be a hospital of a medical school. jULj in columns 5 and 6. Column 7 describes the outliers, i.e. values of v2 that form restriction classes that aren't direct subsets of the larger restriction class. Each of these values also has a fraction with the number of instances that do belong to the larger restriction class of the total number of instances of the restriction class (or jImg(r1)j ). It can be seen that the fraction is less than our jr2j relaxed subset score. If the value of this fraction was greater than the relaxed subset score (i.e. 0.9), the set would have been included in column 3 instead. The last column mentions how many of the total UL instances we were able to explain using UA and the outliers. For example, the union alignment of #1, is the Educational Institution example described before. It shows how educational institutions from DBpedia can be explained by schools, colleges and universities in GeoNames. Column 4, 5 and 6 explain the alignment score RU0 (0.98), the size UA (396) and the size of UL (404). The seven of the eight outliers found (S.BLDG, S.EST, S.LIBR, S.MUS, S.HSP) are mentioned along with their P 0 fractions in column 7.
We also found some other interesting alignments. #2 shows the details of the Spain example mentioned brie y in Section 2.2. #3 shows a union alignment that aligns smaller sets or parts from GeoNames to a complete set. The region of Basse-Normandie in France is made up of three departments. The restriction classes of these three regions are constrained by the geonames:parentADM2 property. #4 shows that Airports and Airbases make up 99% of the airports in DBpedia. From its outliers, one might argue that Air elds (S.AIRF) should also be included, but it was not as its P 0 score was lower than the threshold. Outliers also show that there is a Hill in geonames that has been classi ed as an airport. Even though this instance may be an airport in the hills, ontologically it doesn't make sense that a hill can be an airport. A similar case is observed in #8 where we nd that there is at least one water tower in LinkedGeoData that is aligned with an Educational institution in DBpedia.
The union alignment #5 should have been as straightforward as alignment #2. Our approach was able to detect a pattern, however, that might have been overlooked after looking at individual instances. Netherlands from GeoNames, for example, should be aligned with the country Netherlands from DBpedia. However we have possible alias names, such as The Netherlands and Kingdom of Netherlands, as well a possible linkage error to Flag of the Netherlands.svg generated while importing Wikipedia data into DBpedia (the error seems systematic, see Jordan in #6).
Alignment #7 was able to explain 8 of the 10 license plate codes in the state (bundesland) of Saarland6. The ones that it missed were Ottweiler (OTW) and the police vehicle codes (SAL). Since the vehicle code SAL is not associated with any populated places in Saarland, it is quite possible that it does not get mentioned in LinkedGeoData. Our approach thus provides a deeper insight into the nature of the sources. #9 tries to nd the composition of the state of New Jersey. 100% of the instances in New Jersey from LinkedGeoData can be accounted 6 http://www.europlates.com/publish/euro-plate-info/german-city-codes for in the 9 counties. New Jersey actually has 21 counties7. This suggests that instances in New Jersey in LinkedGeoData that are linked to DBpedia are not a complete representation resulting in an equivalent alignment. The quality of the results generated by our extensional approach are tied to the quality of the instances in the dataset. We nd, however, that such alignments, even though they might be partially incorrect, give an accurate representation of the actual instances in the dataset and highlight the practical quality of the links in the Web of Linked Data.8 Finally, alignment #10 describes how the concept Waterways in LinkedGeoData can be de ned as the union concept of Streams and Rivers in DBpedia. The complete set of alignments discovered by our algorithm are available on our group page.9 4
Related Work
Ontology alignment has been a well explored area of research since the early
days of ontologies. It has received renewed interest in recent years with the
rise of the Semantic Web. Euzenat & Shvaiko [
I m 3 o ed 40 r f
n s i t a e l s p r x e l E l a m # s , d )31 ,)1 n a
(1/ /13 a i d ( e T ) p S P 3 ) B E S 4 5
s .
D r S .H /1 63
e , S ( 7 om lit ) S 1/ fr u 22 ,)7 U (
1 / s t O (3/ (1 .M IT se S r G R e B g D I r a L .L l
.B S th S i j w L 40 , s Uj 4 t e j s a A 69 t Uj 3 a d j j ida UAjULj 01 e 8 p = .9 B 0U 0 D R d n , a C 0 2 0 2 1 0 9 # fr T
o a i c 3 3 3 4 d b p e d i a : P l a c e ( 1 / 9 4 9 8 9 ) 3 4 its seP tu la ito te n N 2 6 1 0 e n t s f r o m e o D a t a w i t h f r o m R a
n
U0 d 1 = D . 0 B jUjU p L A e j j d
i 2 jU a 14 A d j a
t 2 jU a 14 L se j t s , O l
a u r t g lie re r s s e t s 21 ed a 4 ta # L i n E k
e x d p G l a e i o n D I n a s n t d a n s
m c e a s l l e r 8 7 # L T
in a
S k b r d f d b r lgd aS fd f:ty epd f:td :O ra bp -bu edG le3 p i y p la ed rg eo . e a p e n i
o D E g :E ,e nG ,d :a cdau eoD bdun fppu taa axpm it B se 1 le o L l ; an ic an 1v la lIn en ,d 2;p ign
g m
H
N O lg ch
m d o V K M :Wlo en K , , iL eo
D ta l,g ity ,WSB IG ts e d ,
a rT :U lg N ,S ,B 2v( ta ow n :d D L M ) a
K S Z n
d e iv r e 2 , G rs 54 , i t 3 y , , e n t s f r o m t h e L i n k e d G D B p e R d
U0 ia .0 = d 9 a 3 jUjU t
a L A s j j e
t 4 jU ,s 6 A w j i
t 4 jU h 9 L l j a
r O g u re 2 6 4 e 0 6 d 9 t lie tse r s s f r # o
m E
D x p B l p a e i d n i a a I n n d s ta sm n a ec lle s r s e t s f r o m 5 Conclusions and Future Work We described an approach to identifying union alignments in geospatial data sources on the Web of Linked Data. By extending our de nition of restriction classes with the disjunction operator, we were able to nd alignments of union concepts from one source to larger concepts from the other source. Our approach produced union alignments as results that found that concepts at di erent levels in the ontologies of two sources can be mapped even when there was no direct equivalence. We were also able to nd outliers that enable us to identify inconsistencies in the instances that are linked by looking at the alignment pattern. The results provide deeper insight into the nature of the alignments of Geospatial Linked Data.
Though the scope of this paper is the geospatial domain, our algorithm can be used in other domains as well. Our next step is to explore other domains like zoology and genetics for union alignments. Other possible future work is in the mapping and understanding of the properties in the sources. Our preliminary ndings show that the results of this paper can be used to nd patterns in the properties. For example, the countryCode property in GeoNames is closely associated with the country property in DBpedia, though their ranges are not exactly equal. We believe that an in-depth analysis of the alignment of ontologies of sources is warranted with the recent rise in the links in the Linked Data cloud. This is an extremely important step for the grand Semantic Web vision. Acknowledgements This research is based upon work supported in part by the National Science Foundation under award number IIS-1117913.