Judicaël Bedouet

Thomas Dubot

Luis Basora

Towards an Operational Sectorisation based on Deterministic and Stochastic Partitioning Algorithms

This paper describes a method combining operational deterministic and stochastic approaches to generate optimised and smooth sector configuration plans. First, sector configurations commonly used within an Area Control Centre (ACC) are sorted according to a set of objectives for each time period. From these Pareto-optimal solutions, we determine through a stochastic method new sector configurations, mainly unstructured, to improve criteria such as the workload distribution. Then these optimized configurations are remodelled with another stochastic function to compute a set of final configurations acceptable to air traffic controllers. Secondly, we integrate these good solutions throughout the day to build the smoothest sector configuration plan possible, using the minimization of a dedicated distance function between successive configurations. Results of the SESAR 07.05.04 VP-755 experiments demonstrate that such methods could improve several criteria at the level of an ACC, such as the French Reims ACC, and pave the way for the development of an automated decision support tool integrating such algorithms.

I. INTRODUCTION

The challenge of cleverly combining airspace sectors for an efficient use of air traffic control resources [START_REF] Bloem | Combining airspace sectors for the efficient use of air traffic control resources[END_REF], or sectorisation process, is a classic optimisation problem in Air Traffic Management. Various optimisation methodologies have been explored [START_REF] Flener | Automatic airspace sectorisation: A survey[END_REF], such as Constraint Programming [START_REF] Flener | Propagators and violation functions for geometric and workload constraints arising in airspace sectorisation[END_REF], Mixed Integer Programming [START_REF] Drew | Analysis of an optimal sector design method[END_REF], Global Optimisation and Evolutionary Algorithms [START_REF] Delahaye | Modeling and optimization of air traffic[END_REF]Chapter 5], [START_REF] Durand | Metaheuristics for Air Traffic Management[END_REF]Chapter 3].

Nevertheless, most control centres still rely today on a human expertise to compare the traffic demand with the sector capacities and choose the adequate airspace configuration for each time period of the day. In this way, only a small subset of predefined configurations is used, instead of exploring all the possible combinations of sectors. In addition, the usual hotspot resolution method consists in splitting the overloaded sector into two sectors, which is not optimal (increase of the number of control positions) and sometimes impossible (e.g. if the hotspot occurs at the level of an elementary sector) [START_REF] Dubot | Building a smooth and dynamic opening scheme from graph partitioning-exploring dynamic airspace configurations[END_REF].

The European SESAR program [8] experiments with modular and flexible dynamic airspace configurations to better adapt to demand pattern changes and traffic flows volatility induced by an extensive implementation of free route operations [START_REF]P07.05.04 Dynamic Airspace Configuration Step 2-V2 OSED[END_REF], [START_REF]P07.02 Step 1 Release 5 Detailed Operational Description (DOD)[END_REF]. In this context, large airspace blocks are decomposed into airspace building blocks, smaller than current elementary sectors, and delineating typical demand forecast patterns, e.g. traffic flows. These building blocks, which are not necessarily controllable, are then grouped into control sectors named Controlled Airspace Blocks (CAB). In this way, control sectors are more adapted to traffic specificities, which enables to solve hotspots by reorganising the frontiers of control sectors, without modifying their number, instead of splitting one of the existing control sectors. We presented in [START_REF] Dubot | Modelling, generating and evaluating sector configuration plans methodology report of the SESAR VP-755 exercise[END_REF] the methodologies and tools developed within the SESAR VP-755 exercise of the SESAR 07.05.04 project, which consisted in a performance assessment of sectorisation algorithms based on this new paradigm applied to the French Reims ACC.

We describe in this paper the sectorisation algorithms introduced in this communication paper, with the ambition of providing:

• for each time period a set of optimized sector configurations acceptable to controllers, i.e. composed of sectors commonly used in the operational context, or new sectors with admissible shape; • a smooth sector configuration plan ensuring the shape stability of sector configurations (no abrupt sector changes between two consecutive periods of time) throughout the day; • a decision support tool integrating these algorithms to automatically guide the operational experts in the process of building a sector configuration plan, whatever the time horizon considered.

This paper focuses on the way to combine deterministic and stochastic algorithms to compute optimized and operational sector configurations, the acceptability being the key challenge. This approach is based on our previous work, presented in [START_REF] Dubot | Building a smooth and dynamic opening scheme from graph partitioning-exploring dynamic airspace configurations[END_REF] to build smooth configuration plans, which is a relatively unexplored field of research [START_REF] Sergeeva | Dynamic airspace configurations generated by evolutionary algorithms[END_REF], [START_REF] Leiden | Flight level-based dynamic airspace configuration[END_REF]. Nevertheless all algorithms have been reshaped to take into account operational constraints. We describe in section II the mathematical model of this graph partitioning problem, and the different objectives considered, such as the workload distribution. In section III, we detail how to determine initial good solutions using a deterministic algorithm, which explores known sector configurations. Section IV explains how to disorganise and reform these solutions, using stochastic methods. Finally we detail in section V the distance function introduced to integrate these solutions in a smooth sector configuration plan. Section VI summarizes the results obtained with the Reims ACC use case, and section VII concludes on the possibility to integrate such algorithms in an operational automated decision support tool.

II. MODELLING THE PROBLEM

A. Graph model

A sectorisation problem is equivalent to a graph partitioning problem [START_REF] Bichot | Élaboration d'une nouvelle métaheuristique pour le partitionnement de graphe: la méthode de fusion-fission. Application au découpage de l'espace aérien[END_REF]. As shown in Figure 1 for the Reims ACC, each building block is mapped to a node of the graph G = (V, E). The graph G denotes the representation of the airspace, where V (the set of vertices) is the set of building blocks and E (the set of edges), is such that (u, v) belongs to E only if there can be a direct trajectory from u to v. The set of vertices is always the same along the day 1 . We build the edges of the graph by analysing the geometrical connectivity between the vertices [START_REF] Sale | Development of a computer based airspace sector occupancy model[END_REF].

For a given time period δt, the weights of the nodes and the costs of the edges are determined by analysing the entries/exits of the flight plans in the different airspace building blocks. These values are computed as follows:

• D v (δt) density workload that occurs at vertex v during a given time period δt. Density is notably proportional to the time spent by aircraft in the block. It would be possible to refine this value with, for example, the number of potential conflicts, like in [START_REF] Delahaye | Genetic algorithms for partitioning air space[END_REF] or [START_REF] Yousefi | Temporal and spatial distribution of airspace complexity for air traffic controller workload-based sectorization[END_REF]. Nevertheless, the number of aircraft remains the main variable operationally used to decide to open or close a sector. 1 In the context of operations, it may change but every six months or more.

• C e (δt) coordination workload assigned to the edge e during a given period δt. It depends on the number of aircraft flying from a block to another. For a given time period δt, we call P k (δt) a partition of this graph G in k subsets such as P k (δt) = S 1 , ...., S k . Each subset S i of the partition must be non-empty and disjoint from the other subsets. Moreover, the union of all the subsets must entirely cover graph G and satisfies the connectivity constraint: the different elements of a subset, the aforementioned vertices, must be connected. In the operational jargon, a partition is called a sector configuration and a subset a CAB.

B. Partition functions

For a given time period δt, we introduce three functions that will be useful to characterise the properties of a partition: balance, cut and compactness.

We define the balance of a partition P k (δt) as the sum of the differences between the density workload of a subset S i , D Si (δt), and the average density of the subsets:

balance(P k (δt)) = i D Si (δt) -i D Si (δt) k where D Si (δt) = v∈Si D v (δt).
This definition is inspired by [START_REF] Bichot | Élaboration d'une nouvelle métaheuristique pour le partitionnement de graphe: la méthode de fusion-fission. Application au découpage de l'espace aérien[END_REF] and is used to equally share the workload between the different sectors. However, this definition is based on the infinity norm whereas ours is based on the Manhattan norm. A 2-norm could also be considered.

