The importance of geospatial information is being re ected on the growing amount of spatial datasets on the Semantic Web. However, the high variability of the data presents challenges for integration. In this paper, we address the problem of nding spatial equivalences between geospatial RDF datasets. First, we present mappings between our NeoGeo vocabulary and the vocabularies used by some well-known spatial RDF datasets. Second, we describe a method to nd spatially co-located features across spatial RDF datasets. To nd equivalences, we rely on analyzing the Hausdor distance distribution in the compared datasets, with the objective of nding a sensible criterion that aids the recognition of equivalent regions.
Geospatial data is ubiquitous in information management, supporting scienti c, industrial or just everyday activities. The relevance of geospatial data is re ected by the growing amount of geospatial datasets on the Web.
A feature is an abstraction of a real world phenomenon (e.g. a building, a mountain or an administrative region). A geographic feature is a feature associated with a location relative to the Earth, which is usually represented by a certain geometric shape (e.g. a point, a curve or a polygon). Features that are spatially colocated (i.e. share the same location) are not necessarily always the same. However, nding spatially co-located regions is a powerful measure of similarity between features.
Factors like rounding e ects, di erent scales and di erent formats, present a challenge when attempting to elicit equivalences between geospatial resources. We de ne a method for obtaining a criterion that best ts the di erences between the datasets merged.
This work was successfully applied to integrate our RDF representations of the NUTS nomenclature of the European Union 3 and of the GADM project 4 to other datasets describing spatial information on the Semantic Web, and also between each other.
Our contributions are as follows: { Representation and modeling of datasets: we survey the representation of existing geospatial datasets, and distill an integration vocabulary which covers the 3 http://nuts.geovocab.org/ 4 http://gadm.geovocab.org/ core set of classes and properties in existing data. We also integrate existing vocabularies and publish two geospatial datasets (Section 2). { Integration and mapping of multiple datasets: we develop an algorithm for nding equivalences for geometric shapes across multiple datasets (Section 3). { Evaluation of the presented approach: we conduct experiments in which we evaluate the accuracy of the results (Section 4).
We discuss the related work in Section 5. Finally, we identify areas for future work and conclude in Section 6. 2
Representing geospatial data on the web 2.1
We start with providing a brief summary of the analyzed datasets.
{ UN FAO Geopolitical Ontology5: The Food and Agriculture Organization of
the United Nations (FAO) is a specialized agency of the UN. The UN FAO
Geopolitical Ontology provides the FAO and its associated partners with a
master reference for geopolitical information.
{ OS OpenData6 [
Linked Data. { GeoNames.org: GeoNames is a geographical database that covers all countries and provides Linked Data under a Creative Commons attribution license. { Uberblic.org: Uberblic provides an integration service that includes data from
GeoNames, Wikipedia, MusicBrainz, Freebase, Last.fm and Foursquare. { RAMON NUTS8: The Nomenclature of Units for Territorial Statistics (NUTS) is a geocoding standard for referencing the subdivisions of countries for statistical purposes developed by the European Union and published as Linked Data. { DBpedia.org: The community e ort extracts structured information from Wikipedia for publication as Linked Data. { NeoGeo: We provide an integration vocabulary, described in more detail in
Sections 2.4 and 2.5. 5 http://www.fao.org/countryprofiles/geoinfo/geopolitical/resource/ 6 http://data.ordnancesurvey.co.uk/ 7 http://openstreetmap.org/ 8 http://rdfdata.eionet.europa.eu/ramon/nuts2008/ 2.2
The analyzed spatial datasets represent the location of features in di erent ways. We identi ed four main kinds of representation: point, bounding box, points in lists, points using a single property and literals. Geometric shapes are not only described using di erent vocabularies, but also these vocabularies are based on di erent structures, which increases the di culty of working with GeoData across datasets.
{ Point Location of objects is merely represented by a geographic point. The
most common vocabulary to do so is W3C Geo[
A spatial relation states the location of an object in relation to another. We created a set of vocabulary mappings to the NeoGeo vocabulary using the rdfs:subPropertyOf predicate. Table 1 shows which predicates are used in each dataset to describe spatial relations.
Disjoint Touches hasBorder
With disjoint touches
Overlaps Within
isInGroup partially- within Overlaps contains equals formaParteDe parentFeature formadoPor children
Features containinglocation partOf locatedInArea PP nearby / nearbyFeatures Dataset UN FAO Ordnance Survey GeoLinkedData.es LinkedGeoData.org GeoNames.org Uberblic.org RAMON NUTS DBpedia.org NeoGeo neighbour / neighbouringFeatures adjoininglocation DC
EC
PO
PC
EQ Given the lack of a standardized spatial vocabulary, we developed our own set of spatial ontologies, which we call NeoGeo9. We manually created a set of mappings between our vocabularies and the vocabularies used by some acknowledged spatial datasets like the Ordnance Survey and LinkedGeoData.org. Both the GADM and NUTS datasets use the NeoGeo vocabularies.
The Geometry Vocabulary10 is an RDF vocabulary for the description of
georeferenced geometric shapes. It is based on the Core Pro le of the Spatial Schema
[
The Spatial Ontology11 provides a vocabulary for the representation of the
spatial relations used in the Region Connection Calculus (RCC) [
We provide two datasets, NUTS and GADM, containing geospatial information as Linked Data. 9 http://geovocab.org/ 10 http://geovocab.org/geometry 11 http://geovocab.org/spatial
The Nomenclature of Territorial Units for Statistics (NUTS) is a classi cation de ned by the Eurostat o ce of the European Union. It is intended to divide the administrative regions of the European Union, in a way that the resulting regions are demographically equivalent.
The RDF representation of the NUTS nomenclature contains a 1:60,000,000 geospatial representation of the NUTS statistical units mapped to RDF. The resources representing NUTS regions in our dataset include (among others) links to resources in DBpedia, FAO Geopolitical Ontology, GeoNames, Ordnance Survey and GeoLinkedData.es.
The Global Administrative Areas (GADM)12 is a project seeking to become a collaborative e ort on building a spatial database containing information about all of the administrative regions in the world. GADM aims to provide high resolution mappings for all administrative areas in the world, along with additional information about them. The latest version of GADM (0.9) maps 226.439 administrative areas. The information can be downloaded at their website in the following formats: Shape le, ESRI geodatabase, RData and KMZ.
Given the value of the GADM project, we have created an RDF representation of the information contained in the original GADM project, which we seek to enrich with additional capabilities like the materialization of spatial relations, mappings to other RDF datasets and SPARQL querying support. 3
The alignment of the vocabularies is only the rst step for the integration of the datasets. The second step in the process is to nd matchings between the features.
We can classify the features into three general categories, in relation on how their location is represented in the datasets. First are the resources that present no quantitative spatial information at all. Second, the features that approximate their location by using only a single point. And nally, features which present rich information about their location (i.e. include a description of their geometric shape). 3.1
Resources which include no quantitative information about their location can be
integrated by relying either on text matching [
Sometimes the location of a feature is approximated by using a single point (e.g. using the W3C Geo vocabulary) instead of representing its actual extent (i.e. the geometric shape). Examples of this kind of representation are DBpedia, LinkedGeoData.org, GeoNames and LinkedGeoData.es. 12 http://gadm.org/
This kind of representation can lead to false assertions while performing comparisons against a spatial index if these features are not especially considered. For example, DBpedia uses the W3C Geo Vocabulary to describe the latitude and longitude coordinates of features as points. The resource for Germany in DBpedia http://dbpedia.org/resource/Germany is spatially represented by a point with latitude 52.516666 and longitude 13.383333. If we intended to obtain the containment relations for such resource by comparing it with a spatial index, the result would be that Germany is part of Berlin, which is false. Therefore, even though these relations can be obtained using the coordinates represented in DBpedia, rst it is necessary to ensure that the process will not return such false statements. The false matches can be avoided, for example, by ltering the features that will be compared by its class, in a way that ensures that the feature will be properly contained in the features that it will be compared to (e.g. cities in provinces or restaurants in cities). 3.3
Resources that include an accurate description of their extent as a geometric shape can be compared using this information. We will focus on obtaining links between spatially co-located regions (we use the spatial:EQ predicate). Whether owl:sameAs links can be deduced from the obtained links depends on the modeling of the datasets (e.g. the class the resource belongs to).
To perform the comparison, we will adopt a Plate Carree projection for both of the compared datasets. Being this projection equirectangular, we can treat latitude and longitude coordinates as if they were cartesian. Therefore, the units will be presented in centesimal degrees.
The bene t of using an equirectangular projection is that it simpli es the calculations by avoiding local reprojections (e.g. to UTM), and also allows to use a global spatial index, improving the performance of the process. In our approach it is not important if the projection distorts the real size or the actual geometric shapes on the surface of the Earth, as long as the geometric data is equally distorted for all datasets.
Due to a series of factors like rounding e ects and di erent scales, there is no guarantee that both geometric shapes will be vertex by vertex identical. Figure 1 exempli es these di erences by showing the boundaries for Luxembourg as they are represented in the GADM and NUTS datasets.
An e ective method of determining how similar two geometric shapes are is
to compute the Hausdor distance between them. The Hausdor distance is the
"maximum distance of a set to the nearest point in the other set\ [
It can be deduced from the formula that in the particular case of calculating the Hausdor distance between points, the Hausdor distance matches the Euclidean distance d(a; b).
Fig. 1: Incongruency of the geometric data (GADM: blue, NUTS: violet) due to di erences in resolution.
Figure 2 shows the values of correct and wrong guesses for similar regions in both datasets. In order to better appreciate the variability of the values, only small areas are plotted in the chart. From the gure it can be deduced that smaller regions (e.g. boroughs) require greater precision than larger regions (e.g. countries), in order to di erentiate them from each other. Therefore, the Hausdor distance margins allowed for regions which are suspected to be spatially co-located must be di erent, depending on the area size of the regions being compared.
To address this issue, it is desirable to obtain a function for a Hausdor distance threshold for a given area size. In order to do this, rst we calculate the midpoint between the lowest and second lowest Hausdor distance values, for a representative set of features in both datasets. Afterwards we perform a quadratic regression from the midpoint Hausdor distance values. This produces a formula that allows to determine the maximum Hausdor distance allowed between two regions, in order to consider them similar. The resulting function has the following form:
M axHDist(x) = A x2 + B x + C
Where MaxHDist is the maximum Hausdor distance allowed between two regions in order for them to be considered similar. The x variable is the area of the region. The quadratic function gives more precision for small regions while allowing a greater margin for large regions. The A,B and C constants are tunable parameters for the integration procedure.
A yet unresolved issue of using a quadratic function is that the samples must include values for the approximated maximum area for which the integration will be performed. This is because the values of the function will tend to decrease after reaching a maximum value. We are performing experiments with logarithmic functions to solve this issue.
Table 2a shows sample execution times and Hausdor distance values between features in the NUTS and GADM datasets.
Region Name NUTS
Id Finland FI 62.2835 Iceland IS 19.3357 Croatia HR 6.2139 Schleswig-Holstein DEF 2.1126 Karlsruhe DE12 0.8433 Seine-Saint-Denis FR106 0.0358
Area Hausdor Distance Time (ms)
Calculating the Hausdor distance between the original geometric data is quite
expensive, especially for large regions. In order to increase the performance of the
process, as an optional step, we chose to simplify the geometric shapes using the
Ramer-Douglas-Peucker algorithm [
The Ramer-Douglas-Peucker algorithm starts by considering a line segment between the rst and last points of the line. Then, it nds the furthest point from the line segment between the rst and last points of the line. If the point found is closer than a prede ned distance " to the line segment, all other points that were not chosen to be used in the solution can be discarded. If the point furthest from the line segment is greater than ", then the point is used in the solution. The algorithm then calls itself recursively with the found point and the last point as parameters.
Tables 2b and 2c show the Hausdor distance between the NUTS regions and their matching GADM region, as well as execution times for di erent levels of simpli cation. As it can be seen, execution times are dramatically reduced, especially for large regions.
A further re nement of the process is to calculate the simpli cation distance for the Ramer-Douglas-Peucker algorithm depending on the Hausdor distance threshold and therefore of the area of the regions. This is based on the same principle applied for the Hausdor distance, where small areas require greater precision than large areas.
Given two spatial datasets A and B, the algorithm can be summarized as Algorithm 1. 4 4.1
We implemented the algorithm presented in Section 3.3 using the PostGIS 1.5.2 extension running on PostgreSQL 8.4.8. The computer is running on Ubuntu 10.04 on an Intel SU7300 processor with 4GB DDR3 RAM.
PostGIS includes the ST Hausdor Distance function, which implements an approximation to the original algorithm. This approximation can be thought of as the "Discrete Hausdor distance\, which is the Hausdor distance restricted to discrete points for one of the geometric shapes. If more precision is needed, the function receives also an optional "denistyFrac\ parameter which performs a segment densi cation before computing the discrete Hausdor distance.
Since we are not concerned about the actual Hausdor distance values, but just use it as a measure to determine if two regions are similar enough to be considered spatially co-located, this approximation is su cient.
For the simpli cation of geometric data we will use the ST SimplifyPreserveTopology
function included in PostGIS. This function is a re ned version of ST Simplify,
which is based on the Ramer-Douglas-Peucker algorithm [
The query used with PostGIS to nd regions which are supposed to be spatially co-located is very similar to the one presented below. To avoid having to perform the same calculations repeatedly, the values of the maximum Hausdor distance function are cached into the "max hausdor dist\ column. The "geometry\ column in both tables belongs to the "Geometry\ datatype provided by PostGIS. end else end end end end input : Datasets A, B output: Equivalent regions from A and B Convert the compared resources to a shared coordinate reference system. Project the data into an equirectangular projection.
Obtain a representative set of regions in dataset A which intersect regions in dataset B and have a maximum arbitrary Hausdor distance between each other. foreach region a of a representative set of regions in dataset A do
Get the minimum Hausdor distance to a region in dataset B.
Get the second minimum Hausdor distance to a region in dataset B.
Calculate the midpoint between the minimum and second minimum Hausdor distances. end Perform a regression on the midpoints between the Hausdor distances to calculate the Hausdor threshold function. foreach region a in A do foreach region b in B do if a intersects b then
Calculate the Hausdor distance between a and b. if Hausdor distance between a and b is lower than the threshold for the area of a then a and b can be considered as spatially co-located. a and b cannot be considered as spatially co-located.
Algorithm 1: Matching algorithm SELECT g.gadm_level, g.gadm_id, n.nuts_id
FROM nuts n INNER JOIN gadm g ON (n.geometry && g.geometry) WHERE n.shape_area BETWEEN (g.shape_area*0.9) AND (g.shape_area*1.1) AND ST_HausdorffDistance(ST_SimplifyPreserveTopology(n.geometry, 0.5), ST_SimplifyPreserveTopology(g.geometry,0.5)) < g.max_hausdorff_dist;
Basically this query selects the identi ers for the GADM region (level and id), and for the NUTS region (id). The && operator matches an intersection between the bounding boxes of the of the regions. Since similar regions will also have a similar area size, the rst condition in the "where\ clause lters regions that have a similar area size with an error of 10%. The second condition checks if the discrete Hausdor distance between the simpli ed geometric shapes is within the limit calculated by the function presented in Section 3.3. 4.2
We can analyze the e ectiveness of the method by looking at the results of the process of nding spatial equivalences between the NUTS and GADM datasets.
The NUTS dataset codes the geometric shapes fully in RDF using the NeoGeo vocabulary, and the coordinate system used is WGS-84. The data is retrieved by using a Construct SPARQL query and then converted into WKT using XSLT.
After retrieving the geometric data, it is merged with the GADM dataset using the method presented in Section 3.3.
Not all NUTS regions are expected to match a GADM region, since many NUTS regions represent parts or aggregations of administrative boundaries. Also a GADM administrative region in a certain level should be able to match di erent NUTS regions in di erent levels, and vice-versa.
From the existing 1,671 NUTS regions of the 2008 nomenclature that were included in the comparison, the algorithm detected 965 matches, from which 13 were false positives, as Table 3 shows.
Area Hausdor Distance These false positives are due to the fact that the threshold is set too high for very small and very large areas. It is desirable to produce a larger gradient for small areas and a smaller Hausdor distance threshold for large areas. This is still a matter for further research. 5
The problem of aligning spatial datasets is not new in the Semantic Web community and much work has been put on nding sensible solutions both at T-Box and A-Box level.
Ontology alignment is a heavily researched topic. Proposed solutions have been
based on the terminological [
Algorithms have also been proposed for feature matching across spatial datasets.
[
We have presented a generic method that can be used to map multiple spatial datasets. We also showed its functioning by describing the integration between our two spatial datasets and analyzed its results.
Although the method has been used successfully to align the GADM and NUTS datasets, the false positive rate can still be improved when analyzing regions covering a wide spectrum of area sizes. However, the presented method has proven to be usable in Semantic Web applications.
Since the rst experiments showed promising results, we are developing a tool that automates the whole mapping process. We are also further re ning the algorithm to improve its precision and performance.
The authors acknowledge the support of the European Commission's Seventh Framework Programme FP7/2007-2013 (PlanetData, Grant 257641).