Jean-François F Pineau
email: pineau@lirmm.fr

Yves Robert

Frédéric Vivien
email: frederic.vivien@ens-lyon.fr.

Energy-aware scheduling of bag-of-tasks applications on master-worker platforms

Keywords: Energy-aware, overhead, master-worker platforms, bi-criteria, steady-state scheduling

We consider the problem of scheduling an application composed of independent tasks on a fully heterogeneous master-worker platform with communication costs. We introduce a bi-criteria approach aiming at maximizing the throughput of the application while minimizing the energy consumed by participating resources. Assuming arbitrary superlinear power consumption laws, we investigate different models, with energy overheads and memory constraints. Building upon closed-form expressions for the uni-processor case, we derive asymptotically optimal solutions for all models.

Introduction

The Earth Simulator requires about 12 megawatts of peak power, and Petaflop systems may require 100 MW of power, nearly the output of a small power plant (300 MW). At $100 per Megawatt.Hour, peak operation of a Petaflop machine may thus cost $10,000 per hour [START_REF] Ge | Performance-constrained distributed DVS scheduling for scientific applications on power-aware clusters[END_REF]. And these figures ignore the additional cost of dedicated cooling. Current estimates state that cooling costs $1 to $3 per watt of heat dissipated [START_REF] Skadron | Temperatureaware microarchitecture: Modeling and implementation[END_REF]. This is just one of the many economical reasons why energy-aware scheduling is an important issue, even without considering batterypowered systems such as laptop and embedded systems.

Many important scheduling problems involve large collections of identical tasks [START_REF] Casanova | Grid Computing: Making The Global Infrastructure a Reality, chap[END_REF][START_REF] Adler | Optimal sharing of bags of tasks in heterogeneous clusters[END_REF]. In this paper, we consider a single bag-of-tasks application which is launched on a heterogeneous platform. We suppose that all processors have a discrete number of speeds (or modes) of • Under a refined energy-consumption model with overheads, we derive a polynomial algorithm which is asymptotically optimal, i.e. relatively closer to the optimal as the number of processed tasks increase.

• Adding memory constraints to overheads, we consider a model where processor memory is limited. Thus, if the worker runs slower than the desired throughput, it will be forced to switch to a faster mode when the memory will be full. In this context, we determined the best way to minimize the energy consumption while achieving a given throughput on one processor. This represents the first step to adapt our algorithm to this model.

This paper is organized as follows. We first present the framework and different energy consumption models in Section 2. We study the bi-criteria scheduling problem under the model with overheads in Section 3 , and under the more realistic (albeit more difficult) model with memory constraints in Section 4. Section 5 is devoted to an overview of related work. Finally, we state some concluding remarks in Section 6.

Framework

We outline the model for the target applications and platforms, as well as the characteristics of the consumption model. Next we formally state the bi-criteria optimization problem.

Application and platform model

We consider a bag-of-tasks application A, composed of a large number of independent, samesize tasks, to be deployed on a heterogeneous master-worker platform. We let ω be the amount of computation (expressed in flops) required to process a task, and δ be the volume of data (expressed in bytes) to be communicated for each task. We do not consider return messages. This simplifying hypothesis could be alleviated by considering longer messages (append the return message for a given task to the incoming message of the next one).

The master-worker platform, also called star network, or single-level tree in the literature, is composed of a master P master , the root of the tree, and p workers P u (1 ≤ u ≤ p). Without loss of generality, we assume that the master has no processing capability. Otherwise, we can simulate the computations of the master by adding an extra virtual worker paying no communication cost. The link between P master and P u has a bandwidth b u . We assume a linear cost model: it takes a time δ/b u to send a task to processor P u .

We suppose that the master can send/receive data to/from all workers at a given time-step according to the bounded multi-port model [START_REF] Hong | Distributed adaptive task allocation in heterogeneous computing environments to maximize throughput[END_REF][START_REF] Hong | Adaptive allocation of independent tasks to maximize throughput[END_REF]. There is a limit on the total amount of data that the master can send per time-unit. Intuitively, the bound corresponds to the bandwidth capacity of the master's network card; the flow of data out of the card can be either directed to a single link or split among several links, hence the multi-port hypothesis.

We also assume that computations obey the so-called synchronous start computation: the computation of a task on a worker can start at the same time as the reception of the task begins, provided that the computation rate is not greater than the communication rate (the communication must complete before the computation). This models the fact that, in several applications, only the first bytes of data are needed to start executing a task. In addition, the theoretical results of this paper are more easily expressed under this model, which provides an upper bound on the achievable performance. Furthermore, results in [START_REF] Pineau | Communication-aware scheduling on heterogeneous master-worker platforms[END_REF] show that proofs written under that model can be extended to more realistic models (one-port communication and atomic computation).

Energy model

Among the main system-level energy-saving techniques, Dynamic Voltage Scaling (DVS) works on a very simple principle: decrease the supply voltage (and hence the clock frequency) to the CPU so as to consume less power. For this reason, DVS is also called frequency-scaling or speed scaling [START_REF] Hotta | Profile-based optimization of power performance by using dynamic voltage scaling on a PC cluster[END_REF]. We assume a discrete voltage-scaling model. The computational speed of worker P u has to be picked among a limited number of m u modes. Computational speeds are denoted as s u,i , meaning that processor P u running in the ith mode (denoted by P u,i ) needs ω/s u,i time units to execute one task of A. We suppose that processing speeds are listed in increasing order (s u,1 ≤ s u,2 ≤ • • • ≤ s u,mu ), and that modes are exclusive: one processor can only run in a single mode at any given time.

Rather than assuming a relation of the form P d = s α where P d is the power dissipation, s the processor speed, and α some constant greater than 1, we adopt a more general approach, as we only assume that power consumption is a super-linear function (i.e., above the linear function f (x) = x and convex) of the processor speed. We denote by P [START_REF] Ge | Performance-constrained distributed DVS scheduling for scientific applications on power-aware clusters[END_REF] u,i the instantaneous power consumption (per time unit) of processor P u,i .

We focus on the following three energy consumption models. Under the ideal model, switching among the modes does not cost any penalty, and an idle processor does not consume any power. Consequently, for each processor P u , the energy consumption is super-linear from 0 to the power consumption at frequency s u,1 . In this model, the energy consumption is a linear function of the power consumption (P u,i (t) = P [START_REF] Ge | Performance-constrained distributed DVS scheduling for scientific applications on power-aware clusters[END_REF] u,i • t). This simpler model will be used in the proofs to get lower bounds on energy consumption.

Under the model with switching overheads, the processor pays a consumption penalty at each transition between two modes, this energy overhead depending on the modes; we denote by P (i → j) u the energy overhead to switch processor P u from mode i to mode j. In the literature [START_REF] Martin | Combined dynamic voltage scaling and adaptive body biasing for lower power microprocessors under dynamic workloads[END_REF][START_REF] Andrei | Overhead-conscious voltage selection for dynamic and leakage energy reduction of time-constrained systems[END_REF], authors often state that overheads are proportional to the square of the voltage difference between both modes, and they use such a relationship. Instead, in this work we aim at keeping more general assumptions, as long as they are consistent with the superlinearity of power consumption functions. Therefore we assume that overheads are super-linear functions of the difference in power consumption between both modes:

P (i → j) u = β u P [1] u,j -P [1] u,i (0 ≤ i < j ≤ m u )
(with β u a super-linear function depending on the processor). Furthermore, as P [START_REF] Ge | Performance-constrained distributed DVS scheduling for scientific applications on power-aware clusters[END_REF] u is superlinear, we know that the following properties hold (0

≤ i ≤ j ≤ k ≤ l ≤ m u ):
non-decreasing behavior: P

(j → k) u ≤ P (i → k) u
, and P

(j → k) u ≤ P (j → l) u triangular inequality: P (i → k) u ≤ P (i → j) u + P (j → k) u
, super-linearity:

P (i → j) u + P (j → l) u ≥ P (i → k) u + P (k → l) u
.

Under this more realistic model, energy consumption now depends upon the duration of the interval during which the processor is operating at a given mode, and on the processor's previous mode (the overhead is only paid once during this interval). Under this model, the energy consumption is an affine function of the power consumption:

P u,i (t) = P (j → i) u + P [1] u,i • t. (1)
We also suppose in this model that there are no memory constraints, and that a processor can receive data while turned off. To understand the last point, one can consider multi-core processors. If at least one core is turned on, then other cores can be turned off and still have some data sent to their memory. This way, cores will have data to process as soon as they are turned on.

Under the last model with memory constraints, we suppose that all processors have limited memory, and that they must be turned on to receive any data. This is the most complicated model, but also the most realistic.

Objective function

Our goal is bi-criteria scheduling: the first objective is to minimize the energy consumption, and the second to maximize the throughput. We decided to solve this bi-criteria problem by bounding one parameter: the throughput. We denote by ρ u,i the throughput of worker P u,i for application A under a specific schedule, i.e., the average number of tasks the schedule wants P u to execute using mode i per time-unit. There is a limit to the number of tasks that each processor mode can perform per time-unit. First of all, because P u,i runs at speed s u,i , it cannot execute more than s u,i /ω tasks per time-unit. Second, since P u can only be at one mode at a time, and given that ρu,i ω su,i represents the fraction of time spent under mode m u,i per time-unit, this constraint can be expressed by:

∀ u ∈ [1..p], mu i=1 ρ u,i ω s u,i ≤ 1.
We add an additional idle mode P u,0 , whose speed is s u,0 = 0. As the power consumption per time-unit of P u,i , when fully used, is

P [1]
u,i (P

[1]
u,0 = 0), its power consumption per time-unit with a throughput of ρ u,i is then

ρ u,i ω s u,i P [1]
u,i (note that we do not take into account the energy overhead needed to get P u to mode i). We denote by ρ u the throughput of worker P u , i.e., the sum of the throughput of each mode of P u (except the throughput of the idle mode). The total throughput of the platform is denoted by:

ρ = p u=1 ρ u = p u=1 mu i=1 ρ u,i .
We define problem MinPower(ρ) as the problem of minimizing the energy consumption while achieving a throughput ρ. In Section 2.4 we summarize previous results under the ideal model. We extend them to more realistic models in Sections 3 and 4.

Ideal model