We define the cut of a partition P k (δt) such as the sum of the edges cut by the partition during a given period δt:

cut(P k (δt)) = i<j cut(δt, S i , S j )
where cut(δt, S i , S j ) = v1∈Si,v2∈Sj C (v1,v2) (δt).

It estimates the cost needed to coordinate traffic between the different sectors and the initial idea is presented in [START_REF] Kernighan | An efficient heuristic procedure for partitioning graphs[END_REF].

To better handle the shape of sectors, another function, called compactness, has recently been introduced by Jägare, Flener and Pearson in [START_REF] Jägare | Airspace sectorisation using constraint-based local search[END_REF]. Their definition of compactness is inspired by the sphericity of the shape of a quartz particle in crystallography [START_REF] Flener | Propagators and violation functions for geometric and workload constraints arising in airspace sectorisation[END_REF]. We give another definition based on the ratio of two prisms 2 ' volumes, avoiding balconies:

compactness(P k (δt)) = i compactness(S i )
where compactness(S i ) = j prisms of Si volume(j) volume(cover(i)) cover(i) is the smallest prism which includes all the prisms of i. 2 A prism is a polyhedron with two parallel n-sided polygonal bases and n other parallelogram-shaped faces joining the corresponding sides of the two bases. A sector can be seen as a set of contiguous prisms as represented in Figure 2. When a sector can be described by one and only one prism, it is said to be compact. Otherwise, balconies appear, like LFEEUE in Figure 2, which makes more complicated the controllers' task. However, as the altitude of the floor or the ceiling varies inside the ACC (see Figure 3), balconies are unavoidable in some cases. This is the case of LFEEUE, which is operationnally acceptable. The volume of the covering airspace is then corrected to ignore volumes outside the ACC so that compactness of those sectors can be valued to 1. It should be noted that the perfect partition is found when its balance is 0, its cut is 0 and its compactness is 1. Unlike balance and cut, compactness is computationally expensive, but since we often manipulate the same sectors, values of compactness(S i ) are put into a cache to speed up computations.

C. Objectives and constraints

To build the optimal partition of airspace into k sectors, we therefore consider different objectives:

• minimising the workload distribution, which consists in minimising the function balance(P k (δt)) for each period; • minimising the total number of transfers, which consists in minimising the function cut(P k (δt)) for each period; • ensuring that resulting sectors have acceptable geometric shapes with a minor number of balconies, which consists in maximising the function compactness(P k (δt)).

In some contexts, we may also minimise the trajectoryconvexity [START_REF] Flener | Automatic airspace sectorisation: A survey[END_REF], i.e. minimising the number of re-entries (a reentry corresponds to a flight that enters at least twice in the same sector) or ensuring the minimum dwell time [START_REF] Flener | Automatic airspace sectorisation: A survey[END_REF], i.e. minimising the total number of short transits (a short transit corresponds to a flight that spends less than x minutes in a sector, e.g. 4 minutes). In the context of the VP-755 exercise, we assume that these two objectives are not essential, since they are intrinsic to the traffic and the building blocks. They are more useful to design the airspace building blocks since the same sectorisation methodology can be applied to very small cells of airspace [START_REF] Sergeeva | Dynamic airspace configurations generated by evolutionary algorithms[END_REF].

Finally, resulting sectors must respect two hard constraints:

• minimum size: a sector must contain at least one block;

• connectivity: a sector can not be fragmented i.e. its different elements must be connected.

III. DETERMINING AN INITIAL GOOD SOLUTION A. Exploring the complexity

If the connectivity constraint is not considered, the number of solutions is given by the second Stirling number S(n, k):

S(n, k) = 1 k! k j=0 (-1) k-j k j j n ,
where n is the number of building blocks, k is the number of parts,

k j is the binomial coefficient k! j!(k -j)!
For instance, for 8 positions to be opened in the Reims ACC, we have 1.3 × 10 14 possible solutions with the conventional 21 blocks and 2.0 × 10 33 with 42 blocks. It is impossible to assess such a number of sector configurations in a reasonable time. But the Reims controllers do not exploit much more than 79 control sectors including the 21 elementary sectors. If we only consider those sectors, we have a limited set of possible sector configurations: 180 315, going from 1 open position to 21 3 . To reach this result, we enumerate all the valid combinations with an exhaustive search tree. All branches not leading to a valid sector configuration are cut as soon as the connectivity constraint or graph coverage are broken.

We are then able to enumerate all the conventional sector configurations based on all the control sectors used by Reims controllers. To validate the method, we also did some tests in other French ACCs. The complexity of the Reims ACC is a bit smaller than other ACCs in terms of elementary sectors and control sectors. If we consider the Brest ACC, which is representative of the most complex European ACCs, we are able to enumerate all conventional sector configurations but there are much more than in Reims. We get 1.9 × 10 8 sector configurations from 1 to 18 positions. It is hence reasonable to assess all these configurations in a strategic timeframe (preparation of the sector configuration plan for the next day) but not in a tactical one. To apply the method to bigger ACCs like Brest, it would be necessary to find heuristics to increase the number of cuts in the search tree in order to only keep interesting sector configurations: e.g. eliminate configurations that would clearly conduct to an imbalance, independently of the traffic, like a configuration combining large and very small sectors.

B. Assessing the complexity

For each time period of the day, we have access to a database of sector configurations based on conventional sectors. Each sector configuration can be assessed for each of the following objectives: workload distribution, flow cut and if needed trajectory-convexity and minimum dwell-time. It is not necessary to assess the compactness since they are based on conventional sectors that are already accepted by controllers. Then, for each period, we sort each sector configuration according to the value of the n multi-objectives and look for min

P k ∈SC k (balance(P k ), cut(P k ), ..., f n (P k ))
where SC k is the set of configurations with k sectors f n is the n-th objective function.

It is rare to find a solution that minimises all the objectives and according to the theory of multi-objective optimisation, a solution P i k is said to dominate another one

P j k if ∀i ∈ 1, 2, ..., n,f i (P i k ) ≤ f i (P j k ) ∃j ∈ 1, 2, ..., n,f i (P i k ) < f i (P j k )
All solutions that are not dominated are said to be Pareto optimal. The set of Pareto optimal solutions forms the Pareto front. Solutions that are only dominated by solutions of the Pareto front form the 2 nd front, and so on. Following the assessment of the different sector configurations, it is possible to associate each configuration to a front, as illustrated in Figure 4. We limit the total number of solutions in the different fronts to only keep good solutions. For each time period of the day, we have a set of fronts in which we can pick good solutions. To form the sector configuration plan, i.e. the set of sector configurations to be executed, the different good solutions are combined throughout the day, as explained in section V. Next section explains how these solutions can be refined to improve them.

IV. REFINING INITIAL SOLUTIONS

Since the partitioning problem is NP-complete [START_REF] Brucker | On the complexity of clustering problems[END_REF], one efficient way to find, not the optimal solution, but a very good solution, consists in exploring metaheuristics. A complete and detailed review of the different techniques can be found in [START_REF] Bichot | Élaboration d'une nouvelle métaheuristique pour le partitionnement de graphe: la méthode de fusion-fission. Application au découpage de l'espace aérien[END_REF]. These techniques are very efficient if they can start with a good initial solution. In our case, such a solution is provided by exploring the catalogue of existing sector configurations.

Our stochastic algorithms rely on the Simulated Annealing (SA) metaheuristic [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF]. The main idea is to accept worse moves to not be stuck in a local optimum and to slowly decrease the frequency of acceptance as the search progresses. The progress is given by a temperature variable T , which is decreased at each iteration. Our objective is to explore new airspace configurations by exchanging building blocks, in order to check if criteria mentioned previously, e.g. the workload distribution, could be improved without degrading the compactness and consequently their acceptance by controllers. Our method is based on two successive simulated annealing algorithms: the first one will disorganise the initial solution to largely improve the balance and the cut. However, the resulting solution is often composed of ill-shaped sectors. The objective of the second algorithm is to make them compact.

