Link Discovery is a new research area of the Semantic Web which studies the problem of nding semantically related entities lying in di erent knowledge bases. This area has become more crucial recently, as the volume of the available Linked Data on the web has been increasing considerably. Although many link discovery tools have been developed, none of them takes into consideration the discovery of spatial or temporal relations, leaving datasets with such characteristics weakly interlinked and therefore disallowing the exploitation of the rich information they provide. In this paper, we propose new methods for Spatial and Temporal Link Discovery and provide the rst implementation of our techniques based on the well-known framework Silk. Silk, enhanced with the new features, allows data publishers to generate a wide variety of spatial, temporal and spatiotemporal relations between their data and other Linked Open Data, dealing e ectively with the common heterogeneity issues of such data. Furthermore, we experimentally evaluate our implementation by using it in a real-world scenario and demonstrate that it discovers accurately all the existing links in a time e cient and scalable way.
Linked data is a research area which studies how one can make RDF data available on the Web, and interlink it with Work done while the author was at National and Kapodistrian University of Athens.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s).
WWW2016 Workshop: Linked Data on the Web (LDOW2016).
April 11, 2016 - Montréal, Canada.
c 2016 Copyright held by the owner/author(s).
other data in order to increase its value for users [
Recently, spatial and temporal extensions to RDF have
been proposed and implemented. GeoSPARQL [
Link Discovery is one of the main Linked Data Principles.
Its main objective is to establish semantic links between
entities in order to enhance and enrich the information that is
known about them. Whilst the problem of Entity
Resolution i.e., the problem of nding entities which are equivalent,
has been studied a lot in areas such as Relational Databases
and Information Retrieval, Link Discovery de nes the more
generic problem of nding semantically related entities lying
in di erent knowledge bases [
Although a lot of e ort has been given in the representation and querying of geospatial and temporal RDF data, there are not many works in the respective area of Link Discovery. In the context of Spatial Link Discovery, state of the art techniques are focusing on nding only spatial equivalences between entities, leaving other kinds of relations e.g., topological relations, undiscovered and the rich geospatial information lying in many datasets unexploited. The situation regarding Temporal Link Discovery is even more premature and thus, to the best of our knowledge, there are almost no datasets with temporal information that are connected with each other with links that denote a temporal relation.
Another common use of Link Discovery is for detecting
internal links within a single dataset. For example, by
applying an Entity Resolution method on a dataset, we can
1http://www.w3.org/DesignIssues/LinkedData.html
2http://www.opengeospatial.org
discover all the similar entities i.e., all the duplicates of this
dataset. Hence, with Spatial and Temporal Link Discovery
we can materialize all the spatial, temporal and
spatiotemporal relations that hold between the entities of a dataset.
This operation is very useful in the areas of Qualitative
Spatial and Temporal Reasoning where the large graphs that are
created based on the qualitative relations are given as input
to corresponding reasoners [
The lack of research in the area of Spatial and Temporal Link Discovery will be made more notable when more datasets with such characteristics will be made available in the LOD Cloud. Currently, a lot of initiatives are moving towards this direction by publishing open geospatial data and metadata coming out of open government directives3 and open Earth Observation (EO) data and metadata that is currently made available by space and environment agencies (e.g., ESA, NASA and EEA)4. This data usually consists of measurements produced by observations with hundreds of gigabytes of geospatial and temporal information. Making all this data available as Linked Data and interlinking it with semantic connections will allow the development of services with great environmental and commercial value.
EU projects such as LEO, MELODIES and TELEIOS,
have already started exploiting this kind of data by
studying its whole life cycle [
In this paper, we propose new methods for Spatial and Temporal Link Discovery and provide the rst implementation of our techniques based on the well-known framework Silk. Silk, enhanced with the new features, allows data publishers to generate a wide variety of spatial, temporal and spatiotemporal relations between their data and other Linked Open Data, dealing e ectively with the common heterogeneity issues of such data. Furthermore, we experimentally evaluate our implementation by using it in a real-world scenario, with datasets that comprise rich spatial and temporal information, and demonstrate that it discovers accurately all the existing links in a time e cient and scalable way.
The structure of the paper is organized as follows. In Section 2 we present related work in the area of Link Discovery. 3http://www.linkedopendata.gr 4http://datahub.io/organization/teleios and http://datahub.io/organization/leo 5http://www.melodiesproject.eu/content/ enhancing-geospatial-sparql-query-times-silk 6O(nm) where n and m are the numbers of points of the joining spatial objects.
In Section 3 we provide the background on which the new methods for Spatial and Temporal Link Discovery that we propose in Section 4 are based. In Section 5 we describe the implementation of our techniques in the framework Silk and in Section 6 we present the experimental evaluation of them. Finally, in Section 7 we conclude the work by discussing future directions. 2.
Up to now, little e ort has been given in the research area of Spatial and Temporal Link Discovery. Most of the approaches on generic Link Discovery do not exploit the rich spatial and temporal information existing in some datasets, whereas domain speci c approaches on Spatial Link Discovery are able to discover only spatial similarities (spatial duplicates). Hence, to the best of our knowledge, there are no frameworks, either generic or domain speci c, for discovering spatial or temporal relations other than equivalences among RDF datasets. Below we describe the most related to our work state-of-the-art Link Discovery frameworks.
In the area of generic Link Discovery, the authors of [
The LIMES framework [
Similarly to LIMES, Silk [
In the area of Spatial Link Discovery there are some
domain speci c approaches which are able to discover only
spatial equivalences among datasets i.e., they focus on
Spatial Entity Resolution. In order to achieve this, they combine
the geographic distance of the geometries of the entities with
other kinds of distances e.g., with the string distance of their
labels. The supported geographic distances can be applied
either between any kind of spatial objects (e.g., Hausdor
distance), or only between point objects (e.g., Orthodromic
distance). Some of these approaches are presented in [
From the generic frameworks, LIMES also addresses the
problem of Spatial Entity Resolution in [
A detailed review on state of the art algorithms and
frameworks is performed in the surveys [
In this section we provide the state-of-the-art on the
representation of spatial and temporal information in the RDF
data model and a formal de nition of the problem of Link
Discovery. We also present the models and calculi on which
we base the new Link Discovery relations that we introduce.
The extended background of this paper is given in [
Spatial information in the RDF data model is usually represented as serializations of geometries accompanied with a Coordinate Reference System (CRS) which de nes how to relate these serializations to real geometries on the surface of Earth. For encoding this information, Well-Known Text (WKT) and Geography Markup Language (GML) are used. WKT is an OGC standard for the representation of vector geometry objects, CRSs, and transformation rules between di erent CRSs. On the other hand, GML, developed by OGC as well, is the most common XML-based encoding standard for the representation of geospatial data, that provides XML schemas for de ning a variety of concepts that are of use in Geography: geographic features, geometries, CRSs and topologies.
The main RDF vocabularies for representing spatial as well as temporal information are described below. W3C GEO. W3C GEO is an RDF vocabulary for representing simple location information in RDF. It provides the basic terminology for serializing point geometries using a namespace for representing latitude, longitude and other information about spatially-located things. The CRS of this vocabulary is encoded in the namespace and it is the WGS 847. Below, we give an example of the W3C GEO vocabulary: _:1 rdf:type wgs84geo:Point . _:1 wgs84geo:lat "10"^^xsd:double . _:1 wgs84geo:long "20"^^xsd:double .
GeoSPARQL. GeoSPARQL [
The de nition of Link Discovery based on which we de ne our new methods is described as follows:
Definition 1. Let S and T be two sets of entities and R the set of relations that can be discovered between entities. For a relation r 2 R, w.l.o.g., a distance function dr and a distance threshold dr are de ned as follows: dr : S
T ! [0; 1] ; dr 2 [0; 1] The domain of dr is the Cartesian product of S and T and the range is the computed distance normalized to the interval [0; 1]. dr is also normalized to [0; 1].
The set of discovered links for relation r (DLr) is de ned as follows:
DLr = f(s; r; t) j s 2 S ^ t 2 T ^ dr(s; t) dr g DLr contains triples which have as subject an entity from dataset S, as object an entity from dataset T and as predicate the relation r. A triple belongs to DLr i the function dr returns a distance that does not exceed the threshold dr . 3.3
Region Connection Calculus. The Region Connection
Calculus (RCC) [
Dimensionally Extended 9-Intersection Model. The
Dimensionally Extended 9-Intersection Model (DE-9IM) [
Y X EQ Y (a)
X X TPP Y
X
Y X TPPi Y
X X NTPP Y
X Y X NTPPi Y areas, we can de ne relations derived from DE-9IM such as: Intersects, Overlaps, Equals, Touches, Disjoint, Contains, Crosses, Covers, CoveredBy and Within.
Egenhofer’s and OGC Simple Features Model. The
Egenhofer's Model [
Spatiotemporal Constraint Calculus. By pairing a
spatial and a temporal relation model or calculus we can
create a spatiotemporal one. For example, the
Spatiotemporal Constraint Calculus (STCC) [
In this section we describe the new methods that we introduce for Spatial and Temporal Link Discovery. Speci cally, we present the new sets of relations and transformations that we provide and an optimization technique called Blocking. Finally, we prove theoretically the soundness and complete9http://www.opengeospatial.org/standards/sfs ness of our methods and describe how the latter has as result their accuracy to be 100%. 4.1
According to the de nition of Link Discovery, presented above, the set R contains all the relations that can be discovered between entities. In this paper we introduce the sets of spatial (Rs), temporal (Rt) and spatiotemporal (Rst) relations. These sets contain all the relations that are included in the models and calculi described in Section 3. Speci cally, Rs contains the relations that are included in the DE-9IM, Egenhofer's and OGC Simple Features Models and the Region Connection and Cardinal Direction Calculi, Rt contains the relations included in the Allen's Interval Calculus and Rst contains all the per two combinations of the above models and calculi.
We consider these relations as Boolean relations (RB) i.e., either they hold or they do not hold (Rs; Rt; Rst RB R). These relations have also been studied in the context of fuzzy logics but this is out of the scope of this paper.
RB constitutes a special subset of R. The distance function dr and the distance threshold dr for a relation r 2 RB are de ned as follows: dr(s; t) = A common issue that occurs when one tries to discover links between datasets created by di erent data providers is heterogeneity (e.g., we can have datasets expressed in di erent time-zones). A preprocessing technique that addresses this problem is the application of transformations on the attributes of the entities before checking the existence of a link. The transformations that we introduce are generic and not tightly coupled to speci c kind of datasets. (a) (b) Spatial Transformations. The spatial transformations that we introduce are the following:
Vocabulary Transformation. As mentioned in Section 3, the geometries of a dataset can be expressed in di erent vocabularies (e.g., W3C GEO, GeoSPARQL or stRDF). This transformation converts the geometry literals of a dataset in order to be expressed in a common vocabulary (GeoSPARQL).
Serialization Transformation. The geometries of a dataset can be also serialized in di erent ways (e.g., using WKT or GML). This transformation converts the geometries of a dataset to follow a common serialization (WKT).
CRS Transformation. Although a CRS such as WGS 84 is a comprehensive way to describe locations on Earth, some applications work on a projection of the Earth. In these cases, a projected CRS is used that transforms the 3-dimensional ellipsoid approximation of the Earth into a 2-dimensional surface. This transformation reverts the CRS of a geometry from a projected one (e.g., the GGRS87 for Greece) to the World Geodetic System (WGS 84) for better precision and homogeneity.
Validation Transformation. This transformation converts not valid geometries (e.g., self-intersecting polygons) to valid ones.
Simpli cation Transformation. Some datasets have very complex geometries, which makes the computation of spatial relations ine cient. This transformation simpli es a geometry according to a given distance tolerance, ensuring that the result is a valid geometry having the same dimension and number of components as the input.
Envelope Transformation. This transformation computes the envelope (i.e., the minimum bounding rectangle) that contains a geometry and it is useful in cases that we want to compute approximate spatial relations between two datasets.
Area Transformation. In some cases we may want to compare the areas of two geometries to verify the existence of a relation. This transformation computes the area of a given geometry in square metres.
Points-To-Centroid Transformation. In crowdsourcing datasets like OpenStreetMap10, multiple users can dene the position of the same placemark. As a better approximation of the real position of this placemark we can compute the centroid of these positions. This transformation computes the centroid of a cluster of points.
Temporal Transformations. The respective temporal transformations that we introduce are the following: Period Transformation. The stRDF data model supports both time instants and periods. This transformation converts a time instant to a time period with the same starting and ending point.
Time-Zone Transformation. Time elements (i.e., time instants and periods) can be expressed in di erent time-zones. This transformation converts the timezone of a given time element to the Coordinated Universal Time (UTC). 4.3
Since the size of datasets with spatial or temporal
information can be very big, approaches that perform exhaustive
checks between datasets are considered ine cient. Thus,
there is need for a scalable, yet sound and complete
technique for decreasing the number of checks by dismissing
de nitive non-matches prior to the actual check. The most
well-known technique to achieve this is known as Blocking
[
Spatial Relations. The Blocking technique for spatial relations that we propose builds blocks that divide the earth into curved rectangles as depicted in Figure 2(a). The reference system of our technique is WGS 84 which considers a spheroid approximation of the Earth. This approximation requires complicated mathematics for calculations such as areas, distances, etc. (e.g., the shortest path between two points in the spheroid is a circle arc whereas, in a planar approximation it would be just a straight line). Nevertheless, we chose WGS 84 because we prefer having highly accurate calculations rather than fast ones.
The area of the created blocks is measured in square degrees and can be adjusted by a spatial blocking factor sbf . The formula for the computation of the area is the following: 10http://www.openstreetmap.org blockArea = The bigger the value sbf gets, the more and smaller blocks will be created. For example, if we assign to sbf the value 10, our Blocking technique will create 6; 480; 000 non2 overlapping blocks with area 0:01 that cover the whole surface of the earth11.
After the division of the space into blocks, we compute the set of blocks into which each geometry must be inserted. In order to achieve this, we rst compute the minimum bounding box (MBB ) that contains each geometry, and then we nd the blocks that this MBB intersects with. Thus, each geometry is assigned to all the blocks with which its MBB intersects.
Temporal Relations. In the Blocking technique for temporal relations we follow a similar approach to the one for spatial relations. Time is one-dimensional and thus the blocks are one-dimensional as well. Let us suppose that all the time elements of our data are included in the interval from the Epoch12 until the Present (Figure 2(b)). This interval can be manually con gured according to the time range of our data. Following the same strategy as before, we divide the time in blocks whose length can be adjusted with a temporal blocking factor tbf . The formula for the computation of the length of the blocks is the following: blockLength =
time units 1 tbf where time units range from milliseconds to years.
After the division of the time into blocks, we insert in each block all the time periods and instants that temporally intersect with it.
Spatiotemporal Relations. The Blocking technique for spatiotemporal relations is a combination of the techniques mentioned above. In this case the blocks are threedimensional (two dimensions for space and one for time). The formula for the computation of the volume of the blocks is the following: blockV olume = time units 1 sbf 2 tbf 2 4.4
Given that all the entities are inserted in blocks using the aforementioned Blocking technique, we check a relation r 2 Rs[Rt[Rst only within the scope of each block. In order to achieve this, we use the actual spatial and/or temporal information, computing explicitly the relation.
Since the blocks are built to be completely independent of each other, this check can be performed in parallel with respect to the blocks. Then we construct the set of discovered links (DLr) by aggregating the respective links that have been discovered within each block.
Spatial relation Disjoint is treated in a slightly di erent way from the other relations. If two entities belong to the same block, then we follow the previous approach and we check explicitly the relation. If they don't, the Disjoint relation holds by de nition and thus we add a link without actually checking the relation. A similar approach is followed for the temporal relations Before and After as well as for the cardinal direction relations. 11The longitude range of WGS 84 is [ 180 ; 180 ] and the latitude range is [ 90 ; 90 ]. 12The Epoch has been set to January 1, 1970, 00:00:00 GMT. 4.5
The soundness and completeness of the proposed methods for Spatial and Temporal Link Discovery is proved in two steps. In the rst step we prove that the methods are sound and complete when performing an exhaustive check of all the possible pairs of entities (Cartesian product) and in the second that the Blocking technique that we propose does not a ect the accuracy of the discovered links.
Cartesian Product Technique. The proposed algorithms
that check if a spatial or temporal relation holds between
two geometries or time instants have been proven sound in
[
Blocking Technique. We prove that the application of the Blocking technique does not a ect the completeness of our methods for Spatial Link Discovery with reduction to absurdity.
Proof. Let two geometries lying in di erent blocks with a spatial relation r 2 Rs nfDisjointg holding between them.
If r holds between two geometries then they intersect at least at one point (from the de nition of the spatial relations).
If two geometries intersect at one point, so do their MBBs (from the de nition of MBB ).
If the MBBs of two geometries intersect, then there is at least one block in which they will be both inserted (as described above).
This results in a contradiction because we assumed that the two geometries are lying in di erent blocks. Therefore the initial assumption must be false.
The above proves that if a relation other than Disjoint holds between two geometries, then they will be placed in at least one common block and consequently the relation between them will be checked and discovered.
With a similar proof for the Disjoint, the temporal and the cardinal direction relations we can state that our methods remain complete, even after the application of the Blocking technique.
Since we proved theoretically that our methods are sound and complete, their accuracy is guaranteed. Metrics such as Precision and Recall are by de nition equal to 100%: P recision =
Recall =
T DL T DL + F DL
T DL =
T DL T DL
T DL = = 100%
= 100% T DL + F NDL
T DL T DL stands for True Discovered Links, F DL for False Discovered Links and F N DL for False Not Discovered Links. F DL and F N DL are both equal to zero as a consequence of the soundness and the completeness of our methods.
All the proposed methods for Spatial and Temporal Link Discovery have been implemented as extensions to the Silk framework13. As mentioned in Section 2, Silk is the only, to the best of our knowledge, open-source generic framework for discovering relationships between data items within different Linked Data sources.
For our implementation we extended transparently the core components of the Link Discovery Engine of Silk in the following phases:
Transformation Phase. In this phase, Silk reads the incoming entities from the data sources. As an optional step, a transformation operator can be applied to normalize the attributes of these entities. For this phase we implemented the transformation operators that we presented in Section 4.
Blocking Phase. Silk employs a blocking technique which maps entities to a multidimensional index. After the mapping, the entities are divided into multidimensional blocks which optionally overlap with each other. For our implementation we adapted the blocking technique that we introduced in Section 4 to the one that Silk uses, by utilizing a two-dimensional index for the spatial blocking, a one-dimensional for the temporal and a three-dimensional for the spatiotemporal blocking.
Link Generation Phase. Finally, a distance operator computes the distance for each pair of entities that have been inserted in the same block and if this does not exceed a given threshold, it writes the pair to the output. For this phase we implemented distance operators for all the spatial14 and temporal relations that were introduced in Section 4.
On top of the Link Discovery Engine, Silk implements two main applications. The rst is used for generating RDF links on a single machine and is called Silk Single Machine. The datasets that must be interlinked can either reside on the same machine or on remote machines which are accessed via the SPARQL protocol.
The second application is Silk MapReduce which is used for generating RDF links between datasets using a cluster of multiple machines. Silk MapReduce is based on Hadoop15 and it can scale out to very big datasets by distributing the link generation to multiple machines.
In both of these applications our Blocking technique divides the source datasets into blocks and then the distance operators run in parallel with respect to the blocks. In Silk Single Machine we have multi-thread parallelization and in Silk MapReduce multi-machine parallelization. 13The source code of the spatial and temporal extensions of Silk is publicly available here: https://github.com/ silk-framework/silk. 14For the cardinal direction relations, the developed operators support only points and not complex geometries as happens with all the other relations. 15http://hadoop.apache.org 6.
In this section we experimentally evaluate the spatial and temporal extensions of Silk by using it in a real-world scenario. The datasets, detailed instructions and other useful information for reproducing the experiments are publicly available16. 6.1
As we discussed in Section 2, to the best of our
knowledge, there is no related framework with which we can
discover spatial or temporal relations other than equivalences
among RDF datasets. Hence, in the experiments that we
conducted, we compared against variants of Silk and the
state-of-the-art spatiotemporal RDF store Strabon [
Strabon is not considered as a Link Discovery framework but since it supports the GeoSPARQL and stSPARQL query languages, NAMED GRAPHS and CONSTRUCT queries it can be employed for discovering spatiotemporal relations e.g., the intersects relation, by posing Link Discovery queries like the one depicted in Figure 3(a). The only restriction that we face with Strabon is that both the source and the target datasets must be stored locally, in di erent named graphs. On the other hand, with Silk, we can interlink a local dataset with a remote one, that is published by another data publisher. The only access that we need to it, is via a SPARQL endpoint. 6.2
We conducted our experiments both in a single machine and a distributed environment. For the single machine environment, we used a machine with two Intel Xeon E5620 processors (12MB L3 cache, 2.4 GHz), 32 GB of RAM and a RAID-5 disk array that consists of four disks (32 MB cache, 7200 rpm). For the distributed environment we used a cluster provided by the European Public Cloud Provider Interoute17, in which we reserved 1 Master and 20 Slave Nodes with 2 CPUs, 4GB RAM and 10GB disk each.
We ran our experiments using the latest version of Silk with the spatial and temporal enhancements (v2.6.1) and the latest version of Strabon (v3.2.10) with accordingly tuned PostgreSQL (v9.1.13) and PostGIS (v2.0) as proposed by the developers. 6.3
In [
A part of the processing chain of the service is to improve the thematic accuracy of the detected res (hotspots) by correlating them with auxiliary geospatial data. More speci cally, the service nds the land cover of each area which is threatened at a speci c time by a hotspot, in order to avoid false alarms from res started e.g., by farmers as part of their agricultural practices. Also, it nds the municipalities that a hotspot threatens and thus, competent authorities are made aware about the existence of a re in their area of 16http://silk.di.uoa.gr 17http://www.interoute.com 18http://ocean.space.noa.gr/ res CONSTRUCT {?s strdf:intersects ?t .} WHERE{ GRAPH ex:source{?s geo:hasGeometry/geo:asWKT ?sg.
?s strdf:hasValidTime ?st.} GRAPH ex:target{?t geo:hasGeometry/geo:asWKT ?tg.
?t strdf:hasValidTime ?tt.} FILTER(geof:sfIntersects(?sg, ?tg) && strdf:intersects(?st, ?tt))} (a) Dataset HG CLCG GAG
Geometries Time Elements Type #Points Type #Instants Polygons 148,192 Instants 37,048 Polygons 8,004,058 Periods 9,736 Polygons 979,929 Periods 650 responsibility.
Below, we provide a short description of the datasets of the
scenario, whilst in Figure 3(b) we present some quantitative
characteristics of them. These datasets also constitute a
subset of the datasets used in the state-of-the-art benchmark
for Geospatial RDF Stores, Geographica [
Hotspots of Greece (HG). The HG dataset contains the location and the acquisition time of detected res for each re season as produced by the National Observatory of Athens19 after processing appropriate satellite images.
CORINE Land Cover of Greece (CLCG). The Corine Land Cover project20 is an activity of the European Environment Agency that provides data regarding the land cover of European countries. The CLCG is a subset of the dataset that contains all the available information about Greece.
Greek Administrative Geography (GAG). The GAG dataset contains an ontology that describes the administrative divisions of Greece (prefectures, municipalities, districts, etc.) which has been populated with relevant data that is publicly available in the Greek open government data portal21.
With Silk, the above scenario can be translated into two interlinking tasks between the HG and the CLCG and the GAG datasets respectively. In these tasks, Silk discovers the spatiotemporal relation intersects between the datasets. For this, it rst applies a CRS transformation to normalize the heterogeneous geometries and a Period and a TimeZone transformation to normalize the heterogeneous time elements of the datasets. Finally, it populates the threedimensional spatiotemporal blocks and discovers the relation intersects within each one of them. Thus, if a hotspot threatens a municipality or a land cover area, then the output of this procedure will contain the respective entities from the HG, GAG and CLCG datasets, interlinked with an appropriate predicate (e.g., hg:threatens). 6.4
As we have discussed in Section 4, sbf and tbf adjust the area and the length of the blocks in which we divide the space and the time respectively. The bigger they get, the more and smaller blocks are created.
The optimal value for sbf depends on the distribution and the size of the geometries which are not known in advance in the case of our scenario. On the other hand, given the 19http://www.noa.gr 20http://www.eea.europa.eu/publications/COR0-landcover 21http://geodata.gov.gr metadata of the datasets, we can easily compute the optimal value for tbf . The temporal resolution of HG dataset is 15 minutes22, while the one of GAG and CLCG is a multiple of a year (e.g., 5 years). By constructing blocks with temporal dimension equal to 1 year, we can guarantee that, for all the pairs of entities of the datasets HG-GAG and HG-CLCG respectively which belong to the same block, the temporal relation intersects holds by design (i.e., we do not have to check it explicitly between each pair). Hence, the optimal value for tbf is 1 year. 6.5
Since we know the optimal value for tbf , in this experiment we try to approximate the optimal value for sbf . In order to achieve this, we analyze the performance of the single machine implementation of Silk with respect to di erent values of sbf . Particularly for this experiment, we use the full datasets of the scenario and we measure separately the computation times of HG-GAG and HG-CLCG. Furthermore, we count the total number of discovered links in each of these executions.
The graph of Figure 4(a) summarizes the results of this experiment. When sbf takes values close to 0, the blocks are spanning big surfaces of the earth. Hence, most of the geometries of the datasets are inserted in the same block, making the link discovery procedure almost as time consuming as the computation of the Cartesian product.
As sbf gets bigger, Silk seems to perform better. However, this improvement continues until a certain value (value 10) and then, as the sbf increases, the computation time deteriorates. This is due to the fact that a big value for sbf causes the division of space into very small blocks and thus each geometry is inserted into a big number of them. If two geometries are inserted into multiple blocks, then the check of the spatial relation is performed independently in each block that they appear. Hence, in this case we have redundant checks of the same relation that decrease the performance of Silk.
Another useful outcome from this experiment is the comparison of the time consumed for the link discovery task between HG-GAG and HG-CLCG. Figure 4(a) shows that the HG-CLCG interlinking takes orders of magnitude more than the respective HG-GAG. In Figure 3(b) we observe that the CLCG dataset has more geometries than GAG, whereas GAG has more complex ones (with respect to the number of points and not necessarily to their shape). Hence, in cases of spatial relations like intersects, the bottleneck is the number and not the complexity of the geometries.
One nal observation from this experiment is the number 22METEOSAT Second Generation (MSG) satellites return images every 15 minutes.
Links HG-GAG HG-CLCG 80000 79000 of discovered links. This number remains the same independently from the value of sbf . This is expected, since we have already proven in Section 4 that the Blocking technique that we propose does not a ect the accuracy of the discovered links which remains 100%. 6.6
In the second experiment we analyze the performance of three variants of Silk and Strabon with respect to di erent number of entities per dataset. For that reason, we use four di erent subsets of the datasets of the scenario23 and we measure the total execution time for performing the interlinking tasks i.e., we don't distinguish between HG-GAG and HG-CLCG.
The rst variant (Silk (Baseline)), which we consider as baseline, computes the full Cartesian product of the entities and then it checks if the spatiotemporal relation intersects holds between them. The second variant (Silk (Best sbf)), utilizes the Blocking technique with the best sbf , as the latter occurred from the previous experiment. The third one (Silk (MR)), is the distributed variant of Silk, which also utilizes the Blocking technique with the best sbf . In the case of Strabon, the datasets are stored locally and a CONSTRUCT query like the one we described in Figure 3(a) is performed.
The results of this experiment can be seen in Figure 4(b). As we can see from the graph, Silk (Baseline) is the most ine cient implementation, since even for the 1000 entities per dataset it is more time consuming that all the other implementations are for the full datasets.
On the other hand, Strabon seems to be faster for small number of entities per dataset whereas Silk (Best sbf) is faster when interlinking the full datasets. This happens because Silk fully utilizes the cores of the running machine by assigning the workload of each block it creates into a new thread. For big datasets, where the total workload is big enough, the Blocking approach of Silk seems to be the most e cient.
The e ect of the massive parallelization is more remarkable with the distributed variant of Silk (Silk (MR)). With 23The GAG dataset contains less than 1000 entities (Figure 3(b)) and thus for the third measurement of the experiment (Figure 4(b)) we used the full dataset. 10000 ) s nd 1000 o c e s (em 100 i T 10 1
Links Silk (Baseline) Silk (Best sbf) Strabon
Silk (MR) 10
100 1000* Entities per dataset
all (b) 10000 1000 100 10 1 s k n lif o # Silk (MR) the total workload is divided into di erent machines and in each machine it is divided into di erent cores. Also, we observe that, the computation time of Hadoop for small datasets is negligible with respect to the initialization time and the time consumed to copy the data from the local le system to the Hadoop Distributed File System (HDFS) and vice versa. Hence, Silk (MR) outperforms the other Silk variants and Strabon only for the measurement with the full datasets. Also, we can observe from the graph that it has the best scaling factor. Hence, we can claim that, for large datasets it is the only viable solution. 7.
In this paper, we proposed new methods for Spatial and Temporal Link Discovery and provided the rst implementation of our techniques based on the well-known framework Silk. Silk, enhanced with the new features, allows data publishers to generate a wide variety of spatial, temporal and spatiotemporal relations between their data and other Linked Open Data, dealing e ectively with the common heterogeneity issues of such data. Furthermore, we experimentally evaluated our implementation by using it in a real-world scenario, with datasets that comprise rich spatial and temporal information, and demonstrate that it discovers accurately all the existing links in a time e cient and scalable way.
Future work concentrates on extending Silk with more spatial and temporal relations. These relations will be based on algebras and calculi that appear frequently in the relevant bibliography and are useful for speci c use cases. We will also examine how we can estimate the optimal value of the blocking factor, for both the spatial and the temporal dimension, by posing preprocessing queries on the datasets that we want to interlink. Finally, we will try approximate blocking techniques which are more e cient than the one we propose but not 100% accurate. 8.
This work has been partially funded by the FP7 projects LEO (611141) (http://linkedeodata.eu) and MELODIES (603525) (http://www.melodiesproject.eu). We also want to thank Herve Caumont and Cesare Rossi from Terradue (http://www.terradue.com) for helping us conduct our experiments to a cloud environment.