Both bi-criteria problems (maximizing the throughput given an upper bound on energy consumption, and minimizing the energy consumption given a lower bound on throughput) have been studied at the processor level, using particular power consumption laws such as P d = s α [START_REF] Albers | Energy-efficient algorithms for flow time minimization[END_REF][START_REF] Bansal | Dynamic speed scaling to manage energy and temperature[END_REF][START_REF] Bunde | Power-aware scheduling for makespan and flow[END_REF]. We provided an optimal solution to these problems in [START_REF] Pineau | Energy-aware scheduling of flow applications on master-worker platforms[END_REF][START_REF] Pineau | Energy-aware scheduling of flow applications on master-worker platforms[END_REF], using the sole assumption that the power consumption is super-linear. A key step is to establish closed-form formulas linking power consumption and throughput on a single processor: Proposition 1. Under the ideal energy consumption model, for any processor P u , the optimal power consumption to achieve a throughput of ρ (0

< ρ ≤ su,m u ω ) is P u (ρ) = max 0≤i<mu (ωρ -s u,i ) P [1] u,i+1 -P [1] u,i s u,i+1 -s u,i + P [1] u,i ,
and it is obtained using two consecutive modes, P u,i0 and P u,i0+1 , such that

su,i 0 ω < ρ ≤ su,i 0 +1 ω .
Note that a similar result is given in [START_REF] Pineau | Energy-aware scheduling of flow applications on master-worker platforms[END_REF][START_REF] Pineau | Energy-aware scheduling of flow applications on master-worker platforms[END_REF] for the converse problem, namely maximizing the throughout subject to a prescribed bound on power consumption. Thanks to Proposition 1, there is no need to specify the throughput for each frequency on any given processor. One only has to fix a throughput for each processor to know how to achieve the minimum power consumption on that processor. Informally, the power minimization algorithm in [START_REF] Pineau | Energy-aware scheduling of flow applications on master-worker platforms[END_REF][START_REF] Pineau | Energy-aware scheduling of flow applications on master-worker platforms[END_REF] sorts processors in non-decreasing order according to their power consumption ratio. This power consumption ratio depends on the different processor modes, and the same processor appears a number of times equal to its number of modes. Formally, the quantities

P [1] u,i+1 -P [1] u,i
s u,i+1 -s u,i are sorted in non-decreasing order, and the cheapest modes of the processors are selected so that the system can achieve the required throughput. The constraints are that each processor throughput is limited by its maximal frequency, and by the bandwidth of the link between itself and the master. Altogether, this leads to Algorithm 1.

Algorithm 1: Greedy algorithm minimizing power consumption under a given throughput Input: throughput ρ that has to be achieved for u = 1 to p do T [u] ← 0; /* throughput of processor Pu */ Φ ← 0; /* total throughput of the system */ L ← sorted list of the P u k ,i k such that ∀ j,

P [1] uj ,1+ij -P [1] uj ,ij s uj ,1+ij -s uj ,ij ≤ P [1] uj+1,1+ij+1 -P [1] uj+1,ij+1 s uj+1,1+ij+1 -s uj+1,ij+1 ; while Φ < ρ do P u k ,i k ← next(L); /* selection of next cheapest mode */ ρ ← T [u k ]; /* previous throughput of Pu k (at mode i k -1) */ T [u k ] ← min su k ,i k ω ; bu k δ ; ρ + (ρ -Φ) ; /* new throughput of Pu k (at mode i k ) */ if T [u k ] = bu k δ then L ← L\{P u k ,j }; /* no need to look at faster modes for Pu k */ Φ ← Φ + T [u k ] -ρ ;
Suppose that the last selected mode in Algorithm 1 is P u k 0 ,i k 0 . Then:

1. each processor having at least one mode consuming strictly less than P u k 0 ,i k 0 is fully used, either at the throughput of the bandwidth if reached (this throughput is achieved according to Proposition 1), or at the largest single fastest mode that consumes strictly less than P u k 0 ,i k 0 , or at the same mode than P u k 0 ,i k 0 ;

2. any processor whose first non-trivial mode consumes exactly the same as P u k 0 ,i k 0 is either not used at all, or fully used at its first non-trivial mode;

3. any processor whose first non-trivial mode consumes strictly more than the mode P u k 0 ,i k 0 is not used at all; 4. P u k 0 ,i k 0 is used at the minimum throughput such that the system achieves a throughput of ρ (according to Proposition 1).

This algorithm was proven optimal [START_REF] Pineau | Energy-aware scheduling of flow applications on master-worker platforms[END_REF][START_REF] Pineau | Energy-aware scheduling of flow applications on master-worker platforms[END_REF] to solve problem MinPower(ρ) under the ideal model, and asymptotically optimal under a model where an overhead is paid each time a processor is turned on. In the next sections, we extend this algorithm and assess its performance under more restrictive models.

Model with switching overheads

When we move to more realistic models, the problem gets much more complicated. In this section, we still look at the problem of minimizing the energy consumption of the system with a throughput bound, but now we suppose that there is an energy consumption overhead when switching the mode of a processor. We denote this problem as MinPowerOverhead(ρ). Recall that we do not suppose any memory constraint in this section: the memory of each processor is supposed to be infinite.

To take the switching overhead into account, we suppose that at time 0, P u is in mode 0, and it must be in mode 0 again at time t. We then define the following behavior on every processor P u in order to achieve a throughput of ρ u during t time units; if the throughput is feasible, we know that ρ u ≤ min s u,mu ω ; b u δ , so ωρ u is between two consecutive modes:

s u,i0 < ωρ u ≤ s u,i0+1
. We would like to use both modes, according to the results of [START_REF] Pineau | Energy-aware scheduling of flow applications on master-worker platforms[END_REF][START_REF] Pineau | Energy-aware scheduling of flow applications on master-worker platforms[END_REF] for the ideal energy consumption model: running mode P u,i0 during

t 1 = t(s u,i0+1 -ρ u ω) s u,i0+1 -s u,i0
time units, and mode P u,i0+1 during t 2 = t(ρ u ω -s u,i0 ) s u,i0+1 -s u,i0 time units. But the presence of an overhead when switching from P u,i0 to P u,i0+1 may cost more energy than staying at mode P u,i0+1 : this may happen if ωρ u is very close to s u,i0+1 , or if t is small. Then the best solution may be to use processor P u in mode i 0 + 1 during the last t = t ρ u ω s u,i0+1 time units, after staying at mode 0 (it can still receive data while turned off) during the first (t -t ) time unit. Overall, the energy consumption of P u during t time units is:

P u (t, ρ u ) = min    P (0 → i0) u + P [1] u,i0 • t 1 + P (i0 → i0+1) u + P [1] u,i0+1 • t 2 + P (i0+1 → 0) u P (0 → i0+1) u + P [1] u,i0+1 • t + P (i0+1 → 0) u (2)
Thanks to the properties of overheads (see Section 2.2), we can prove the following result:

Proposition 2. For any processor P u , the optimal energy consumption to achieve a throughput of ρ (0 < ρ ≤ su,m u ω ) during t time units, is obtained either by using the two consecutive modes that surround ωρ, or by using only the first mode not smaller than ωρ.