During the first phase, the objective is to minimise the balance and the cut while keeping a good compactness. Then, we define the following objective function:

min αcut(P k ) + βbalance(P k ) + 1 compactness 2 (P k )
.

In our experiments, we chose for instance α = 0.1 and β = 0.9 to homogenise the two first terms. The goal of the third term with the compactness is to control the shape of the sectors but not necessarily to guarantee compact sectors. The outcome solution will be then refined during the second phase to be acceptable to controllers. This is done by optimising the compactness under the constraints of not worsening the balance and cut of the initial solution. The objective function to minimise is then min (1/compactness(P k )) such that balance(P k ) ≤ balance(P initial k ) cut(P k ) ≤ cut(P initial k ).

V. ELABORATE A STABLE SOLUTION OVER TIME

We have seen in section IV how to determine for each time period a large number of good solutions, through the use of Pareto fronts. The next step is to combine them to form a smooth sector configuration plan throughout the day. For two consecutive time periods, we must find two sector configurations that minimise the distance between both. It is a classic of the shortest path problems in graph that can be solved by applying the Bellman's Principle of Optimality [START_REF] Bellman | Dynamic programming and modern control theory[END_REF], for which we just have to define a distance function between two partitions. Gusfield introduces the notion of partitiondistance in [START_REF] Gusfield | Partition-distance: A problem and class of perfect graphs arising in clustering[END_REF]. Given two partitions P and P of the same graph G, he defines the distance D(P, P ) between these two partitions as the smallest sum of weights of any nodes of G whose removal causes the two induced partitions to be identical. This distance function is categorised by Yousefi et al. as a shared-cell metric [START_REF] Yousefi | Trigger metrics for dynamic airspace configuration[END_REF]. Based on the blocks shared or not by the different sectors, it measures the degree of difference between two sectorisations. Yousefi et al. also introduces another metric based on the Hausdorff distance [START_REF] Gregoire | Hausdorff distance between convex polygons[END_REF]. It is purely based on the geometric differences between two partitions. Some additional details about associated reconfiguration complexity metrics can be found in [START_REF] Zelinski | Comparing methods for dynamic airspace configuration[END_REF]. It should be noted that these metrics can measure a distance between two configurations even if the number of sector changes.

We define a distance based on the shared-cell metric:

distance(P k (δt), P k (δt )) = j ∈R tt D j (δt) + D j (δt ) 2
where

R tt = min(k,k ) i=0 v∈Si(δt),v∈Si(δt )
v is the set of cells that do not change after reconfiguration.

This distance is defined as the total density workload of the building blocks that are moved from a subset S i to another while switching from the first partition to the second one. To reflect the reality of operations, we alter the results to favour the collapsing/de-collapsing operations. A collapsing operation corresponds to two sectors that are merged together to form a unique sector. A de-collapsing option corresponds to the splitting of a sector. In such cases, we consider that these operations are the least disturbing for the controllers and we sum 0 instead of D j (δt) + D j (δt ).

Once we have defined the distance between two sector configurations, we apply a shortest path algorithm to determine the sector configuration plan that minimises the total distance, which is the sum of the distances between the different sector configurations composing the plan. It should be noted that the transition between two sector configurations only depends on the previous configuration. However, once one is chosen, some interesting future transitions are eliminated and it is not possible to come back to one of them without deteriorating the smoothness. Such a process is already known from controllers who may decide to break the smoothness to switch to another succession of transitions. With a shortest path algorithm, we can better explore the catalogue of sector configurations and have a smooth plan for the entire day.

VI. RESULTS

A. Protocol

A reference scenario was provided by DSNA, the French Air Navigation Service Provider. This scenario contains the sector configuration plan of a very busy day (2015, June 26 th ), i.e. the different sectors that were opened for each time period this day. Traffic data were provided by EUROCONTROL in the DDR2 format [27]. One of the purposes of the VP-755 exercise was to explore the granularity of building blocks on the sectorisation process. For this reason, a set of new building blocks was manually designed with the expertise of an operational expert from Reims. Whereas Reims controllers use 21 blocks nowadays, we explored in this study the use of 42 manually designed blocks. These blocks do not necessarily correspond to the cutting of a 21-block into two blocks but to a further refinement according to major flows (see Figure 5). The optimisation process follows four steps. During the first step, all the possible sector configurations with the 79 conventional sectors are enumerated (see section III-A). In a second step, according to the sector configuration plan from DSNA, sector configurations for each time period are classified into Pareto fronts (see section III-B). The third step consists in refining the solutions of each first front with a good balance 4(see section IV). The refined configurations are injected in the catalogue of conventional configurations. In the final step, conventional and refined configurations are classified into Pareto fronts again and used by the smoothing algorithm to determine a configuration plan stable over time (see section V). We chose to limit the maximum number of Pareto solutions for each time period to 200, which is sufficient to have a plan mainly based on collapsing/decollapsing operations. Our tests show that we need to increase this number to 500 if we want a plan entirely based on collapsing/decollapsing operations. However, this will increase the computation time and may inject less optimal configurations in the plan.

In the next paragraphs, we will discuss the results of the refining algorithm and the final plan found by the smoothing algorithm.

B. Refining algorithm results

In this section, we have a look at a solution found for the period 07:08 -09:05, where 6 positions were opened. 15 configurations were present in the first front and we will focus on the refinement of a randomly chosen solution denoted by P 14 6 . This solution illustrates most of the characteristics of the found solutions. The figure 6 shows the initial and refined configurations and exploded views of both.

The refined configuration is based on three conventional sectors (LFEE4N, LFEEKD4R and LFEEKHEH), rediscovered by the refining algorithm, and three new sectors. The algorithm decides to collapse LFEEUKBN and LFEEHBN, which were clearly underloaded, into the single sector LFEE4N. One of the sectors is a bit more overloaded (LFEEKD4R) but this sector is interesting because it contains major flows from East and South to the Paris TMA (Terminal Manoeuvring Area): the number of transfers is relatively small compared to other sectors. However, even if this sector is conventional, it is not often exploited by controllers because its large size makes it difficult for them to precisely visualise it on the Operational Display Systems.

Table I shows the values of the objective functions of the initial, unstructured and well-shaped solutions. Since the goal of the refining process is to minimise balance and cut and maximise compactness, we see that the balance is very good at the end of the disorganising phase but the compactness is not so good and needs to be reworked to be acceptable to controllers. At the end of the refining phase, the solution is not so well-balanced but well-shaped without degrading the metrics of the initial configuration. Table III shows that all sectors are compact except "HF KF UF2 XF2", which is described with only two prisms. A sector with two prisms often corresponds to a sector with one balcony, which is acceptable to controllers if it is justified. It should be noted that the initial solution already contains a sector with one balcony (see table II).

C. Smoothing algorithm results

In this section, we focus on the properties of the resulting sector configuration plan. We compared this plan to the reference operational plan and a best-balanced plan. The latter is formed by juxtaposing the best-balanced configuration for each time period, without considering cut or stability objectives. The results of those different plans are presented in the following graphics.

Figure 7a shows that the balance of the resulting plan is often better than the reference plan and does not reach excessive values. The average balance gain is equal to 12.9%. The curve OptimizedPlan bestBalance m1 shows that there are better balanced configurations but using those configurations will probably lead to an instability over time.

Figure 7b shows that the cut of the resulting plan is often a bit better than the reference plan. The average cut gain is equal to 3.4%. Compared to balance, it is not so easy to reach high gains because any other sectorisation would also cut flows somewhere.

As shown in figure 7c, the compactness oscillates between 0.95 and 1, a good performance, which suggests a large acceptability by controllers.