Proof Let S be an optimal solution to achieve a throughput of ρ during t time units, and let i 0 and i 0 + 1 be the two consecutive modes that surround ωρ (s u,i0 ≤ ωρ ≤ s u,i0+1 ). Then, we have two cases: S uses only one mode: this mode is greater than (or equal to) i 0 + 1, otherwise ρ cannot be achieved. Among all possible modes, the overhead to switch P u from mode 0 to i 0 + 1 is the smallest (overheads are increasing), and the power consumption at this mode is also the smallest (as P [START_REF] Ge | Performance-constrained distributed DVS scheduling for scientific applications on power-aware clusters[END_REF] u is super-linear, t P [START_REF] Ge | Performance-constrained distributed DVS scheduling for scientific applications on power-aware clusters[END_REF] u,i0+1 = tρ u ω

P [1] u,i0+1 s u,i0+1 ≤ tρ u ω P [1] u,i s u,i , ∀i ≥ i 0 + 1).
S uses more than one mode: one of these modes i max has to be greater than (or equal to) i 0 + 1 (as S is feasible), another (i min ) has to be lower or equal to i 0 (otherwise our solution solutions for problem MinPowerOverhead(ρ) when d becomes large. Indeed we derive the following result:

Theorem 1. Algorithm 2 is asymptotically optimal for problem MinPowerOverhead(ρ).

Proof If the application A is composed of N tasks, the optimal scheduling time will be T = N ρ , where ρ is the throughput bound. We denote by P opt the optimal energy consumption that would be obtained under the ideal model, P * the optimal energy consumption that can be achieved under the model with switching overheads, and P the energy consumption given by Algorithm 2.

As the model with overheads is more constrained than the ideal model, the minimum energy consumption under this model is greater than under the ideal model, so we have P opt ≤ P * ≤ P. Also, one can remark that, during d time units, the solution given by Algorithm 2 does not consume more energy than the solution given by Algorithm 1 where overhead costs are added.

To prove this last claim, let S be the solution given by Algorithm 2, and S be the solution given by Algorithm 1. If both algorithms do not select the same modes, because they achieve the exact same throughput, then one processor P imin has a throughput in S lower than in S (ρ imin ≤ ρ imin ), and another processor P imax has a throughput in S greater than in S (ρ imax ≥ ρ imax ). According to the selection of the modes in Algorithm 2, we know that, during d time units, P imax consumes no more power at a throughput of ρ imax than P imin at a throughput of ρ imin . So we can build a new solution from S , where P imin gives a fraction of its work to P imax until one of these processors reaches its next (or previous) mode. This new solution will consume no more power than S . If we repeat this exchange pattern, we prove that the solution given by Algorithm 2 consumes no more than the solution given by Algorithm 1.

Next we observe that the solution given by Algorithm 1 under the model with overheads will only pay at most three overheads for each processor, during d time units (two if the processor is in an exact mode, three otherwise). Thus, if we denote by P [START_REF] Skadron | Temperatureaware microarchitecture: Modeling and implementation[END_REF] u the maximum overhead P u can pay during t time units, we have:

P(t) ≤ P opt • t + 3 • t d • p u=1 P [2] u ≤ P opt • t + 3 • t d • p • p max u=1
P [2] u .

If we fix d = √ T , we have

P(T ) ≤ P * • T + 1 + √ T • 3p • p max u=1 P [2] u . (4)
Then, we compare P and P * during the scheduling of the N tasks of application A. We use the optimal power consumption times the T time units as a lower bound of the optimal energy consumption during this T time units, (i.e., P * (T ) ≥ P * • T ), and we obtain:

P(T ) P * (T ) ≤ 1 + 1 T + 1 √ T 3p • p max u=1 P [2] u P * ≤ 1 + O 1 √ T .
which achieves the proof of the asymptotic optimality of Algorithm 2.

Copyright P (2) P (2) P (1) P ( 1)

Pk 1 Pk j1 Pk j1 +1 Pk j2 Pk j3 tk j1 tk j2 Pi 0+1 Pi 0 S S of S of S Figure 1.
From modes of P (1) and P (2) to Pu,i 0

• S uses only one mode: this mode is greater than (or equal to) i 0 + 1, otherwise ρ cannot be achieved. Among all possible modes, the overhead to switch P u from mode 0 to i 0 + 1 is the smallest (overheads are increasing), and the power consumption at this mode is also the smallest (as P [START_REF] Ge | Performance-constrained distributed DVS scheduling for scientific applications on power-aware clusters[END_REF] u is super-linear). Furthermore, as the mode speed is greater than the throughput bound, the memory is never used to buffer data for later processing.

• S uses more than one mode: because of the memory bound, S uses its modes alternatively during the t time-units. Let call P u,k1 , • • • , P u,k K the different modes used successively (some may be the same), with P u,k1 used during the first t k1 time-units, P u,k2 used during the next t k2 time-units, and so on. We have K j=1 t kj = t. We split the list of modes used by S in two, depending on whether the mode is slower or faster than P u,i0 :

P (1) = P u,kj |1 ≤ j ≤ K, k j ≤ i 0 , P (2) = P u,kj |1 ≤ j ≤ K, k j > i 0 .
As S is feasible, we know that the memory is empty at times 0 and t, and is never overfilled during the whole interval. From that optimal solution, we build another solution, S .

• We gather all the first modes of S that belong to P (2) : P u,k1 • • • P u,kj 1 ∈ P (2) , P u,kj 1 +1 ∈ P (1) . As the memory is empty at time 0, and these modes are faster than the throughput bound, we replace them in S by P u,i0+1 . The power consumption under this mode is lesser, we pay fewer overheads (only two switching overheads instead of j 1 + 1), and the overhead is smaller from P 0 to P u,i0+1 than to P u,k1 , and from P u,i0+1 to P u,kj 1 +1 than from P u,kj 1 (because the first modes of S are in P (2) and P u,kj 1 +1 is in P (1) ).

• (Figure 4). From this time kj 1 j=1 t kj = t k 1 on, we use P u,i0 in S continuously. As the next modes of S belongs to P (1) , and S is feasible, and P u,i0 is faster than the modes of P (1) , then the memory is less filled in S than in S until time kj 2 j=1 t kj . Then, as the memory state function is continuous and upper bounded, and as this function is strictly increasing under S (it uses P u,i0 continuously), we know that there exists a time, denoted by t k 2 , when the memory state of S will be the same as the one of S . At this time, S stops to use P u,i0 and uses the same next modes than S. From time t k 1 to t k 2 , both schedules have achieved the same amount of work, and they have the same communication rate, and the same memory state at time t k 1 and t k 2 ), so they have the same average throughput during this interval. This average throughput is achieved under S by only using P u,i0 continuously, whereas S uses modes of P (1) and P (2) . According to our previous work on the ideal model [START_REF] Pineau | Energy-aware scheduling of flow applications on master-worker platforms[END_REF], we know that the power consumption of S is then smaller than one of S. Furthermore, S pays less overheads than S (only two, instead of k j2 -k j1 + 1 in S), and smaller overheads (thanks to the non-decreasing behavior of the overhead function). We repeat this pattern for all sets of modes of P (1) in S.

• At this step, S is only composed of P u,i0 and modes of P (2) . The next step is to build another schedule S which splits the work of modes of P (2) among P u,i0 and P u,i0+1 . If we look at the memory state backwards, we face a similar case as previously; because the memory state at the end of the t time units is the same for both schedules, and since P u,i0+1 cleans the memory slower than modes of P (2) , then the memory is less filled under S than under S . So there exists a time when both schedule had the same memory state, which defines the time window to use P u,i0+1 in S . During this time window, S does not consume more energy than S , so we can replace each mode of P (2) in S by P u,i0+1 in S .

• Now S is an optimal schedule that uses only P u,i0 and P u,i0+1 . We will gather the utilization of P u,i0 and P u,i0+1 to fully fill and empty the memory, starting with P u,i0 . The power consumption will not change, because the modes will be used the same average time, and the number of switching overheads will not increase. Overall, this scheduling (which is the one defined at the beginning of the section) is optimal.

Altogether, Proposition 3 only is a first step towards designing an efficient schedule for a master-worker platform that obeys the fully realistic model that is dealt with in this section. Indeed, it remains to decide which fraction of the total load should be assigned to each worker, and at which throughput. But Proposition 3 provides the optimum solution for each worker to execute its prescribed share of the work.

Related Work

Several papers have been targeting the minimization of power consumption. Most of them suppose that processors can switch to arbitrary speed values.

• Unit time tasks. Bunde [START_REF] Bunde | Power-aware scheduling for makespan and flow[END_REF] focuses on the problem of offline scheduling unit time tasks with release dates, while minimizing the makespan or the total flow time on one processor. He extends his work from one processor to multi-processors, but unlike this paper, does not take any communication time into account. He also proves the NP-completeness of the problem of minimizing the makespan on multi-processors with jobs of different amount of work. Authors in [START_REF] Albers | Energy-efficient algorithms for flow time minimization[END_REF] concentrate on minimizing the total flow time of unit time jobs with release dates on one processor. After proving that no online algorithm can achieve a constant competitive ratio if job have arbitrary sizes, they exhibit a constant competitive online algorithm and solve the offline problem in polynomial time. Contrarily to [START_REF] Bunde | Power-aware scheduling for makespan and flow[END_REF] where tasks are gathered into blocks and scheduled with increasing speed in order to minimize the makespan, here the authors prove that the speed of the blocks needs to be decreasing in order to minimize both total flow time and energy consumption. Bansal et al [START_REF] Bansal | Speed scaling for weighted flow time[END_REF] improved a part of this work and gave algorithms for the more general problem with arbitrary jobs.

• Communication-aware. In [START_REF] Varatkar | Communication-aware task scheduling and voltage selection for total systems energy minimization[END_REF], the authors are interested about scheduling task graphs with data dependencies while minimizing the energy consumption of both the processors and the inter-processor communication devices. They demonstrate that in the context of multiprocessor systems, inter-processor communications are an important source of energy consumption, and their algorithm reduces up to 80% of the communications. They focus on multiprocessor problems, and consider the energy consumption of the communications, while assuming the communication times negligible compared to the computation times.

• Discrete voltage case. In [START_REF] Ishihara | Voltage scheduling problem for dynamically variable voltage processors[END_REF], the authors deal with the problem of scheduling tasks on a single processor with discrete voltages. They also look at the model where the energy consumption is related to the task, and describe how to split the voltage for each task. They extend their work in [START_REF] Okuma | Real-time task scheduling for a variable voltage processor[END_REF] to online problems. In [START_REF] Zhang | Energy minimization of real-time tasks on variable voltage processors with transition energy overhead[END_REF], the authors add the constraint that the voltage can only be changed at each cycle of every task, in order to limit the number of transitions and thus the energy overhead. They find that under this model, the minimal number of frequency transitions in order to minimize the energy may be greater than two.

• Deadlines. In [START_REF] Quan | Energy efficient fixed-priority scheduling for real-time systems on variable voltage processors[END_REF], the authors focus on the problem where tasks arrive according to some release dates. They show that during any elementary time interval defined by some release dates and deadlines of applications, the optimal voltage is constant, and they determine this voltage, as well as the minimum constant speed for each job. [START_REF] Bansal | Dynamic speed scaling to manage energy and temperature[END_REF] improves the best known competitive ratio to minimize the energy while respecting all deadlines. [START_REF] Chan | Energy efficient online deadline scheduling[END_REF] works with an overloaded processor (which means that no algorithm can finish all the jobs) and tries to maximize the throughput. Their online algorithm is O(1) competitive for both throughput maximization and energy minimization. [START_REF] Chen | Energy-efficient real-time task scheduling with task rejection[END_REF] has a similar approach by allowing task rejection, and proves the NP-hardness of the problem under study.

• Slack sharing. In [START_REF] Zhu | Scheduling with dynamic voltage/speed adjustment using slack reclamation in multiprocessor real-time systems[END_REF][START_REF] Rusu | Multi-version scheduling in rechargeable energy-aware real-time systems[END_REF], the authors investigate dynamic scheduling. They consider the problem of scheduling DAGs before deadlines, using a semi-clairvoyant model. For each task, the only information available is the worst-case execution time. Their algorithm operates in two steps: first a greedy static algorithm schedules the tasks on the processors according to their worst-case execution times and the deadline, and reduces the processor speeds so that each processor meets the deadline. Then, if a task ends sooner than according to the static algorithm, a dynamic slack sharing algorithm uses the extra-time to reduce the speed of computations for the following tasks. However, they do not take communications into account.

• Heterogeneous multiprocessor systems. Authors in [START_REF] Chen | Energy-efficient task partition for periodic real-time tasks on platforms with dual processing elements[END_REF] study the problem of scheduling real-time tasks on two heterogeneous processors. They provide a FPTAS to derive a solution very close to the optimal energy consumption with a reasonable complexity. In [START_REF] Huang | A near-optimal solution for the heterogeneous multi-processor single-level voltage setup problem[END_REF], the authors propose a greedy algorithm based on affinity to assign frame-based real-time tasks, and then they re-assign them in pseudo-polynomial time when any processing speed can be assigned for a processor. Authors of [START_REF] Yu | Power-aware resource allocation for independent tasks in heterogeneous real-time systems[END_REF] propose an algorithm based on integer linear programming to minimize the energy consumption without guarantees on the schedulability of a derived solution for systems with discrete voltage. Finally, [START_REF] Chen | Allocation cost minimization for periodic hard real-time tasks in energy-constrained dvs systems[END_REF][START_REF] Hsu | Multiprocessor synthesis for periodic hard real-time tasks under a given energy constraint[END_REF] explored the search of approximation algorithms to minimize processor allocation cost under energy constraints.

• Overheads. In [START_REF] Martin | Combined dynamic voltage scaling and adaptive body biasing for lower power microprocessors under dynamic workloads[END_REF], the authors consider the scheduling of DAGs, while optimizing both dynamic power consumption and leakage power consumption. Their algorithm trades energy consumption and task execution time. In [START_REF] Andrei | Overhead-conscious voltage selection for dynamic and leakage energy reduction of time-constrained systems[END_REF], the authors also consider the execution of tasks with dependencies. They take transition overheads into account, and prove complexity results: the discrete voltage scaling problems, with and without overheads (as in Sections 3 and 2.4), are strongly NP-hard, while continuous voltage scaling can be solved in polynomial time.

Conclusion

In this paper, we have dealt with the problem of scheduling a bag-of-tasks application on a heterogeneous master-worker platform, with minimal energy consumption. Our study takes transition overheads and memory constraints into account. Starting from an optimal algorithm under an ideal model without overhead nor memory constraint, we were able to provide an asymptotically optimal solution for the former extension, with transition overheads. Adding memory constraint, we have derived an important property characterizing how to efficiently achieve a target throughput. We hope that our results will provide a sound theoretical basis for forthcoming studies.

As future work, it would be interesting to study the absolute performance of our algorithm under the new models, in order to assess whether its performance can be guaranteed within a given bound from the optimal. It would also be interesting to test our algorithm through some simulations and actual experiments. We intend to use the Grid5000 testbed [START_REF] Cappello | Grid'5000: A large scale, reconfigurable, controlable and monitorable grid platform[END_REF] as we have on-line access to the electrical consumption of the clusters. Even if individual consumption of the nodes is not available (only groups of nodes), we hope to see if there are any major difference between our model forecasts and the actual consumption of the nodes.

This work was supported in part by the ANR StochaGrid project.

does not consume more energy). Thanks to overhead properties, we know that the total cost of overheads in S, denoted as P overhead u , is:

u (even if S uses more than two modes, due to the triangular inequality) ≥ P (0 → imin) u + P (imin → i0+1) u + P (i0+1 → 0) u because i max is greater than (or equal to) i 0 + 1 ≥ P (0 → i0) u + P (i0 → i0+1) u + P (i0+1 → 0) u (due to the super-linearity) Moreover, as P [1] is super-linear, we know that the power consumption is smaller when using only modes i 0 and i 0 + 1 rather than any other (see the proof of Proposition 1 in [START_REF] Pineau | Energy-aware scheduling of flow applications on master-worker platforms[END_REF] for details). Overall, our solution does not consume more energy than S, which concludes the proof.

If we rewrite Equation ( 2) by replacing t 1 , t 2 , and t by their values, we can express the energy consumption as a function of the throughput:

As we are using the same two modes for the same duration as under the ideal model, we see that Equation (3) is very close to the formula described in Proposition 1. We simply add the energy overhead if using these two modes, and we compare it to the energy consumption of the faster mode. Using these new results, we can modify Algorithm 1. The general principle of the approach is as follows: instead of looking at the power consumption per time-unit, we look at the energy consumed during d time units, where d will be defined later. We still take into account the possibility that the worker is bandwidth limited in a separated step.

Algorithm 2: Greedy algorithm minimizing energy consumption under overheads Data: throughput ρ that has to be achieved Sort in non-decreasing order all the modes of the system P u k ,i k , except those greater than bu k δ , according to the values

Insert one additional mode with a speed of ωb u k /δ per processor while the throughput ρ is not achieved do Select the next cheapest processor Increase its throughput to meet its next mode

If we consider an ideal model, i.e., where no overheads are paid, then Algorithm 2 behaves like Algorithm 1. Hence, we expect solutions built by Algorithm 2 to become good approximate

Model with memory constraints

In this section, we consider the model with memory constraints. In addition to paying overheads when switching modes, each processor now has a limited memory, and cannot receive any data whenever turned off. Memory constraints will force each processor to run at a throughput different from one of its own modes, and to switch from its slower mode to its faster mode regularly, when its memory becomes full. Our goal is to provide an optimal single-processor policy for achieving a target throughput ρ: assuming that the data steadily arrives at rate ρ, which modes should be used to minimize energy consumption while meeting the memory constraint?

Let M u be the memory bound of P u . We suppose that at time 0, P u is at mode 0, with no data in its memory, and it must return into that state at time t.

If the throughput is feasible, we know that ρ u ≤ min s u,mu ω ; b u δ , and s u,i0 < ωρ u ≤ s u,i0+1 .

Our strategy is to run the slowest mode P u,i0 first, in order to accumulate data into memory.

As δ represents the size of one task, ρ u -su,i 0 ω

is the throughput at which the tasks are accumulating into the memory under mode i 0 , and su,i 0 +1 ω -ρ u is the throughput at which the memory is cleaned under mode i 0 + 1. After t 1 time-units under mode P u,i0 , the memory will be full, and we have to switch to the mode P u,i0+1 during t 2 time-units until the memory is emptied. We will then repeat this pattern. The values of t 1 and t 2 are given by:

If the memory size is large enough and does not impose any constraint during t times units, or if the remaining time is too small to fill the memory, then t 1 and t 2 will be calculated the same way as t 1 and t 2 in Section 3.

As in the previous section, the overhead when switching from P u,i0 to P u,i0+1 may cost more energy than staying at mode P u,i0+1 . Hence we still have to compare the energy consumption of using P u,i0 and P u,i0+1 for the whole t time units and for the computation of last tasks (when there is no enough time to fill the memory) with the energy consumption of staying at mode P u,i0+1 during the corresponding time units.

Overall, the new formula expressing the energy consumption of P u during t time-units is much more complicated. However, we can prove that the optimal way to achieve a given throughput is to use these two modes exclusively: Proposition 3. For any processor P u with a memory bound of M u , the optimal energy consumption to achieve a target throughput ρ during t time-units, where ρ also is the data arrival rate and verifies 0 < ρ ≤ su,m u ω , is obtained either by using the two consecutive modes that surround ωρ, or by using exclusively the first mode not smaller than ωρ.

Proof Let S be an optimal solution to achieve a throughput ρ during t time-units, and let i 0 and i 0 + 1 be the two consecutive modes that surround ωρ (s u,i0 < ωρ ≤ s u,i0+1 ). Then, we have two cases:


Nathalie Abadie

Bénédicte Bucher

EURECOM Raphaël Troncy

Jérôme Euzenat
email: jerome.euzenat@inria.fr

Keywords: data interlinking, linked data, instance matching

This report presents the first version of the interlinking module for the Datalift platform as well as strategies for future developments.

Executive Summary

This document describes the first version of the data interlinking module on the Datalift platform.

We have chosen to integrate the Silk tool developed by the Frei Universität Berlin within the platform because it has already been broadly used and this is a maintained and opensource tool. So, we first briefly describe Silk and other components that may be useful within the data interlinking module.

Silk is a script-based tool: one has to write a script in the Silk-SL language telling Silk where and how to find links in the datasets. We present a script that can be used within the Datalift platform. We describe briefly how we have built the module around Silk and how Silk can take its data from the triple stores of the Datalift platform and how it can output the generated links in the platform's triple store as well. Of course, the module can still take its data out of the platform.

We also explain how we plan to extend this module so that it can go beyond Silk. This may be achieved in two different and complementary ways:

-by integrating modules within Silk that provides new interlinking methods or new ways to interlink; -by automatically generating Silk scripts from our analysis to the data to be interlinked. So, we describe two additional Silk modules that can be defined for matching time (events) and geographical data. We also explain how, from ontology alignment expressed in the expressive language EDOAL, it can be possible to generate links or Silk scripts that take advantage of the content of alignments. This is what we will concentrate on, in the first part of the second year.

Table of Contents

Introduction

This deliverable presents the design of the interlinking module of the Datalift platform.

There are lots of isolated RDF data sets being published everyday. A web of linked RDF data set is highly required for web users to share information with each other. For that purpose, the dataset published from the Datalift platform must be linked to other, likely external, datasets. It is the purpose of the interlinking module to propose this feature.

We decided to provide more context to the actual prototype by considering tools that could be used for the module as well as peripheral tools. We also provide information about how this module is supposed to develop in the future through extensions.

Hence, this deliverable discusses existing tools that we may reuse in the platform ( §2). Existing linking algorithms are, for their part, the object of Deliverable D4.1. We then briefly motivate the choice that has been made for the implementation of the module and give a general view of how this implementation will be developed ( §3). We describe the current implementation and its capabilities ( §4). Finally we present the blueprint for future work: implementing specialised Silk plug-in that may be used with the dataset considered in the Datalift project ( §5) and discussing how to use alignments for generating Silk specifications ( §6).

Context

In this chapter, we describe in some details existing tools that may be used in the platform or with the platform. This description may skip and the reader may come back to it if he or she needs more contextual information.

We describe mainly two tools: Silk ( §2.1.1), a system for establishing links among data sources, and MDR ( §2.2) a system for manipulating data sources which may ultimately be used for generating Silk scripts (manually). Since MDR may use an alignment server, we briefly present one ( §2.3). Even if MDR is not used within the platform, Alignment servers may be used to retrieve alignments prior to interlinking data.

Silk

Silk1 , or the Silk Link Discovery Engine, is also described and compared to other tools in Deliverable D4.1. It is an interlinking software that helps to find out similar items in RDF data sets. It accepts RDF data sets both in file and in SPARQL endpoint. After interlinking computation, it produces RDF link set both in file and in SPARQL endpoint.

In order to fulfill the interlinking computation, Silk needs the specification of several information. They are, -the concepts from which to find the similar items, -the properties of the concepts upon which to match the similar items, -the techniques that are used to match the properties' values, and -the threshold of linking or not.

All these information are specified in a link specification file. Silk will run such file to produce link sets between different data sets.

Silk provides different variants for their functions. They are, -Silk Single Machine, which is used to produce RDF links on a single machine, -Silk MapReduce, which is used to deploy Silk on groups of machines and -Silk Server, which acts as an identity resolution module in any application background that checks whether there are new links arising when new RDF data sets are coming.

Silk also provides a workbench to produce the link specification file.

In what follows, we embedded Silk Single Machine in the Datalift interlinking module. However, we may use the other settings.

Silk-LSL: a linking specification language