Figure 8a shows the stability of the configuration plan. The curve OptimizedPlan bestBalance m1 shows that a plan with the best-balanced configurations is very unstable; there are too many differences between each sector configuration. The stability of the smooth plan is similar to the stability of the To assess stability over time, we also implemented the Hausdorff metric [START_REF] Yousefi | Trigger metrics for dynamic airspace configuration[END_REF] (see Figure 8b). It also shows that a plan with the best-balanced configurations is very unstable. We can see that the smooth plan is as stable as the reference plan except that there are two peaks. It would be possible to remove those peaks by considering this metric to measure the distance between two configurations in the smoothing algorithm instead of the cell-based metric. In all cases, it confirms the results given by the cell-based metric. We are able to build a plan as stable as the operational plan, as compact as the operational plan, and improving the workload distribution and the number of transfers.

Finally, we study the robustness of this plan (see Figure 9). Instead of using flight plans, we assess the balance of this plan with corresponding real trajectories. As expected, compared to the assessment with the flight plans used to elaborate the optimisation, the plan is slightly less balanced. Nevertheless, the final average balance gain is equal to 12% whereas the initial assessment gives 12.9%, which demonstrates a good robustness.

VII. CONCLUSION AND PERSPECTIVES

We described in this paper a new approach using deterministic and stochastic methods to assess and Balance along the day -comparison between the flight plan assessment (M1) and the trajectory assessment (M3) refine sector configurations based on conventional sectors and combine them into a smooth sector configuration plan. The application of this method to the Reims scenario of the SESAR VP-755 exercise [START_REF] Dubot | Modelling, generating and evaluating sector configuration plans methodology report of the SESAR VP-755 exercise[END_REF] demonstrates the possibility to improve several criteria, such as the workload distribution (average gain of 12%) along the day, without degrading the compactness of the configurations, and hence build a smooth configuration with reasonable transition costs.

Such algorithms could be integrated in a decision support tool provided to operational experts in charge of building and updating the sector configuration plans, notably to help them to deal with the dynamicity required by free route operations and traffic uncertainty. Enumerating all sector configurations is time-consuming but would only need to be done when a new sector design is implemented. Then conventional and optimised solutions would be rapidly provided to operational experts. Fine-tuned solutions generated by stochastic algorithms using the Simulated Annealing metaheuristic would be proposed to operational experts for addition to the catalogue, if deemed acceptable to air traffic controllers. Such an acceptance, and the associated training required, should be assessed within the framework of SESAR 2020 Advanced Airspace Management exercises. Besides, the last algorithm would help operational experts to build a smooth sector configuration plan in line with the operational need of stability for controllers and would bring more reactivity in case of crisis management.

As mentioned during the VP-755 exercise, several algorithms could hence co-exist within such as tool, depending on the considered time horizon (uncertainty of the traffic demand and necessity to rapidly compute solutions). The methods presented in this paper could support the development of some of these algorithms, but the final tool would certainly require to complement them with other methods. Many evolutions are already foreseen, such as:

• the application of this method to a larger number of blocks, for instance automatically generated by EURO-CONTROL SAGA algorithm [28]; • the use of multi-objective optimisation methods applied to graph partitioning [START_REF] Rummler | Graph partitioning revised -a multiobjective perspective[END_REF] to easily build Pareto fronts with multiple objectives; • the use of an overload constraint based on occupancy "peak" and "sustain" values, that need to be defined for each new sector, in the same way as the Monitor Alert Parameter [START_REF] Drew | A method of optimally combining sectors[END_REF]; • the refinement of the flow cut objective to integrate transfers from neighbouring ACC; • the use of trackflows to guide the selection of proposed configurations thanks to the respective weights of trajectories options for the flights, combined with complexity metrics [31].

Figure 1 .

 1 Figure 1. 21 Reims building blocks (a) vs. their graph representation (b)

2 8- 10

 210 November 2016 Hosted by Technical University of Delft, the Netherlands

Figure 2 .

 2 Figure 2. Sector LFEEUE composed of two contiguous prisms

Figure 3 .

 3 Figure 3. Flight Levels (FL) of the floor of the Reims ACC airspace

Figure 4 .

 4 Figure 4. Example of Pareto fronts with two objectives

Figure 5 .

 5 Figure 5. 42 Reims blocks (some are covered by top blocks)

Figure 6 .

 6 Figure 6. From the initial solution P 14 6 , at the top, to its refinement, at the bottom

6 8- 10

 610 November 2016 Hosted by Technical University of Delft, the Netherlands

Figure 7 .

 7 Figure 7. Balance (a), cut (b) and compactness (c) along the day

  Figure 8. Cell-based (a) and Hausdorff distances (b) along the day

TABLE I VALUES

 I OF THE OBJECTIVE FUNCTIONS OF THE SOLUTION P14

						6
	Solution step by step	Balance	Cut	Compactness
	Initial solution			16.02	121.03	0.759
	Unstructured solution		2.432	126.67	0.653
	Well-shaped solution		8.434	111.28	0.939
			TABLE II
	SECTOR METRICS OF THE INITIAL SOLUTION P 14 6
	Sector S	D S		C S		Compactness	Prisms
	LFEESE4H	9.633	57.948	0.759	3
	LFEEUKBN	4.313	18.974	1.0	2
	LFEEKD2F	9.845	52.820	1.0	5
	LFEEHBN	2.483	16.410	1.0	1
	LFEE4R	8.417	42.051	1.0	2
	LFEEE4E	9.739	53.846	1.0	2
			TABLE III
	SECTOR METRICS OF THE REFINED SOLUTION P 14 6r
	Sector S		D S		C S	Compactness	Prisms
	LFEEKHEH		7.394	29.743	1.0	1
	HF KF UF2 XF2		5.497	52.820	0.939	2
	LFEEKD4R	11.622	41.538	1.0	5
	E UE XE		5.923	34.871	1.0	2
	SE UF1 UH XF1 XH	7.198	42.564	1.0	2
	LFEE4N		6.797	21.025	1.0	2

In the reality of operations, only a maximum of 17 positions are opened simultaneously.

8-10 November 2016 Hosted by Technical University of Delft, the Netherlands

8-10 November 2016 Hosted by Technical University of Delft, the Netherlands

We can find in the first front ill-balanced but very well-cut solutions. We decided to give priority to well-balanced configurations.

ACKNOWLEDGEMENT

Authors would like to thank Nathalie Bartoli, Julien Bourget and Antoine Joulia for their constructive suggestions during the reviewing of this paper. They would also like to express their gratitude to their ONERA colleagues and DSNA partners for the execution of the VP-755 exercise: Sébastien Aubry, Thomas Chaboud, Stéphane Degrémont, Rémi Lafage, Isabelle Luxembourg, Sylvain Mondou and Valérie Neyns. This study was co-financed by the European Union, through the SESAR Joint Undertaking. Authors would like to thank Kris Delcourte, project manager of the SESAR 07.05.04 project and all the European partners involved in this project.


Mohamed Ben Ellefi
email: benellefi@lirmm.fr

Zohra Bellahsene

Stefan Dietze
email: dietze@l3s.de

Konstantin Todorov
email: todorov@lirmm.fr

Dataset Recommendation for Data Linking: an Intensional Approach

With the growing quantity and diversity of publicly available web datasets, most notably Linked Open Data, recommending datasets, which meet specific criteria, has become an increasingly important, yet challenging problem. This task is of particular interest when addressing issues such as entity retrieval, semantic search and data linking. Here, we focus on that last issue. We introduce a dataset recommendation approach to identify linking candidates based on the presence of schema overlap between datasets. While an understanding of the nature of the content of specific datasets is a crucial prerequisite, we adopt the notion of dataset profiles, where a dataset is characterized through a set of schema concept labels that best describe it and can be potentially enriched by retrieving their textual descriptions. We identify schema overlap by the help of a semantico-frequential concept similarity measure and a ranking criterium based on the tf*idf cosine similarity. The experiments, conducted over all available linked datasets on the Linked Open Data cloud, show that our method achieves an average precision of up to 53% for a recall of 100%. As an additional contribution, our method returns the mappings between the schema concepts across datasets -a particularly useful input for the data linking step.

Introduction

With the emergence of the Web of Data, in particular Linked Open Data (LOD) [START_REF] Bizer | Linked data -the story so far[END_REF], an abundance of data has become available on the web. Dataset recommendation is becoming an increasingly important task to support challenges such as entity interlinking [START_REF] Nunes | Combining a co-occurrence-based and a semantic measure for entity linking[END_REF], entity retrieval or semantic search [START_REF] Blanco | Effective and efficient entity search in rdf data[END_REF]. Particularly with respect to interlinking, the current topology of the LOD cloud underlines the need for practical and efficient means to recommend suitable datasets: currently, only very few, well established knowledge graphs show a high amount of inlinks, with DBpedia being the most obvious target [START_REF] Schmachtenberg | Adoption of the linked data best practices in different topical domains[END_REF], while a large amount of datasets is largely ignored. This is due in part to the challenge to identify suitable linking candidates without prior knowledge of the available datasets and their characteristis. Linked datasets vary significantly with respect to represented resource types, currentness, coverage of topics and domains, size, used languages, coherence, accessibility [START_REF] Buil-Aranda | Sparql webquerying infrastructure: Ready for action?[END_REF] or general quality aspects [START_REF] Guéret | Assessing linked data mappings using network measures[END_REF]. This heterogeneity poses significant challenges for data consumers when attempting to find useful datasets. Hence, a long tail of datasets from the LOD cloud1 has hardly been reused and adopted, while the majority of data consumption, linking and reuse focuses on established knowledge graphs such as DBpedia [START_REF] Auer | Dbpedia: A nucleus for a web of open data[END_REF] or YAGO [START_REF] Suchanek | Yago: a core of semantic knowledge[END_REF].

In line with [START_REF] Lopes | Two approaches to the dataset interlinking recommendation problem[END_REF], we define dataset recommendation as the problem of computing a rank score for each of a set of datasets D T (for Target Dataset) so that the rank score indicates the relatedness of D T to a given dataset, D S (for Source Dataset). The rank scores provide information of the likelihood of a D T dataset to contain linking candidates for D S .

We adopt the notion of a dataset profile, defined as a set of concept labels that describe the dataset. By retrieving the textual descriptions of each of these labels, we can map the label profiles to larger text documents. This representation provides richer contextual and semantic information and allows to compute efficiently and inexpensively similarities between profiles.

Although different types of links can be defined across datasets, here we focus on the identity relation given by the statement "owl:sameAs". Our working hypothesis is simple: datasets that share at least one concept, i.e., at least one pair of semantically similar concept labels, are likely to contain at least one potential pair of instances to be linked by a "owl:sameAs" statement. We base our recommendation procedure on this hypothesis and propose an approach in two steps: [START_REF] Bizer | Linked data -the story so far[END_REF] for every D S , we identify a cluster 2 of datasets that share schema concepts with D S and (2) we rank the datasets in each cluster with respect to their relevance to D S .

In step [START_REF] Bizer | Linked data -the story so far[END_REF], we identify concept labels that are semantically similar by using a similarity measure based on the frequency of term co-occurence in a large corpus (the web) combined with a semantic distance based on WordNet without relying on string matching techniques [START_REF] Han | Umbc ebiquitycore: Semantic textual similarity systems[END_REF]. For example, this allows to recommend to a dataset annotated by "school" one annotated by "college". In this way, we form clusters of "comparable datasets" for each source dataset. The intuition is that for a given source dataset, any of the datasets in its cluster is a potential target dataset for interlinking.

Step [START_REF] Nunes | Combining a co-occurrence-based and a semantic measure for entity linking[END_REF] focuses on ranking the datasets in a D S -cluster with respect to their importance to D S . This allows to evaluate the results in a more meaningful way and of course to provide quality results to the user. The ranking criterium should not be based on the amount of schema overlap, because potential to-link instances can be found in datasets sharing 1 class or sharing 100. Therefore, we need a similarity measure on the profiles of the comparable datasets. We have proceeded by building a vector model for the document representations of the profiles and computing cosine similarities.

To evaluate the approach, we have used the current topology of the LOD as evaluation data (ED). As mentioned in the beginning, the LOD link graph is far from being complete, which complicates the interpretation of the obtained results-many false positives are in fact missing positives (missing links) from the evaluation data-a problem that we discuss in detail in the sequel. Note that as a result of the recommendation process, the user is not only given candidate datasets for linking, but also pairs of classes where to look for identical instances. This is an important advantage allowing to run more easily linking systems like SILK [START_REF] Volz | Silk -A link discovery framework for the web of data[END_REF] in order to verify the quality of the recommendation and perform the acutal linking. Our experimental tests with SILK confirm the hypothesis on the incompleteness of the ED.

To sum up, the paper contains the following contributions: (1) new definitions of dataset profiles based on schema concepts, (2) a recommendation framework allowing to identify the datasets sharing schema with a given source dataset, (3) an efficient ranking criterium for these datasets, (4) an output of additional metadata such as pairs of similar concepts across source and target datasets, (5) a large range of reproducible experiments and in depth analysis with all of our results made available.

We proceed to present the theoretical grounds of our technique in Section 2. Section 3 defines the evaluation framework that has been established and reports on our experimental results. Related approaches are presented and discussed in Section 4 before we conclude in Section 5.

A Dataset Interlinking Recommendation Framework

Our recommendation approach relies on the notion of a dataset profile, providing comparable representations of the datasets by the help of characteristic features. In this section, we first introduce the definitions of a dataset profile that we are using in this study. Afterwards, we describe the profile-based recommendation technique that we apply.

Intensional Dataset Profiles

A dataset profile is seen as a set of dataset characteristics that allow to describe in the best possible way a dataset and that separate it maximally from other datasets. A feature-based representation of this kind allows to compute distances or measure similarities between datasets (or for that matter profiles), which unlocks the dataset recommendation procedure. These descriptive characteristics, or features, can be of various kinds (statistical, semantic, extensional, etc.). As we observe in [START_REF] Ellefi | Towards semantic dataset profiling[END_REF], a dataset profile can be defined based on a set of types (schema concepts) names that represent the topic of the data and the covered domain. In line with that definition, we are interested here in intensional dataset characteristics in the form of a set of keywords together with their definitions that best describe a dataset. Definition 1 (Dataset Label Profile). The label profile of a dataset D, denoted by P l (D), is defined as the set of n schema concept labels corresponding to D:

P l (D) = {L i } n i=1 .
Note that the representativity of the labels in P l (D) with respect to D can be improved by filtering out certain types. We rely on two main heuristics: (1) remove too popular types (such as foaf:Person), (2) remove types with too few instances in a dataset. These two heuristics are based on the intuition that the probability of finding identical instances of very popular or underpopulated classes is low. We support (1) experimentally in Section 3 while we leave (2) for future work.

Each of the concept labels in P l (D) can be mapped to a text document consisting of the label itself and a textual description of this label. This textual description can be the definition of the concept in its ontology, or any other external textual description of the terms composing the concept label. We define a document profile of a dataset in the following way.

Definition 2 (Dataset Document Profile). The document profile of a dataset D, P d (D), is defined as a text document constructed by the concatenation of the labels in P l (D) and the textual descriptions of the labels in P l (D).

Note that there is no substantial difference between the two definitions given above. The document profile is an extended label profile, where more terms, coming from the label descriptions, are included. This allows to project the profile similarity problem onto a vector space by indexing the documents and using a term weighting scheme of some kind (e.g., tf*idf).

By the help of these two definitions, a profile can be constructed for any given dataset in a simple and inexpensive way, independent on its connectivity properties on the LOD. In other words, a profile can be easily computed for datasets that are already published and linked, just as for datasets that are to be published and linked, allowing to use the same representation for both kinds of datasets and thus allowing for their comparison by the help of feature-based similarity measures.

As stated in the introduction, we rely on the simple intuition that datasets with similar intension have extensional overlap. Therefore, it suffices to identify at least one pair of semantically similar types in the schema of two datasets in order to select these datasets as potential linking candidates. We are interested in the semantic similarity of concept labels in the dataset label profiles. There are many off-the-shelf similarity measures that can be applied, known from the ontology matching literature. We have focused on the well known semantic measures Wu Palmer [13] and Lin's [START_REF] Lin | An information-theoretic definition of similarity[END_REF], as well as the UMBC [START_REF] Han | Umbc ebiquitycore: Semantic textual similarity systems[END_REF] measure that combines semantic distance in WordNet with frequency of occurrence and co-occurrence of terms in a large external corpus (the web). We provide the definition of that measure, since it is less well-known and it showed to perform best in our experiments. For two labels, x and y, we have

sim UMBC (x, y) = sim LSA (x, y) + 0.5e -αD(x,y) , (1)
where sim LSA (x, y) is the Latent Semantic Analysis (LSA) [START_REF] Deerwester | Indexing by latent semantic analysis[END_REF] word similarity, which relies on the words co-occurrence in the same contexts computed in a three billion words corpus3 of good quality English. D(x, y) is the minimal WordNet [START_REF] Miller | Wordnet: A lexical database for english[END_REF] path length between x and y. According to [START_REF] Han | Umbc ebiquitycore: Semantic textual similarity systems[END_REF], using e -αD(x,y) to transform simple shortest path length has shown to be very efficient when the parameter α is set to 0.25. With a concept label similarity measure at hand, we introduce the notion of dataset comparability, based on the existence of shared intension.

Definition 3 (Comparable Datasets). Two datasets D and D are comparable if there exists L i and L j such that

L i ∈ P l (D ), L j ∈ P l (D ) and sim UMBC (L i , L j ) ≥ θ, where θ ∈ [0, 1].

Recommendation Process: the CCD-CosineRank approach

A dataset recommendation procedure for the linking task returns, for a given source dataset, a set of target datasets ordered by their likelihood to contain instances identical to those in the source dataset.

Let D S be a source dataset. We introduce the notion of a cluster of comparable datasets related to D S , or CCD(D S ) for short, defined as the set of target datasets, denoted by D T , that are comparable to D S according to Def. 3. Thus, D S is identified by its CCD and all the linking candidates D T for this dataset are found in its cluster, following our working hypothesis.

Finally, we need a ranking function that assigns scores to the datasets in CCD(D S ) with respect to D S expressing the likelihood of a dataset in CCD(D S ) to contain identical instances with those of D S . To this end, we need a similarity measure on the dataset profiles.

We have worked with the document profiles of the datasets (Def. 2). Since datasets are represented as text documents, we can easily build a vector model by indexing the documents in the corpus formed by all datasets of interestthe ones contained in one single CCD. We use a tf*idf weighting scheme, which allows to compute the cosine similarity between the document vectors and thus assign a ranking score to the datasets in a CCD with respect to a given dataset from the same CCD. Note that this approach allows to consider the information of the intensional overlap between datasets prior to ranking and indexing -we are certain to work only with potential linking candidates when we rank, which improves the quality of the ranks. For a given dataset D S , the procedure returns datasets from CCD(D S ), ordered by their cosine similarity to D S .

Finally, an important outcome of the recommendation procedure is the fact that, along with an ordered list of linking candidates, the user is provided the pairs of types of two datasets-a source and a target-where to look for identical instances. This information facilitates considerably the linking process, to be performed by an instance matching tool, such as SILK.

Application of the Approach: an Example

We illustrate our approach by an example. We consider education-data-gov-uk4 as a source dataset (D S ). The first step consists in retrieving the schema concepts from this dataset and constructing a clean label profile (we filter out noisy labels, as discussed above), as well as its corresponding document profile (Def. 1 and Def. 2, respectively). We have P l (education-data-gov-uk) = {London Borough Ward, School, Local Learning Skills Council, Adress}. We perform a semantic comparison between the labels in P l (education-data-gov-uk) and all labels in the profiles of the accessible LOD datasets. By fixing θ = 0.7, we generate CCD(education-data-gov-uk) containing the set of comparable datasets D T , as described in Def. 3. The second step consists of ranking the D T datasets in CCD(education-data-gov-uk) by computing the cosine similarity between their document profiles and P d (education-data-gov-uk). The top 5 ranked candidate datasets to be linked with education-data-gov-uk are (1) rkb-explorercourseware5 , (2) rkb-explorer-courseware6 , (3) rkb-explorer-southampton7 , (4) rkb-explorer-darmstadt8 , and (5) oxpoints 9 .

Finally, for each of these datasets, we retrieve the pairs of shared (similar) schema concepts extracted in the comparison part:

-education-data-gov-uk and statistics-data-gov-uk share two labels "London Borough Ward" and "LocalLearningSkillsCouncil".

-education-data-gov-uk and oxpoints contain similar labels which are, respectively, "School" and "College", for the SILK results see Section 3.5.

Experiments and Results

We proceed to report on the experiments conducted in support of the proposed recommendation method.

Evaluation Framework

The quality of the outcome of a recommendation process can be evaluated along a number of dimensions. Ricci et al. [START_REF] Ricci | Recommender systems handbook[END_REF] provide a large review of recommender systems evaluation techniques and cite three common types of experiments: (i) offline experiments, where recommendation approaches are compared without user interaction, (ii) user studies, where a small group of subjects experiments with the system and reports on the experience, and (iii) online experiments, where real user populations interact with the system.

For the task of dataset recommendation, the system suggests to the user a list of n target datasets candidates to be linked to a given source dataset. There does not exist a common evaluation framework for the datasets recommendation, thus, we evaluate our method with an offline experiment by using a pre-collected set of linked data considered as evaluation data (ED). The most straightforward, although not unproblematic (see below) choice of evaluation data for the data linking recommendation task is the existing link topology of the current version of the LOD cloud.

In our recommendation process, for a given source dataset D S , we identify a cluster of target datasets, D T , that we rank with respect to D S (cf. Section 2.2). To evaluate the quality of the recommendation results given the ED of our choice, we compute the common evaluation measures for recommender systems, precision and recall, defined as functions of the true positives (TP), false positives (FP), true negatives (TN) and false negatives (FN) as follows:

P r = T P T P + F P ; Re = T P T P + F N . ( 2
)
The number of potentially useful results that can be presented to the user has to be limited. Therefore, to assess the effectiveness of our approach, we rely on the measure of precision at rank k denoted by P @k. Complementarily, we evaluate the precision of our recommendation when the level of recall is 100% by using the mean average precision at Recall = 1, MAP@R, given as:

M AP @R = Total D S q=1 P r@R(q) Total D S , (3)
where R(q) corresponds to the rank, at which recall reaches 1 for the qth dataset and Total D S is the entire number of source datasets in the evaluation.

Experimental Setup

We started by crawling all available datasets in the LOD cloud group on the Data Hub10 in order to extract their profiles. In this crawl, only 90 datasets were accessible via endpoints or via dump files. In the first place, for each accessible dataset, we extracted its implicit and explicit schema concepts and their labels, as described in Def. 1. The explicit schema concepts are provided by resource types, while the implicit schema concepts are provided by the definitions of a resource properties [START_REF] Gottron | A systematic investigation of explicit and implicit schema information on the linked open data cloud[END_REF]. As noted in Section 2, some labels such as "Group", "Thing", "Agent", "Person" are very generic, so they are considered as noisy labels. To address this problem, we filter out schema concepts described by generic vocabularies such as VoID11 , FOAF 12 and SKOS 13 . The dataset document profiles, as defined in Def. 2, are constructed by extracting the textual descriptions of labels by querying the Linked Open Vocabularies14 (LOV) with each of the concept labels per dataset.

To form the clusters of comparable datasets from Def. 3, we compute the semantico-frequential similarity between labels (given in eq. ( 1)). We apply this measure via its available web API service 15 . In addition, we tested our system with two more semantic similarity measures based on WordNet: Wu Palmer and Lin's. For this purpose, we used the 2013 version of the W S4J 16 java API.

The evaluation data (ED) corresponds to the outgoing and incoming links extracted from the generated VoID file using the datahub2void tool 17 . It is made available on http://www.lirmm.fr/benellefi/void.ttl. We note that out of 90 accessible datasets, only those that are linked to at least one accessible dataset in the ED are evaluated in the experiments.

Evaluation Results

We started by considering each dataset in the ED as an unlinked source (newly published) dataset D S . Then, we ran the CCD-CosineRank workflow, as described in Section 2.2. The first step is to form a CCD(D S ) for each D S . The CCD construction process depends on the similarity measure on dataset profiles. Thus, we evaluated the CCD clusters in terms of recall for different levels of the threshold θ (cf. Def. 3) for the three similarity measures that we apply. We observed that the recall value remains 100% in the following threshold intervals per similarity measure: Wu Palmer: θ ∈ [0, 0.9]; Lin: θ ∈ [0, 0.8]; UMBC:

θ ∈ [0, 0.7].
The CCD construction step ensures a recall of 100% for various threshold values, which will be used to evaluate the ranking step of our recommendation process by the Mean Average Precision (MAP@R) at the maximal recall level, as defined in Def. 3. The results in Fig. 1 show highest performance of the UMBC's measure with a M AP @R ∼ = 53% for θ = 0.7, while the best MAP@R values for Wu Palmer and Lin's measures are, respectively, 50% for θ = 0.9 and 51% for θ = 0.8. Guided by these observations, we evaluated our ranking in terms of precision at ranks k = {5, 10, 15, 20}, as shown in Table 1. Based on these results, we choose UMBC at a threshold θ = 0.7 as a default setting for CCD-CosineRank, since it performs best for three out of four k-values and it is more stable than the two others especially with MAP@R.

Baselines and Comparison

To the best of our knowledge, there does not exist a common benchmark for dataset interlinking recommendation. Since our method uses both label profiles and document profiles, we implemented two recommendation approaches to be Fig. 1. The MAP@R of our recommender system by using three different similarity measures for different similarity threshold values considered as baselines -one using document profiles only, and another one using label profiles: Doc-CosineRank : All datasets are represented by their document profiles, as given in Def. 2. We build a vector model by indexing the documents in the corpus formed by all available LOD datasets (no CCD clusters). We use a tf*idf weighting scheme, which allows us to compute the cosine similarity between the document vectors and thus assign a ranking score to each dataset in the entire corpus with respect to a given dataset D S . UMBCLabelRank: All datasets are represented by their label profiles, as given in Def. 1. For a source dataset D S , we construct its CCD(D S ) according to Def. 3 using UMBC with θ = 0.7. Thus, D S is identified by its CCD and all target datasets D T are found in its cluster. Let AvgUMBC be a ranking function that assigns scores to each D T in CCD(DS), defined by:

AvgUMBC(D , D ) = |P l (D )| i=1 |P l (D )| j=1 max sim U M BC (L i , L j ) max(|P l (D )|, |P l (D )|) , (4)
where L i in P l (D ) and L j in P l (D ).

Fig. 2 depicts a detailed comparison of the precisions at recall 1 obtained by the three approaches for each D S taken as source dataset. It can be seen that the CCD-CosineRank approach is more stable and largely outperforms the two other approaches by an MAP@R of up to 53% as compared to 39% for UMBCLabelRank and 49% for CCD-CosineRank. However, the UMBCLabelRank approach produces better results than the other ones for a limited number of Measure \ P@k P@5 P@10 P@15 P@20 WU Palmer (θ = 0.9) 0, 56 0, 52 0.53 0.51 Lin (θ = 0.8) 0.57 0.54 0.55 0.51 UMBC (θ = 0.7) 0.58 0.54 0.53 0.53 Table 1. Precision at 5, 10, 15 and 20 of the CCD-CosineRank approach using three different similarity measures over their best threshold values based on Fig. 1 source datasets, especially in the case when D S and D T share a high number of identic labels in their profiles.

The performance of the CCD-CosineRank approach demonstrates the efficiency and the complementarity of combining in the same pipeline (i) the semantic similarity on labels for identifying recommendation candidates (CCD construction process) and (ii) the frequential document cosine similarity to rank the candidate datasets. We make all of the ranking results of the CCD-CosineRank approach available to the community on http://www.lirmm.fr/benellefi/ CCD-CosineRank_Result.csv.

Discussion

We begin by a note on the vocabulary filtering that we perform (Section. 3.2). We underline that we have identified the types which improve/decrease the per-formance empirically. As expected, vocabularies, which are very generic and wide-spread have a negative impact, acting like hub nodes, which dilute the results. For comparison, the results of the recommendation before removal are made available on http://www.lirmm.fr/benellefi/RankNoFilter.csv.

The different experiments described above show a high performance of the introduced recommendation approach with an average precision of 53% for a recall of 100%. Likewise, it may be observed that this performance is completely independent of the dataset size (number of triples) or the schema cardinality (number of schema concepts by datasets). However, we note that better performance was obtained for datasets from the geographic and governmental domains with precision and recall of 100%. Naturally, this is due to the fact that a recommender system in general and particularly our system performs better with datasets having high quality schema description and datasets reusing existing vocabularies (the case for the two domains cited above), which is considered as linked data modeling best practice. An effort has to be made for improving the quality of the published dataset [START_REF] Ellefi | Datavore: A vocabulary recommender tool assisting linked data modeling[END_REF].

We believe that our method can be given a more fair evaluation if better evaluation data in the form of ground truth are used. Indeed, our results are impacted by the problem of false positives overestimation. Since data are not collected using the recommender system under evaluation, we are forced to assume that the false positive items would have not been used even if they had been recommended, i.e., that they are uninteresting or useless to the user. This assumption is, however, generally false, for example when the set of unused items contains some interesting items that the user did not select. In our case, we are using declared links in the LOD cloud as ED, which is certain but far from being complete for it to be considered as ground truth. Thus, in the recommendation process the number of false positives tends to be overestimated, or in other words an important number of missing positives in the ED translates into false positives in the recommendation process.

To further illustrate the effect of false positives overestimation, we ran SILK as an instance matching tool to discover links between D S and their corresponding D T s that have been considered as false positives in our ED. SILK takes as an input a Link Specification Language file, which contains the instance matching configuration. We recall that our recommendation procedure provides pairs of shared or similar types between D S and every D T in its corresponding CCD, which are particularly useful to configure SILK. However, all additional information, such as the datatype properties of interest, has to be given manually. This makes the process very time consuming and tedious to perform over the entire LOD. Therefore, as an illustration, we ran the instance matching tool on two flagship examples of false positive D T s:

Semantically Similar Labels: We choose education-data-gov-uk18 as a D S and its corresponding false positive D T oxpoints 19 . The two datasets contain in their profiles, respectively, the labels "School" and "College", detected as highly similar labels by the UMBC measure, with a score of 0.91. The instance matching gave as a result 10 accepted "owl:sameAs" links between the two datasets. Identical Labels: We choose rkb-explorer-unlocode20 as a D S and its corresponding D T s, which are considered as FP: yovisto21 datos-bcn-uk22 datosbcn-cl 23 . All 4 datasets share the label "Country" in their corresponding profiles. The instance matching process gave as a result a set of accepted "owl:sameAs" links between rkb-explorer-unlocode and each of the three D T .

We provide the set of newly discovered linksets to be added to the LOD topology and we made the generated linksets and the corresponding SILK configurations available on http://www.lirmm.fr/benellefi/Silk_Matching.

It should be noted that the recommendation results provided by our approach may contain some broader candidate datasets with respect to the source dataset. For example, two datasets that share schema labels such as books and authors are considered as candidates even when they are from different domains like science vs. literature. This outcome can be useful for predicting links such as "rdfs:seeAlso" (rather than "owl:sameAs"). We have chosen to avoid the inclusion of instance-related information in order to keep the complexity of the system as low as possible and still provide reasonable precision by guaranteeing a 100% recall.

As a conclusion, we outline three directions of work in terms of dataset quality that can considerably facilitate the evaluation of any recommender system in that field: (1) improving descriptions and metadata; (2) improving accessibility;

(3) providing a reliable ground truth and benchmark data for evaluation.

Related Work

With respect to finding relevant datasets on the Web, we cite briefly several studies on discovering relevant datasets for query answering. Based on wellknown data mining strategies, [START_REF] Wagner | Discovering related data sources in data-portals[END_REF] and [START_REF] Wagner | Entity-based data source contextualization for searching the web of data[END_REF] present techniques to find relevant datasets, which offer contextual information corresponding to the user queries. A feedback-based approach to incrementally identify new datasets for domainspecific linked data applications is proposed in [START_REF] De Oliveira | Feedback-based data set recommendation for building linked data applications[END_REF]. User feedback is used as a way to assess the relevance of the candidate datasets.

In the following, we cite approaches that have been devised for the datasets interlinking candidates recommendation task and which are, therefore, directly relevant to our work. Nikolov et al. [START_REF] Nikolov | Identifying relevant sources for data linking using a semantic web index[END_REF] propose a keyword-based search approach to identify candidate sources for data linking consisting of two steps: (i) searching for potentially relevant entities in other datasets using as keywords randomly selected instances over the literals in the source dataset, and (ii) filtering out irrelevant datasets by measuring semantic concept similarities obtained by applying ontology matching techniques.

Mehdi et al. [START_REF] Mehdi | Discovering domain-specific public SPARQL endpoints: a life-sciences use-case[END_REF] propose a method to automatically identify relevant public SPARQL endpoints from a list of candidates. First, the process needs as input a set of domain-specific keywords, which are extracted from a local source or can be provided manually by an expert. Then, using natural languages processing techniques and queries expansion techniques, the system generates a set of queries that seek to exact literal matches between the introduced keywords and the target datasets, i.e., for each term supplied to the algorithm, the system runs a comparison to a set of eight queries: {original-case, proper-case, lower-case, upper-case} × {no-lang-tag, @en-tag}. Finally, the produced output consists of a list of potentially relevant SPARQL endpoints of datasets for linking. In addition, an interesting contribution of this technique is the bindings returned for the subject and predicate query variables, which are recorded and logged when a term match is found on some particular SPARQL endpoint. The records are useful in the linking step.

Leme et al. [START_REF] Leme | Identifying candidate datasets for data interlinking[END_REF] present a ranking method for datasets with respect to their relevance for the interlinking task. The ranking is based on Bayesian criteria and on the popularity of the datasets, which affects the generality of the approach. The authors extend this work and overcome this drawback in [START_REF] Lopes | Two approaches to the dataset interlinking recommendation problem[END_REF] by exploring the correlation between different sets of features-properties, classes and vocabularies-and the links to compute new rank score functions for all the available linked datasets.

None of the studies outlined above have evaluated the ranking measure in terms of Precision/Recall, except for [START_REF] Lopes | Two approaches to the dataset interlinking recommendation problem[END_REF] which, according to the authors, achieves a mean average precision of around 60% and an excepted recall of 100% with rankings over all LOD datasets. However, a direct comparison to our approach seems unfair since the authors did not provide the list of the datasets and their rank performance by datasets considered as source.

In comparison to the work discussed above, our approach has the potential of overcoming a series of complexity related problems, precisely, considering the complexity to generate the matching in [START_REF] Nikolov | Identifying relevant sources for data linking using a semantic web index[END_REF], to produce the set of domain-specific keywords as input in [START_REF] Mehdi | Discovering domain-specific public SPARQL endpoints: a life-sciences use-case[END_REF] and to explore the set of features of all the network datasets in [START_REF] Lopes | Two approaches to the dataset interlinking recommendation problem[END_REF]. Our recommendation results are much easier to obtain since we only manipulate the schema part of the dataset. They are also easier to interpret and apply since we automatically recommend the corresponding schema concept mappings together with the candidate datasets.

Conclusion and Future Work

Following the linked data best practices, metadata designers reuse and build on, instead of replicating, existing RDF schema and vocabularies. Motivated by this observation, we propose the CCD-CosineRank interlinking candidate dataset recommendation approach, based on concept label profiles and schema overlap across datasets. Our approach consists of identifying clusters of comparable datasets, then, ranking the datasets in each cluster with respect to a given dataset. We discuss three different similarity measures, by which the relevance of our recommendation can be achieved. We evaluate our approach on real data coming from the LOD cloud and compare it two baseline methods. The results show that our method achieves a mean average precision of around 53% for recall of 100%, which reduces considerably the cost of dataset interlinking. In addition, as a post-processing step, our system returns sets of schema concept mappings between source and target datasets, which decreases considerably the interlinking effort and allows to verify explicitly the quality of the recommendation.

In the future, we plan to improve the evaluation framework by developing a more reliable and complete evaluation data for dataset recommendation. We plan to elaborate a ground truth based on certain parts of the LOD, possibly by using crowdsourcing techniques, in order to deal with the false positives overestimation problem. Further work should go into btaining high quality profiles, in particular by considering the population of the schema elements. We also plan to investigate the effectiveness of machine learning techniques, such as classification or clustering, for the recommendaiton task. One of the conclusions of our study shows that the recommendation approach is limited by the lack of accessibility, explicit metadata and quality descriptions of the datasets. As this can be given as an advice to data publishers, in the future, we will work on the development of recommendation methods for datasets with noisy and incomplete descriptions.

Fig. 2 .

 2 Fig. 2. Precisions at recall=1 of the CCD-CosineRank approach as compared to Doc-CosineRank and UMBCLabelRank

http://datahub.io/group/lodcloud

http://ebiquity.umbc.edu/resource/html/id/351

http://education.data.gov.uk/

http://courseware.rkbexplorer.com/

http://courseware.rkbexplorer.com/

http://southampton.rkbexplorer.com/

http://darmstadt.rkbexplorer.com/

https://data.ox.ac.uk/sparql/

http://datahub.io/group/lodcloud

http://rdfs.org/ns/void

http://xmlns.com/foaf/0.1/

http://www.w3.org/2004/02/skos/core

http://lov.okfn.org/dataset/lov/

http://swoogle.umbc.edu/SimService/

https://code.google.com/p/ws4j/

https://github.com/lod-cloud/datahub2void

http://education.data.gov.uk/

https://data.ox.ac.uk/sparql

http://unlocode.rkbexplorer.com/sparql/

http://sparql.yovisto.com/

http://data.open.ac.uk/query

 [START_REF] Nunes | Combining a co-occurrence-based and a semantic measure for entity linking[END_REF]We note that we use the term "cluster" in its general meaning, referring to a set of datasets grouped together by their similarity and not in a machine learning sense.

Acknowledgements

This research has been partially funded under the Datalyse project 24 -FSN-AAP Big Data n3-, by the European Commission-funded DURAARK project (FP7 Grant Agreement No. 600908) and the COST Action IC1302 (KEYSTONE).