Below is a Silk-LSL specification to interlink cities in the two data sets DBpedia (http://dbpedia.org/ontology/ and Geonames (http://www.geonames.org/ontology#) [START_REF] Bizer | Silk -a link discovery framework for the web of data[END_REF]: path="?a/dbpedia:populationTotal" /> <Param name="num2" path="?b/gn:population" /> </Compare> </AVG> </LinkCondition> <Thresholds accept="0.9" verify="0.7" /> <Output acceptedLinks="accepted_links.n3" verifyLinks="verify_links.n3" mode="truncate" /> </Interlink>

</Silk>

This specification fulfills two roles:

-It is an alignment: it specifies the classes in which entities to link can be found.

Restrictions to dbpedia:City and gn:P are in fact an alignment between these two concepts. Similarly, the compared properties dbpedia:populationTotal and gn:population and rdfs:label and gn:name, respectively provide the correspondences between properties.

-It specifies how to link entities. Indeed, what Silk brings in addition to an alignment is the specification of how to decide if two entities should be linked: when the average (AVG) of their respective distances (Compare) is over a threshold (Threshold, there are two thresholds, one for accepting automatically the equivalence and one for drawing the attention of a user).

Data management tool

The Data management tool of Michael Luger (U. Innsbruck) is a tool for navigating and interlinking datasets graphically. It allows for:

-interactively displaying pairs of datasets and select properties to compare; -using ontology alignments from an Alignment server to identify properties to compare; -analysing the datasets in order to establish keys; -matching datasets (work in progress).

This tool could be used in parallel of the platform in order to analyse datasets or it could be integrated within the platform. The Alignment view (see Figure 2.1) displays all the classes and properties of the two datasets and offers features to deal with schema alignments and dataset analysis. Its purpose is the discovery of information about the datasets, in particular possible schema-level correspondences which are suitable restrictions for the Matcher, i.e., candidate selection.

There are two reasons for creating an Alignment view separate from the Dataset Explorer:

-The selection of resources serves a different purpose, so it will not trigger the dataset filtering SPARQL queries as in the Dataset Explorer. -The features that are part of this view would clutter the interface too much, when combined with the browsing feature.

Upon activating this view, an Alignment server [START_REF] David | The alignment api 4.0[END_REF] is checked for schema alignments, and the schema alignments are then displayed both inline and in the bottom left corner (each pair of table cell's color increases the hue of a base color). These alignments can be selected for restricting the input of the Matcher view.

When selecting two classes or two properties from each of the two schema-views, they will show up at the bottom of the view. They can be stored on the Alignment Server or directly used as restriction input for the Matcher view.

There is an option to calculate the discriminability and coverage factors for each property, and results will be shown inline. The algorithms are adapted from [START_REF] Song | Automatically generating data linkages using a domainindependent candidate selection approach[END_REF].

Property Correspondences Discovery, i.e., candidate selection, allows for finding schemalevel correspondences between properties of the two datasets by investigating instance-level information: Taking for example the sider and dailymed datasets, suppose we perform stringbased matching between the object values for all possible property combinations between the two datasets, there would be a total of approximately 2 000 000 000 different comparisons.

The number of comparisons can be reduced massively while still maintaining totally useful results (in comparison) as follows:

-only match literals.

-only match literals with the same datatype (detect datatypes of type integer, double, uri, xml, string, description (100+ character strings)) -also according to the datatype, suitable matching methods can applied. -only match properties that fulfill certain discriminability and coverage criteria.

-for each remaining property-pair, only match a subset of the property-values from one dataset with all the property-values of the other dataset. This means, for each property-pair, we put for example the constraint LIMIT 10 for the property-values of the one dataset's selected property and match each of those 10 property-values with all the property-values of the second dataset's selected property. Then for each of the 10 property-values, we remember the highest score and calculate the average over each of those 10 highest scores. Suppose a value range between 0.0 and 1.0 for such a score: when comparing the results of using LIMIT 10 with LIMIT 100, with the above dataset there was a maximum difference of 0.07 between the scores for each property-pair (except one outlier).

This means, that we can effectively reduce the number of comparisons and still obtain very useful results: Datatype detection reduces the number of comparisons from 2 000 000 000 to 150 000 000, and the LIMIT constraint to 750 000 for the above pair of datasets. Taking into account the property coverage and discriminability factors obtain an even higher reduction, but such constraints have to be used properly. Indexing could further improve performance.

For scoring those property-similarities, one option would be to count the percentage of exact or near-exact matches, another to calculate the average over the highest scores for each value from the LIMIT-constrained dataset. In addition to displaying those scores in the user interface after triggering this method, the best matches between the property-values could be displayed (perhaps a pop-up for each of the e.g. 10 matches or a selection) to allow the user to investigate suitable candidates.

This candidate selection feature could be further improved by using other schema alignment methods such as also comparing the classes-and properties-titles and looking into the structure of the schemas.

The matcher view is not available yet. Basically, the idea for the overall workflow is that property restrictions for the matcher can be selected from the Dataset Explorer and the Alignments views:

-Properties can be selected as restrictions for the matcher.

-Classes can be selected as restrictions, and consequently all the properties under the classes constraint are used as input for the matcher.

ANR-10-CORD-009

-Properties can be constrained by their object-values and those constrained properties serve as input for the matcher.

This needs to be defined in more detail, including how to best handle the picking of union and intersection of properties.

Then, the user can specify the matching method and weights for each of the properties. Again, some features like matching datatypes as well as coverage and discriminability can be displayed to assist the user.

During or after the matching phase, matched instances along with all their associated classes, properties, and property-values can be displayed to the user who can then supply feedback.

It would also be possible for the matching view to generate Silk specifications instead of actually performing the match.

Alignment server

Alignment servers are independent software components which offer a library of matching methods and an alignment store that can be used by their clients. MDR uses an Alignment server for retrieving alignments in order to help linking data. The Datalift platform may take advantage of them for the same purpose.

In a minimal configuration, alignment servers contribute to storing and communicating alignments. Ideally, they can offer all the following services:

Matching two ontologies possibly by specifying the algorithm to use and its parameters (including an initial alignment). Storing an alignment in persistent storage. Retrieving an alignment from its identifier. Retrieving alignment metadata from its identifier can be used for choosing between specific alignments. Finding (stored) alignments between two specific ontologies. Comparing alignments for determining what their differences are. Editing an alignment by adding or discarding correspondences (this is typically the result of a graphic editing session). Trimming alignments, i.e., selecting correspondences within thresholds. Generating code implementing ontology transformations, data translations or bridge axioms from a particular alignment. Translating a message with regard to an alignment. Finding a similar ontology is useful when one wants to align two ontologies through an intermediate one.

All these services are potentially useful for Datalift if users want to match ontologies and manipulate alignments before interlinking data. However, the main services to be used in our case is the storing and retrieving service. It will allow to provide already stored alignments to the platform. For instance, someone wanting to interlink a data set using ontology o with a data set using an ontology o can ask for matching the two ontologies and using the alignment for generating the Silk script. A more complete scenario involves [START_REF] Olteanu | A multi criteria fusion approach for geographical data[END_REF] asking for alignments between o and o , maybe resulting in no alignment, (2) asking for an ontology close to o which may result in ontology o , (3) asking for the alignments between o and o , which may return several alignments a, a and a , (4) asking for the metadata of these alignments and

(5) choosing a because it is certified by a trusted authority, (6) matching o and o with a particular algorithm, [START_REF] David | The alignment api 4.0[END_REF] suppressing the resulting correspondences whose confidence is under a reasonable threshold for this algorithm, (8) editing the results so that it is correct, [START_REF] Girres | Quality assessment of the french openstreetmap dataset[END_REF] storing it in the server for sharing it with other parties, [START_REF] Goodchild | A simple positional accuracy measure for linear features[END_REF] retrieving alignment a and this latter one, [START_REF] Goodwin | Geographical linked data: The administrative geography of great britain on the semantic web[END_REF] finally using these two alignments in order to generate a script to interlink the two data sources.

Alignment servers are middleware components of the semantic web infrastructure. They can be used by semantic web applications as well as by the infrastructure itself. They can be used at design time or at run time. For Datalift, the Alignment server is to be used when platform users need alignments for generating links. The Alignment server is built on the Alignment API that is seated on top of a relational database for sharing alignments and is wrapped around a simple protocol. Each access method is a plug-in that interacts with the server through the protocol. Currently, HTML, agent and web service plug-ins are available.

The Alignment server architecture is made of four layers (shown in Figure 2.2):

The Alignment API which provides operations for manipulating alignments including extension points for adding new matchers and renderers. A storage system which offers persistent storage and retrieval of alignments. It implements only basic storage and runtime memory caching functions. The storage is made through a DBMS interface and can be replaced by any database management system as soon as it is supported by JDBC. A protocol manager which handles the server protocol. It accepts queries from plug-in interfaces and uses the server resources for answering them. It uses the storage system for caching results. Protocol drivers (WSDL, HTTP, Jade, JXTA) which accept incoming queries in a particular communication system and invoke the protocol manager in order to answer them. These drivers are ideally stateless and only translators for the external queries.

Conclusion

We have presented tools that we may use in the Datalift data interlinking module. We will consider how to use them in the next chapter.

Implementation choices

As Deliverable D4.1 shows, there are many approaches to develop an interlinking module.

We have chosen to build our first prototype using Silk as a linking engine instead of writing a new one from scratch. We motivate below this choice. This should allow us to experiment with data interlinking within the platform.

If Silk appears to be too limited in the end, we may reconsider this choice and develop another module.

Why Silk?

We decided to experiment with Silk for several reasons:

-It is available in an appropriate license (compatible with inclusion in the Datalift platform); -It is maintained; -It is supposed to be quite extensible; -It is popular: independent projects have used it and it is heavily used in the LATC project.

However, Silk does come with a few draw backs:

-It is not that extensible: introducing modifications (like using alignments) requires major changes in the software; -It is script based, so any extension must have been considered in the scripting language; -It is written in Scala, which at that point of mastery, can be considered an obstacle.

The main problem is that Silk follows a specific and rather strict framework and does not provide an API for bypassing this framework.

We are in contact with Silk developers and discuss with them about the opportunity to further open their software. However, the two development tracks below are independent from this evolution.

Building an interlinking module around Silk

In Silk, the user has to write a script telling the system how to find links: between which classes, with which methods and which thresholds. On the other side, in Datalift, we want to define a system to find links without such an input.

A first way to use Silk under the platform is to develop the module so that it finds the parameters needed by Silk and generates (see Figure 3.1). One particular implementation of this approach will be the object of §6.

Another way of working consists of extending Silk with particular Datalift capabilities and to run Silk so that it uses such capabilities (see Figure 3.2). Such an extension may be quite simple such as developing measures for some particular data (see §5) or using alignments from inside Silk for piloting the script execution process. The second solution is difficult due to Silk relative closedness.

Both solutions are viable and we plan to pursue them together.

Conclusion

We have justified the decision of embedding Silk in the Datalift interlinking module and presented ways to extend it. We will now describe the currently implemented module.

Current prototype description

The current prototype integrates Silk within the Datalift platform. It produces owl:sameAs links from the data in the platform or elsewhere and store them in the public repository.

The module uses the last version of Silk (2.4.2). It is available in the Datalift code repository since version f1c94ccb681499b5dc5488de1dfbc2d01fac3550.

Principles

A first version of the Data interlinking module has been developed embedding Silk.

The current interlinking module is able to:

-Load its (RDF) data from the platform triple store; -Load its Silk script from the platform environment; -Run the Silk script; -Store the (RDF) results in the platform triple store.

This first version would be fully functional for integrating data if it was possible to upload the Silk script on the platform. This is our next immediate goal. Further work is presented in conclusion.

We have currently used Silk as a standalone server but it can also be used as a web service or deployed to the cloud. It is even possible that the Silk developers offer online services that could be used by the Datalift platform. In this Silk script, the RDF data sources are queried in the Datalift SPARQL endpoint. After the linking computation, the result is output as local files. They are, "insee eurostat verify links.xml" and "insee eurostat accepted links.xml". Currently, the Datalift external SPARQL endpoint does not support SPARQL Update. Thus, the link data set could not be stored directly to Datalift repository by specifying a SPARQL endpoint in the script. The Datalift interlinking module, thus reads the output files and store their results in the Datalift triple store using the Sesame API.

A Silk script for linking INSEE and NUTS

The results can be seen in the Datalift triple store as in Figure 4.1.

When looking at the result, we can see that the script is not optimal: it has matched twice FR101 ("Paris"), once with Paris the city (COM 75056) and once with Paris the department ANR-10-CORD-009 (DEP 75). In fact, it is also not efficient because wards ("communes") are not in the NUTS database and only French regions are matchable to the INSEE database. Hence, it is better to write two different pieces of scripts replacing the RestrictTo parts by: <SourceDataset dataSource="insee" var="a"> <RestrictTo> ?a rdf:type insee:Region . The first script section shows the instances from insee:Region should be compared with instances from eurostat:NUTSRegion with rdf:level equals 2. Meanwhile, the parent region of those instances should be http://ec.europa.eu/eurostat/ramon/rdfdata/nuts2008/FR. Similarly, the second script section shows the instances from insee:Departement should be compared with instances from eurostat:NUTSRegion with rdf:level equals 3. Their grandparent region should also be http://ec.europa.eu/eurostat/ramon/rdfdata/nuts2008/FR.

Conclusion

We have briefly introduced the current implementation of the Datalift interlinking module which is available from the platform repository.

We will consider, in the two next chapters, the way we plan to further improve this module.

Additional components

When dealing with specialised types of data, more informed comparisons may be used. For example, initial experiments performed when trying to align event descriptions help us to deduce that the existing similarity metrics are not sufficiently adapted to meet our needs.

We hereafter expose our motivation behind these extensions namely: temporal inclusion ( §5.1), token-wise metrics ( §5.2) and space ( §5.3), and we detail their algorithms [START_REF] Khrouf | EventMedia Live: Reconciliating Events Descriptions in the Web of Data[END_REF].

These extension can be embedded in SIlk, and hence in the Datalift platform, as new similarity measures tied to some data types (temporal and geographic).

Temporal inclusion metric

Most of the ontologies aiming at representing events, such as the LODE1 ontology, consider that an event has a start date and might have an end date. Intuitively, we consider that two events are similar if they share, among other things, the same time or temporal interval. Hence, matching two events requires a temporal overlap detection. The Date Time metric provided by Silk only measures the difference between two dates which is normalized against a predefined threshold MaxDays. Indeed, the more the difference between two dates is inferior to MaxDays, the higher is the similarity score. This metric brings confusion on what convenient threshold MaxDays must be specified especially when dealing with over thousands of events. Moreover, it is not suitable to infer if two events share a common temporal interval or not. For instance, we manually detect a similarity between two events, coming from two different social media directories, which have a common label Radiohead en Chile, but the first event is given between 26th at 07:49:01 PM and 27th at 18:05:01 PM of March 2009, while the second one is given on 27th March 2009 at 9:00 PM. We hence propose to introduce a new temporal inclusion metric which detects if a specific date belongs to one temporal interval or if two temporal intervals have an overlap. In the aforementioned example, we observe a difference of nearly 3 hours between the end date of the former event and the start date of the latter one. Thus, a certain number of hours θ has to be tolerated when comparing two dates.

Given two events (e 1 , e 2 ) which have respectively the pair start date and end date (d 1 , d 1 ) and (d 2 , d 2 ) such that d 1 , d 2 = 0 and d 1 , d 2 can be null, the temporal inclusion similarity is defined by the following function:

(5.1)

s(e 1 , e 2 ) =        1 if |d 1 -d 2 | ≤ θ where (d 1 , d 2 ) = 0 1 if d 1 ± θ ∈ [d 1 , d 2 ] where d 2 = 0 (idem for d 1 ) 1 if min(d 1 , d 2 ) -max(d 1 , d 2 ) ≥ 0 where (d 1 , d 2 ) = 0 0 otherwise.

Token-wise string similarity

Comparisons based on string similarity have been widely exploited by many applications such as duplicate detection and data integration. Overall, they are divided into two main classes: character-based and token-based functions, in which the similarity score ranges from 0 to 1. The former class considers a string as a sequence of characters to compute the score.

A typical example is the edit distance which is the minimum number of edit operations, i.e., insertion, deletion, and substitution, to convert one string to another. One advanced variant which is not based on the edit distance model is the Jaro metric [START_REF] Jaro | Advances in Record-Linkage Methodology as Applied to Matching the 1985 Census of Tampa, Florida[END_REF], in which the distance depends on the number and the order of common characters between two strings. For example, the Jaro similarity between "finn brother" and "brothers finn" is 0.6. We note that this score is low despite the high similarity between these strings which have similar words. Indeed, changing the order of tokens affects the sequence of characters which makes the character-based metrics sensitive to the tokens positions. The Jaro metric is mainly used to overcome misspelled data and to match short strings such as personal names [START_REF] Cohen | A Comparison of String Distance Metrics for Name-Matching Tasks[END_REF]. For example, the Jaro distance between "brother" and "brothers" is 0.98. The second class of string distances is the token-based distance which considers a string as a sequence of tokens.

They split strings into token sets (i.e. by white-space) called bag of words, and they compute the similarity based on these sets. A typical metric is the Jaccard distance [START_REF] Jaccard | Étude comparative de la distribution florale dans une portion des Alpes et des Jura[END_REF] where the score is the ratio of intersection size and the union size of two token sets. For example, the token sets of "finn brother" and "brothers finn" are respectively {"finn", "brother"} and {"brothers", "finn"}. The Jaccard distance between these two strings is 0.3 which is a low score as the close similarity between "brother" and "brothers" is ignored. Indeed, token-based functions only consider the exact overlap between the token sets and neglect approximate tokens.

We have studied the performance of these string similarity functions over the Event-Media data that consists of user-generated content featuring typos, misspelled and noisy data [START_REF] Khrouf | Réconcilier les événements dans le web de données[END_REF]. We find some similar events wherein the labels have a low similarity in terms of character-based and token-based functions. For example, the Jaccard score between "Anna Plus Kristen Puferfish" and "Pufferfish for Anna and Kristen" is 0.28 while the Jaro score is 0.6. To overcome these limitations, we introduce a novel hybrid metric called Token-Wise [START_REF] Khrouf | EventMedia Live: Reconciliating Events Descriptions in the Web of Data[END_REF] combining the two string similarity classes. Our objective is to compute a fuzzy overlap between two token sets. We enhance our method by allowing to attribute a low weight for a list of words (stop-words) frequently used such as the prepositions and, for, in, from, etc. The Token-Wise metric proceeds as follows:

-The strings s and t are first split into a set of tokens {s 1 ....s k } and {t 1 ....t p } -A list L sp of stop-words and related weight can be specified. These stop-words are in general frequent words which differ from one context to another. For instance, analyzing the events titles in EventMedia help us to find out some frequent words such as festival, concert, music. etc. We can also attribute a specific weight for the remaining words which do not belong to L sp .

-Using one of the character-based functions such as Jaro, Jaro-winkler and Levenshtein, the similarity scores are computed between each token pair from the two sets generating a set of triples (s i , t j , sim (s i , t j )). We can keep the triples, in which the scores are larger than a given sim' threshold δ. Then, for each token, we keep its correspondent triple which contains the highest score.

-The token-wise score is based on the Jaccard similarity pattern which computes the ratio of union size and intersection size of two token sets. Given two strings s, t and their respective token sets A and B, the token-wise score adopts the following pattern

(5.2) pattern(s, t) = |A ∩ B| |A\B| + |B\A| + |A ∩ B|
Given sim (s i , t j ) the score of the based-character similarity between two tokens, ws i and wt j the respective weights of s i and t j , N the number of matched tokens (filtered triples), M ANR-10-CORD-009 the number of unmatched tokens where we set sim = 0, the token-wise score can be written as

(5.3) token -wise(s, t) = N i=1 sim (s i , t j ) × ws i × wt j N +M i=1 (1 -sim (s i , t j )) × (ws 2 i + wt 2 j ) + N i=1 sim (s i , t j ) × ws i × wt j
To better understand the token-wise measure, we consider the following two event titles "Island Treasre Music" and "Treasure Island". We compute the Jaro similarity between each token pair from their respective sets ("Island", "Treasre", "Music") and ("Treasure", "Island"). Then, we only take the highest score obtained for each token provided that this score is above a predefined character-based (sim') threshold δ. In this example, for the sake of simplicity, we set this threshold = 0 and we consider the word "music" as a stop-word with the weight w=0.1. Thus, we retain the following triples including the matched tokens and their Jaro scores: (1.0, island, island); (0.95, treasre, treasure). The word "music" is still unmatched, so its sim'=0. In this example, we attribute the weight w=1 for the remaining words. The score between s and t is:

token-wise(s, t) = 1 × 1 × 1 + 0.95 × 1 × 1 (1 -1) × (1 + 1) + (1 -0.95) × (1 + 1) + (1 -0) × 0.1 + (1 + 0.95) = 0.98

Interconnecting geographical data sets

The inter-connexion of geographic data has been a major research domain in geographical information science for a long time and still is. Firstly, many various information, e.g., inhabitants, climate, species, tourism, diseases, is somehow related to earth and the main usage of geographic information is the possibility to search for correlation between different kinds of information based on their spatial relationships. This requires at least one integration step that is referencing these pieces of information in one same geographic reference system. Second, acquiring located data often is a costly process so that data are usually acquired once and reused several times: when a user needs located data he will not acquire it from scratch but will first look for an existing dataset. Third, quality control mechanisms rely on comparing the examined dataset with a reference dataset or comparing together several datasets. Eventually, one current "linked data on the web" argument is shared with geographical data: data should be acquired once and should then be easily discoverable, accessed and combined. This has been reinforced by the European INSPIRE directive (EU INSPIRE Directive 2007/2/EC) which requires state member to contribute to a European infrastructure of geographic information where legal located data, useful to define and monitor Europe environmental policy, be easily accessible and combined. If many methods and tools have been designed, reusing them demands a careful analysis of their original context and the distance to Datalift objectives. Indeed most tools are valid in a certain context only, either explicitly or because of the context in which they have been designed and tested.

Many approaches have been established in the context of traditional geographical data, i.e., data produced by professionals. In this context, heterogeneities stem from different selections of objects in the world, different levels of details, different representation choices [START_REF] Bishr | Semantic Aspects of Interoperable GIS[END_REF]. Some researches have tackled geographical schema matching and assess the necessity to represent unambiguously the semantics of the database, i.e., the relationship with the real world or in other words the database specifications [START_REF] Kavouras | Theories of Geographic Concepts: Ontological Approaches to Semantic Integration[END_REF][START_REF] Abadie | Schema matching based on attribute values and background ontology[END_REF]. [START_REF] Abadie | Schema matching based on attribute values and background ontology[END_REF] proposes to encode in a formal ontology semantic knowledge relevant to schema matching. This includes relationship with an ontology of the real world but also how an object of the real world is represented through database objects. The author proposes an OWL implementation of IGN database specifications aiming at supporting data integration. [START_REF] Schade | Towards semantic datums for geospatial information[END_REF] uses ontologies to convert spatial data from one model to another (which is a key process in INSPIRE to transform producer data into a common model). He annotates source and target schemas with a domain ontology after [START_REF] Klien | Semantic Annotation of Geographic Information[END_REF] method. Matching items are identified through inferences and an ontology of spatial analysis operations is used to evaluate if it is possible to derive new items from the target schema by applying these operations on the source schema. [START_REF] Rodriguez | Determining semantic similarity among entity classes from different ontologies[END_REF] have concentrated on data matching based on several ontologies including the data themselves. Other works have studied data matching based either on geometrical criteria, like distance and topological relationships [START_REF] Mustière | Matching networks with different levels of detail[END_REF] or on a mix of geometric and semantic criteria [START_REF] Olteanu | A multi criteria fusion approach for geographical data[END_REF].

More recently researchers have matched traditional data with user contributed data, namely Open Street Map data (published as LinkedGeodata on the LOD). [START_REF] Haklay | How good is openstreetmap information? a comparative study of openstreetmap and ordnance survey datasets for london and the rest of england[END_REF] has matched OSM network and OSGB Meridian network to assess some distance between both. The interconnection is not between the roads themselves but only between the networks using [START_REF] Goodchild | A simple positional accuracy measure for linear features[END_REF] distance. [START_REF] Girres | Quality assessment of the french openstreetmap dataset[END_REF] performed a similar but more detailed analysis on France OSM data compared to IGN. They interconnected the dataset at the feature level (roads, lakes) using different distance measures that can be reused in the context of Datalift. Last, [START_REF] Hahmann | Connecting linkedgeodata and geonames in the spatial semantic web[END_REF] has experimented the connection of linked data based on spatial criteria. More precisely they have interconnected Geonames residential areas in Geonames and in LinkedGeodata in Germany. Matching at the schema level is performed manually and then the authors combine a Levenshtein minimum string distance between the place names and a buffer intersection method between the place coordinates.

Our objective in datalift is to manage spatial aspects in ontologies interconnexion and in data interconnexion. Ontologies interconnexion can be enhanced by considering more finely the semantic and the kind of geometry. This can be modelled using [START_REF] Abadie | Schema matching based on attribute values and background ontology[END_REF]'s proposal. This will also result in valuable information for data interconnexion. For instance the possible error associated to the determination of the center of a populated place makes it easier to define relevant geometric distance threshold in populated places interconnexion. Data interconnexion can also be enhanced by combining several similarity criteria (shape, distance, semantics, relationships with other features). Distance algorithms can be reused from existing java implementations. Semantics similarity will be provided by the platform, shape or relationships tools are implemented on the Geoxygene platform. The combination of criteria is more tricky and we will adopt [START_REF] Olteanu | A multi criteria fusion approach for geographical data[END_REF] results to address this. Last, it is obviously important not only to connect features or feature collections but also to comment on the connection and use carefully the similarity relationships [START_REF] Goodwin | Geographical linked data: The administrative geography of great britain on the semantic web[END_REF]. For instance, is this the similar object at different levels of details? Can a conflation strategy [START_REF] Yuan | Development of conflation components[END_REF] be used or not?

Conclusion

We have briefly presented three types of special purpose techniques for comparing particular datatypes. We plan to integrate such techniques in a further version of the platform, first through Silk plug-ins.

Using EDOAL to control interlinking

We consider here the use of alignments as input of the interlinking process. The type of alignments required to express interlinking with the precision of the script provided in §4.2 goes beyond simple alignments. For expressing expressive alignments, we have designed the EDOAL language [START_REF] David | The alignment api 4.0[END_REF] 1 which must be considered for that purpose.

Working on interlinking the web of data, we have the incentive to use SPARQL in order to preform interlinking. This is because most linked data is offered as a SPARQL endpoint that Silk allows to restrict sources and targets with SPARQL.

Hence the question is how do we generate useful queries from alignments and, specifically, EDOAL alignments because, they may be very useful for that purpose. Relating expressive alignments and SPARQL has already been the topic of a previous paper [START_REF] Euzenat | Processing ontology alignments with sparql (position paper)[END_REF].

In fact, there are several ways to generate queries from alignments (corresponding to the following sections):

-query mediator (queryprocessor) which transform a query according to the alignment ( §6.1); -query generator (easier) which generates a query for each EDOAL expression in a correspondence ( §6.2); -data transformation which generates a unique CONSTRUCT-based SPARQL query able to transform data from one ontology to another ( §6.3); -CONSTRUCT-based SPARQL link generators able to generate a query for creating links between datasets ( §6.4).

Mediating queries

We proposed the QueryProcessor interface and its QueryMediator implementation which takes a query and an alignment and evaluates the query after having translated it with the help of the Alignment (see Figure 6.1).

o o A query mediator q q Figure 6.1: A query mediator generated from an alignment allows for transforming queries over data.

Only a trivial string-based version of this has been implemented within the Alignment API (which supports EDOAL). But it served its purpose (because, with simple alignments, it is enough to transcribe URIs).

Since, we have introduced EDOAL within the Alignment API, it would be interesting to redevelop such a mediator for EDOAL. Recently, Gianluca Correndo from Southampton contacted us because he has implemented a partial query mediator for EDOAL [START_REF] Correndo | Sparql query rewriting for implementing data integration over linked data[END_REF]. That would be useful to extend it and integrate it within the API.

Extracting linked data

For dealing with linked data, we actually do not need to transform queries, but to generate them. In particular, we need to generate queries from alignments in EDOAL in order to restrict the investigations of the data to be matched. What is needed is displayed by Figure 6 In the latter case, this is only possible because the query pattern is definite, i.e., by constraining the properties to have an exact value, we know which value must the generated instances have. This is, however, not what is needed in the Datalift interlinking module.

Generating links

Finally, one can imagine using SPARQL CONSTRUCT queries in order to generate owl:sameAs links between resources of two datasets. For that purpose, it is necessary that the EDOAL alignment provides enough information to identify the corresponding resources. This is the case of the following correspondence which corresponds to the correspondence of §6. ?n nuts:hasParentRegion nuts:FR1 . ?r insee:nom ?l . ?n nuts:name ?l .

This single SPARQL query performs what the script of §4.2 has accomplished. It can, in principle, be directly generated from the correspondences (similar Silk scripts could be generated as well).

Implementation

This is not implemented so far but will certainly have to in the context of Datalift. Gianlucca Correndo already has a beginning of implementation of the importer generation. The obvious way to implement this would be to use the Visitor pattern to traverse inductively EDOAL expressions.

It is necessary to investigate how to share part of the code of these three functions. It seems clear that the two latter share at least the query pattern that is created inductively on the structure of the EDOAL expression. It is possible that the CONSTRUCT part could be expressed in the same way. The first type of operation, query mediation, is quite different because it is a query transformation and not a data transformation.

Going further

EDOAL expression transformation is far from a simple task because:

-we want to rewrite query parts which match the most specific EDOAL expression -it is difficult to recognise them because they may be interleaved with others. Indeed, it is difficult to predict the interaction between the SPARQL queries at runtime. This is a well known problem of term rewriting: that of confluence. We want that whatever the order in which we evaluate the SPARQL queries, this will in the end provide the same result. This is trivially true if not two queries can match the same piece of data, not if several queries can concern the same resource. In the present case, we also would like that all rewriting concerning the same entity be treated within the same query (for both performance and coherence considerations). This problem seems to be well known in database mapping generation and is treated (for simple correspondences) in a recent paper [START_REF] Rivero | Generating sparql executable mappings to integrate ontologies[END_REF]. ANR-10-CORD-009

Conclusion

We now have an operational data interlinking module within the platform which should allow to experiment with novel interlinking algorithms. We also have plans for enriching this module that will be implemented in next year.

Our planned next steps are:

-integrating additional components -integrating Silk script generator based on alignments (DMT) -integrating Silk script generator based on alignments (EDOAL based)

We plan to achieve them within three months and to be able to experiment with this setting in order to decide if this strategy is valid or if we must change for another.

2 . 2 2 . 3

 2223 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Data management tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Alignment server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Implementation choices 13 3.1 Why Silk? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Building an interlinking module around Silk . . . . . . . . . . . . . . . . . . . 13 3.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Current prototype description 16 4.1 Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.2 A Silk script for linking INSEE and NUTS . . . . . . . . . . . . . . . . . . . 16 4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Additional components 20 5.1 Temporal inclusion metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.2 Token-wise string similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.3 Interconnecting geographical data sets . . . . . . . . . . . . . . . . . . . . . . 22 5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Using EDOAL to control interlinking 24 6.1 Mediating queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 6.2 Extracting linked data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 6.3 Importing linked data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 6.4 Generating links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 6.5 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 6.6 Going further . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Conclusion 30 References 30

Figure 2 . 1 :

 21 Figure 2.1: The Alignment view of DMT.

Figure 2 . 2 :

 22 Figure 2.2:The Alignment server is built on the Alignment API that is seated on top of a relational database for sharing alignments and is wrapped around a simple protocol. Each access method is a plug-in that interacts with the server through the protocol. Currently, HTML, agent and web service plug-ins are available.

Figure 3 . 1 :Figure 3 . 2 :

 3132 Figure 3.1: Developing a tool for generating Silk scripts.

Figure 4 . 1 :

 41 Figure 4.1: The sameAs links found by the Silk script in the Datalift triple store.

2 Figure 6 . 6 :

 266 Figure 6.6: A more elaborate EDOAL correspondence indicating which properties must be compared in order to establish the link.

  Here is the Silk script for linking geographical RDF data in France from INSEE and Europe from Eurostat.

	</DataSources>
	<Interlinks>
	<Interlink id="region">
	<LinkType>owl:sameAs</LinkType>
	<SourceDataset dataSource="insee" var="a">
	<RestrictTo>
	{ { ?a rdf:type insee:Region } UNION
	{ ?a rdf:type insee:Departement } UNION
	{ ?a rdf:type insee:Commune } }
	</RestrictTo>
	</SourceDataset>
	<TargetDataset dataSource="eurostat" var="b">
	<RestrictTo>
	?b rdf:type eurostat:NUTSRegion
	</RestrictTo>
	</TargetDataset>
	<LinkCondition>
	<Aggregate type="max">
	<Compare metric="levenshteinDistance" threshold="0">
	<TransformInput function="lowerCase">
	<Input path="?a/geo:nom[@lang='fr']" />
	</TransformInput>
	<TransformInput function="lowerCase">
	<Input path="?b/eurostat:name" />
	</TransformInput>
	</Compare>
	</Aggregate>
	</LinkCondition>
	<Filter />
	<Outputs> <?xml version="1.0" encoding="utf-8" ?> <Output maxConfidence="1.0" type="file" > <Silk> <Param name="file" value="insee_eurostat_verify_links.xml"/> <Prefixes> <Param name="format" value="alignment"/> <Prefix id="rdf" namespace="http://www.w3.org/1999/02/22-rdf-syntax-ns#" /> </Output> <Prefix id="rdfs" namespace="http://www.w3.org/2000/01/rdf-schema#" /> <Output minConfidence="0.1" type="file"> <Prefix id="geo" namespace="http://rdf.insee.fr/geo/" /> <Param name="file" value="insee_eurostat_accepted_links.xml"/> <Prefix id="dc" namespace="http://purl.org/dc/elements/1.1/" /> <Param name="format" value="alignment"/> <Prefix id="cc" namespace="http://creativecommons.org/ns#" /> </Output> <Prefix id="owl" namespace="http://www.w3.org/2002/07/owl#"/> </Outputs> <Prefix id="dcterms" namespace="http://purl.org/dc/terms/" /> </Interlink> <Prefix id="xmlns" namespace= </Interlinks> "http://ec.europa.eu/eurostat/ramon/ontologies/geographic.rdf#"/> <Prefix id="insee" namespace="http://rdf.insee.fr/geo/" /> </Silk>
	<Prefix id="eurostat" namespace=
	"http://ec.europa.eu/eurostat/ramon/ontologies/geographic.rdf#"/>
	</Prefixes>
	<DataSources>
	<DataSource id="insee" type="sparqlEndpoint">
	<Param name="endpointURI" value="http://localhost:8080/datalift/sparql" />
	</DataSource>
	<DataSource id="eurostat" type="sparqlEndpoint">
	<Param name="endpointURI" value="http://localhost:8080/datalift/sparql" />
	</DataSource>

  .2. Figure6.2: A query generator generated from an alignment allows for producing the SPARQL queries which restrict the search area in which an interlinker would look for.What is needed is to retrieve all instances of EDOAL expressions appearing in both sides of a correspondence in order to see if they can be matched. For instance, with respect to the following EDOAL correspondence: to Figure6.3: it expresses the equivalence between the class Region in the insee data set with NUTSRegion instances whose level is equal to 2 and whose parent region is FR1 in the NUTS data set.It is possible to generate the following queries which respectively extract the two corresponding set of entities: The EDOAL correspondence between INSEE regions and NUTS French region of level 2 corresponding to the example given in the Silk script of §4.2.In the case of the latter query, it is possible to generate data corresponding to the NUTSRegions of level two situated in France to Regions: CONSTRUCT ?n rdf:type insee:Region . PREFIX insee: <http://rdf.insee.fr/ontologie-geo-2006.rdf#> PREFIX nuts: <http://ec.europa.eu/eurostat/ramon/ontologies/geographic.rdf#> PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> FROM <http://rdf.insee.fr/geo/regions-2011.rdf> Figure 6.5: A SPARQL link generator generated from an alignment can directly link data sets with a single SPARQL query. PREFIX insee: <http://rdf.insee.fr/ontologie-geo-2006.rdf#> PREFIX nuts: <http://ec.europa.eu/eurostat/ramon/ontologies/geographic.rdf#> PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> FROM <http://rdf.insee.fr/geo/regions-2011.rdf> FROM <http://ec.europa.eu/eurostat/ramon/rdfdata/nuts2008/> WHERE ?r rdf:type insee:Region .

		o			A	NUTSRegion o
		Region	=	level hasParentRegion 2 = SPARQL link generator FR1 =
		d1			q	d2
	Figure 6.3: SELECT ?r	o	A SPAQRL query generator Void	o
	q PREFIX insee: <http://rdf.insee.fr/ontologie-geo-2006.rdf#> PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>	q
	FROM <http://rdf.insee.fr/geo/regions-2011.rdf> FROM <http://ec.europa.eu/eurostat/ramon/rdfdata/nuts2008/> WHERE WHERE ?r rdf:type insee:Region . ?n rdf:type nuts:NUTSRegion .
	?n nuts:level 2^^xsd:int .
	?n nuts:hasParentRegion nuts:FR1 .
					nuts2008/>
	<Cell> WHERE
	<entity1> ?n rdf:type nuts:NUTSRegion .
	<edoal:Class rdf:about="&insee;Region" /> ?n nuts:level 2^^xsd:int .
	</entity1> ?n nuts:hasParentRegion nuts:FR1 .
	<entity2>
	<edoal:Class>
	<edoal:and rdf:parseType="Collection">
	<edoal:Class rdf:about="&nults;NUTSRegion"/> <edoal:AttributeValueRestriction> 6.3 Importing linked data
	<edoal:onAttribute> Another use consists of not only extracting the data but importing data from one dataset <edoal:Property rdf:about="&nuts;level"/> </edoal:onAttribute> into another dataset. What is then needed is a CONSTRUCT query that will transform the
	<edoal:comparator rdf:resource="&xsd;equals"/> data (see Figure 6.4).
	<edoal:value>2</edoal:value>
	</edoal:AttributeValueRestriction> <edoal:AttributeValueRestriction> o	A	o
	<edoal:onAttribute>
		<edoal:Relation rdf:about="&nuts;hasParentRegion"/> SPARQL import generator
	</edoal:onAttribute>
	<edoal:comparator rdf:resource="&xsd;equals"/> <edoal:value><edoal:Instance rdf:about="&nuts;FR1"/></edoal:value> q d1 d2
	</edoal:AttributeValueRestriction>
	</edoal:and>
	</edoal:Class> </entity2> Figure 6.4: An import query can be generated from an alignment in order to import data
	<measure rdf:datatype='&xsd;float'>1.</measure> from one data set into another.
	<relation>=</relation>
	</Cell>

corresponding and SELECT ?n PREFIX nuts: <http://ec.europa.eu/eurostat/ramon/ontologies/geographic.rdf#> PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> FROM <http://ec.europa.eu/eurostat/ramon/rdfdata/or, in the reverse direction, CONSTRUCT ?r rdf:type nuts:NUTSRegion . ?r nuts:level 2^^xsd:int . ?r nuts:hasParentRegion nuts:FR1 .

http://www4.wiwiss.fu-berlin.de/bizer/silk/

http://linkedevents.org/ontology/

http://alignapi.gforge.inria.fr/edoal.html

ANR Contint -ANR-10-CORD-Un ascenseur pour les donnes Project URL http://www.datalift.org/

<edoal:and rdf:parseType="Collection"> <edoal:Class rdf:about="&nuts;NUTSRegion"/> <edoal:AttributeValueRestriction> <edoal:onAttribute> <edoal:Property rdf:about="&nuts;level"/> </edoal:onAttribute> <edoal:comparator rdf:resource="&xsd;equals"/> <edoal:value>2</edoal:value> </edoal:AttributeValueRestriction> <edoal:AttributeValueRestriction> <edoal:onAttribute> <edoal:Relation rdf:about="&nuts;hasParentRegion"/> </edoal:onAttribute> <edoal:comparator rdf:resource="&xsd;equals"/> <edoal:value><edoal:Instance rdf:about="&nuts;FR1"/></edoal:value> </edoal:AttributeValueRestriction> </edoal:and> </edoal:Class> </entity2> <!--This may not be standard EDOAL --> <edoal:transformation> <edoal:Transformation edoal:type="o-"> <edoal:entity1> <edoal:Property rdf:about="&insee;nom"/> </edoal:entity1> <edoal:entity2> <edoal:Property rdf:about="&nuts;name"/> </edoal:entity2> </edoal:Transformation> </edoal:transformation> <!--A better rewriting --> <edoal:linkConstraint> <edoal:Cell> <edoal:entity1> <edoal:Property rdf:about="&insee;nom"/> </edoal:entity1> <edoal:entity2> <edoal:Property rdf:about="&nuts;name"/> </edoal:entity2> </edoal:Cell> </edoal:linkConstraint> <measure rdf:datatype='&xsd;float'>1.</measure> <relation>=</relation> </Cell> This information can be expressed either as a transformation or as a constraints. It could also be expressed as a linking condition. This correspondence corresponds to (part of) Figure 6.6.

The corresponding SPARQL query generating links is: