Antonio Maccioni
email: maccioni@dia.uniroma3.it

Orlando Cassanon

Yongming Luo
email: y.luo@tue.nl

Juan-Carlos Castrejon-Castillo

Genoveva Vargas-Solar
email: genoveva.vargas-solar@imag.fr

Orlando Cassano
email: orlando.cassano@cetic.be

Juan Castrejón
email: juan.castrejon@imag.fr

NoXperanto: Crowdsourced Polyglot Persistence

Keywords: Crowdsourced Polyglot Persistence Polyglot Persistence, Crowdsourcing, Multidatabases, Big Data, Property Graph, Graph Databases

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Big datasets are not uniform collections of homogeneous data and, for this reason, they are not logically stored in one single database. In addition, the size of big datasets is such that it is not possible to adopt data cleaning, dataset preparation and integration using classic methods. Otherwise, data would never be ready for being analyzed and exploited in reasonable time.

Often, these datasets are sharded across distributed persistence supports that adopt different access and manage-ment policies, different degrees of availability, fault tolerance and consistency.

Polyglot Persistence [START_REF] Sadalage | NoSQL distilled: a brief guide to the emerging world of polyglot persistence[END_REF] is a brand new term to indicate the combination of approaches that cope with a variety of persistence systems and that are used for "integrating" heterogeneous datasets.

As part of the emerging polyglot persistence movement [START_REF] Sadalage | NoSQL distilled: a brief guide to the emerging world of polyglot persistence[END_REF], the simultaneous use of multiple SQL, NoSQL and NewSQL data stores is gradually becoming a common practice in modern application development [START_REF] Cooper | Spanner: Google's globally-distributed database[END_REF][START_REF] Borthakur | Petabyte scale databases and storage systems at facebook[END_REF]. They enable the integration of these data stores for managing big datasets in a scalable and loosely coupled way. This approach seems to be a pertinent strategy to deal with big datasets integration. Nonetheless, the combination of these heterogeneous data stores, flexible schemas and non-standard APIs, represent an added complexity for application developers. For instance, considering that data are spread across multiple data stores, each of which possibly relies on distinct data models (graph, document, etc.), developers must be familiar with a high number of implementation details, in order to effectively work with and maintain the overall data entities.

Providing an integrated view of the underlying data collections for enabling querying, is still an open issue, often solved at the application code level. Given that there is no uniformization of schemas and there is a lack of metainformation available about the data (i.e. mappings, metadata, semantic equivalences, data similarities), query results are not integrated collections of data, often, they are bags of non related data collections. It follows that, the quality of querying in such polyglot systems is poor.

Contribution. This paper proposes NoXperanto, a novel crowdsourcing1 approach to address querying over data collections managed by polyglot persistence settings.

We avoid the pursue of uniformity, but rather, we preserve the variety of original systems and languages. The main contribution of NoXperanto is the ability to solve complex queries involving different data stores by exploiting queries from expert users (i.e. a crowd of database administrators, data engineers, domain experts, etc.), assuming that these users can submit meaningful queries.

Crowds have been revealed to be effective to solve queries over a single database [START_REF] Franklin | Crowddb: answering queries with crowdsourcing[END_REF], but they have never been used to query a multi-database system, where the required expertise (about schemas, models, data formats and instances of the database) cannot be superficial. In fact, from the structure of the queries, we can infer who is expert.

NoXperanto exploits the results of such "meaningful queries" in order to facilitate the forthcoming query answering processes. In particular, the results of queries are used to: (i) help non-expert users in using the multi-database environment and (ii) improve performances of the multidatabase environment, which not only uses disk and memory resources, but heavily rely on network bandwidth.

NoXperanto employs a layer to keep track of the information produced by the crowd. This is modeled as a Property Graph and thus, it is persisted by a Graph Database Management System (GDBMS).

Outline. The remainder of the paper is organized as follows. While Section 3 introduces the concepts that we need throughout the paper, Section 2 discusses works that are related to our. Section 4 explains our approach in detail. Section 5 describes implementation issues. Section 6 concludes the paper with future perspectives of research.

RELATED WORKS

Most information systems are supported by distributed and heterogeneous data sources: multi-databases, data warehouses and Web portals. Such systems are, in fact, mediation infrastructures that emerged more than 20 years ago to enable transparent access to multiple data sources through querying, analysis, navigation and management facilities.

With the advent of NoSQL stores and polyglot persistence approaches, problems of data integration emerge with some specifities: the high heterogeneity of data models (e.g., NoSQL underlying data models are not standardized), the absence of semantic descriptions, the volume of data to integrate, just to name a few. Transformation and other wellknown techniques to bridge different databases seem hard to employ at large scale [START_REF] Virgilio | Converting relational to graph databases[END_REF]; they would bring data duplication that is unfeasible when the data size is huge. In order to deal with heterogeneity, the majority of information systems define an integrated schema. However, the integration process, generally controlled by the administrator of the system, is hardly suited for managing data in highly distributed and evolving environments such as the Web. Hardly coupled multi-sources storing huge datasets with semantic information (e.g. global schemas, mappings, rewritting rules) can be restrictive and expensive for applications that require simplicity, performance and large-scale dynamicity.

Advances in polyglot persistence querying are addressing the integration of heterogeneous data by providing pivot querying languages like UnQL that provide some operators for integrating graph, document, key value and relational data. There exists equivalent works which consider a unified language, proposing some SQL extension [START_REF] Marcus | Human-powered sorts and joins[END_REF][START_REF] Selke | Pushing the boundaries of crowd-enabled databases with query-driven schema expansion[END_REF][START_REF] Bozzon | Answering search queries with crowdsearcher[END_REF][START_REF] Demartini | Crowdq: Crowdsourced query understanding[END_REF][START_REF] Park | An overview of the deco system: data model and query language; query processing and optimization[END_REF], or consider a metamodel approache such as the Apache's MetaModel project 2 .

To overcome existing problems of data integration, we propose a solution to exploit a crowd of experts in a transparent way. Experts are all the users who are able to submit meaningful queries. We do not assume having a unified query surname : "Luo" Country : "China" name : "Orlando" surname : "Cassano" Country : "Belgium" name : "Antonio" surname : "Maccioni" Country : "Italy" name : "Genoveva" surname : "Vargas-Solar" Country : "Mexico" name : "Juan" surname : "Castrejòn" Country : "Mexico" language, but rather we follow the idea of the polyglot persistence movement to support multiple languages. The idea of using crowdsourcing for answering queries over a database has been covered in previous works [START_REF] Selke | Pushing the boundaries of crowd-enabled databases with query-driven schema expansion[END_REF][START_REF] Bozzon | Answering search queries with crowdsearcher[END_REF][START_REF] Wang | Crowder: crowdsourcing entity resolution[END_REF][START_REF] Demartini | Crowdq: Crowdsourced query understanding[END_REF][START_REF] Franklin | Crowddb: answering queries with crowdsourcing[END_REF][START_REF] Park | An overview of the deco system: data model and query language; query processing and optimization[END_REF][START_REF] Virgilio | Generation of reliable randomness via social phenomena[END_REF]. In particular, CrowdDB [START_REF] Franklin | Crowddb: answering queries with crowdsourcing[END_REF] integrates human inputs within a query plan that contains operations that usual database systems cannot always answer correctly (i.e. matching, ranking, etc.). RandomDB [START_REF] Virgilio | Generation of reliable randomness via social phenomena[END_REF] answers non deterministic queries using social network crowds with the aim to replace existing random number generators.

QUERYING A POLYGLOT MULTI-STORE

This section introduces basic concepts that are needed to introduce our approach in the next section.

Property Graph. Graph data models are able to generalize other data models:

• relational data: both schema and instance of relational data can be modeled with graphs [START_REF] Angles | Survey of graph database models[END_REF];

• XML data: XML document is modeled as a tree and a tree is an acyclic, undirected graph;

• document stores: each document consists of nested key-value pairs (therefore a tree), so a document store can be modeled as a set of trees;

• key-value stores: they corresponds to a set of nodes of the property graph.

NoXperanto does not generalize, nor integrates, other models; rather, it adopts a graph data model in order to link more easily the parts of the entities that are spread across different databases. In particular, we use the property graph model [START_REF] Rodriguez | Constructions from dots and lines[END_REF]. Briefly, a property graph is a multi-graph (a graph where two nodes can be connected by more than one edge) where every node and every edge has associated a set of properties. A property is a key-value pair, denoted in the format of < key, value >.

An instance of property graph is reported in Figure 1. This represents people (i.e. the nodes) and their relationships. For example the node representing a person whose name is Genoveva supervises the node representing the person whose name is Juan. In this case <name : Genoveva> is a property where name is the key and Genoveva is the value.

Though the property graph is directed, we simplify it using the undirected version. The property graph is the "defacto" standard model adopted by the GDBMSs (i.e. Neo4J, OrientDB, etc.). We will see in the Section 5 more details about it, since we make use of a GDBMS.

Running Example. To facilitate the understanding of the approach, let us consider the following running example. We have an infrastructure of databases, called movieBlog, behind a big blog website talking about movies. Information about entities such as the movies are splitted into different databases. The infrastructure consists in a multi-database, where we have a document store containing blog entries, a relational database storing information about actors, and a graph database keeping track of the movies' cast. Figure 2 depicts our scenario.

The definition of the databases of our running example are in Figure 3.

[DEFINITIONS] define "blogEntries" as document define "movies" as graph define "actors" as table

Figure 3: The database definition of the databases in Figure 2.

The example defines three databases of different kind: a relational database (i.e. table actors), a graph database (i.e. graph movies) and a document store (i.e. document blogEntries). The keys of these databases are the attributes Actor, id and id, respectively for the databases actors, movies and blogEntries.

Polyglot Environment. Databases contain entities (e.g., a tuple in a relational database or a document in a document store). Every entity can be referred with a key (e.g.,

[DEFINITIONS] define "comments" on "blogEntries.movie" = "movie.titles" as link a primary key in a relational database or a document id in a document store). Queries are expressions that aim at retrieving: (i) an entity, (ii) a part of an entity or (iii) a combination of entities. Without referring to a particular language or algebra, we can refer to these tasks with general operator of selection (σ), projection (π) and join (⊲⊳), respectively.

A σ query over a polyglot environment still involves separate answering processes, where database instances are independent from each other. In this case, the query can be dispatched to all the underlying databases, after an eventual syntactic translation of the query expression. A π is straightforward since it operates locally by extracting a sub-part of a result. While the semantics of σ and π in a polyglot environment are well-defined, the semantics of the ⊲⊳ needs to be clarified. In fact, if we join heterogeneous databases we can hardly rely upon a single algebra. We define such semantics as follows. Let us suppose to have two entities ei and ej belonging, respectively, to two heterogeneous databases. Among the others, the two entities have attributes ai and aj, respectively. Let us also suppose that there exists a comparing operator ✸. A join ei ⊲⊳e i .a i ✸e j .a j ej is the union between the information content of ei and the content of ej iff the predicate ei.ai✸ej.aj is satisfied.

Clearly, we can develop a join operator in a polyglot environment at a code-level exploiting existing join algorithms (e.g., nested-loop style join). In this context, such operations are very expensive as we cannot rely upon the optimizations of the DBMSs but we are compelled to load all the data in memory and, sometimes, to transfer them over a network.

Next section explains how NoXperanto is able to answer queries using a crowd of experts and, in particular, it will focus on how the join operators can be computed efficiently.

NOXPERANTO

This section explains our approach in detail. We first give an overview of the overall approach. Then, we conclude the section describing some use case in order to point out the advantages of the system.

Crowdsourcing Approach

In NoXperanto we aim at solving complex queries over a system containing several heterogeneus databases. To perform such queries we have to keep track of the relationships among entities stored in different databases. We employ two ways to indicate these relationships: one is explicit and the other is implicit.

Explicit Working Mode. In the explicit manner, the user can define how two classes of entities in different databases are related. For example, in Figure 4 we define that an entity of the database blogEntries is the same of an entity in the database movies if the value of blogEntries.movie is equal to the value of movies.titles. movies:"Keanu Reeves" actors:"Keanu Reeves" movies:"Carrie-Anne Moss" actors:"Carrie-Anne Moss" crowd link: "actors.Actor=movies.id" crowd link: "actors.Actor=movies.id" In this case we can exploit several techniques (i.e. ontology matching, schema matching, string matching, etc.) to find the instances of such definitions. They work at schema level and are very expensive to be performed at run-time. We can mitigate this complexity by using an hybrid approach between this explicit mode with the implicit mode that is explained next, but this lies outside the scope of this paper.

However, in many cases the administrator does not explicitly specify such definitions. It turns out that an automatic discovery of the relationships might be very useful. NoXperanto provides such a mechanism through the implicit modality.

Implicit Working Mode. The implicit working mode is driven by a crowdsourcing approach. Crowdsourcing is employed in different contexts to solve difficult problems and to build up knowledge bases relying on the effort of many people. Usually, a problem is split into many sub-problems that are solved through the so called microtasks. A microtask is a complicated task for a computer but it is easy for a person. The final problem is solved by considering all the microtasks that people of the crowd have processed. Often, these people are unaware of the problem or do not even know that they are processing a microtask.

The implicit working mode expects the system to be able to recognize the relationships. In this case, the system uses the knowledge of a crowd of experts, which appears when they submit complex queries. If those queries are also meaningful, in the sense that they produce a non empty set of results, we persist the relationships between entities of the two (or more) databases in our property graph layer.

More in detail, we extract the predicate of the join conditions from such queries to define a crowd link. For example, let us imagine an expert submitting σ id,N ationality (actors ⊲⊳ Actor=id movie). In a SQL-like language, the query will look like the following: SELECT id, Nationality FROM actors, movies WHERE actors.Actor = movies.id

The result of the query is {<Keanue Reeves, Canada>, <Carrie-Anne Moss, Canada>}, thus, it is a non empty result set and the query is meaningful. In the answering process we have identified some relationships between entities in movies and entities in actors. For each of them, NoXperanto persists a crowd link on the property graph layer as in Figure 5.

The Approach at Work

In this section we describe a sequence of four use cases to show the real benefits of a crowdsourcing approach in this context. The cases alternate queries from a non expert and expert users. For the sake of simplicity we consider a SQL-like syntax but of course, it is just the semantics of the id:"500bb. . . " title:"The Matrix" crowd link: "blogEntries.movie==movies.title" language and does not refer to any relational database. We refer the multi-database managed by NoXperanto with movieBlog. In this way, we query our datasets in a transparent way. The four cases are defined as follows:

• Use case 1 : a non-expert user asks for all information about "The Matrix". It is a simple keyword searchlike query (either submitted by a human being or by a programmatic access), so we cannot assume that the user is an expert.

SELECT * FROM movieBlog WHERE movieBlog.title == ''The Matrix''

The result of the query is {year=1999} since we have found an attribute title within the databases in movieBlog and an entity where the value of such attribute is "The Matrix".

• Use case 2 : a domain expert perform the following query:

SELECT * FROM movies JOIN blogEntries ON blogEntries.movie == movies.title

Note that the expert does not generally refer to movieBlog but to a precise database. The result of the query is: {year=1999, content="A computer hacker learns from mysterious rebels about the true nature...'' author="jccastrejon''} We can say that there is a relationship between blo-gEntries.movie and movies.title. Since a non-expert user could not write such a join with meaningful results, we determine that this user was an expert user. Consequently, she can be included within our crowd. In fact, the system stores a crowd link for each of the results as in Figure 6. We have bridged the document store with the graph databases at runtime.

• Use case 3 : a non-expert user submits the query of Use case 1, but in this case the result is different.

{year=1999, content="A computer hacker learns from mysterious rebels about the true nature...'' author="jccastrejon''}

We provided information to the user that we were not able to retrieve before. This additional information is provided by answering a join-free query. This is due to the information within the layer, which allows to bridge sharded parts of the same entity.

• Use case 4 : another expert user submits the query of Use case 2. The scenario is similar to use case 2, but the query answering is much more efficient. We do not have to perform an expensive join operation. We can directly exploit the presence of the crowd links to determine a pairs of entities to form the final results.

IMPLEMENTATION ISSUES

This section provides and overview of the implementation concerns that are required to develop the NoXperanto approach based on the requirements outlined in the previous sections.

Data Layer Issue. We manage the heterogeneity of multiple data stores by relying on a data layer based on the property graph data model (see Section 3). We implemented this layer on an emerging GDBMS, that is Neo4J3 . It provides a REST interface so that the interaction with the applications running in the polyglot environment is facilitated. Moreover, this interface would provide operations to manage data entities and links between them. For example, the specific syntactic sugar to specify when to consider the crowd links in the query answering.

Language Issue. Our approach does not consider a unified query language for polyglot persistence applications, but rather rely on the existing language support provided by scalable data stores. Thus, we propose to provide extensions for each of these languages, based on the general query semantics described in section 3. In particular, these extensions rely on the REST interface of the property graph model to manage the link and join operations described in section 4.

To implement these language extensions we intend to follow a model-driven approach, as proposed in our previous work 4 . In particular, the language definitions would be implemented using the Xtext framework [START_REF] Eysholdt | Xtext: implement your language faster than the quick and dirty way[END_REF], while the implementation of the link and join operations would be conducted with the Acceleo project5 , by relying on text templates that refer to the graph model REST interface. The native query mechanisms of each of the supported data stores would be used to retrieve the data in each of the systems.

Consistency Issue. Our approach assumes an eventual consistency model [START_REF] Pritchett | Base: An acid alternative[END_REF] in the persistence of the crowd links among the distributed entities. As a consequence, even when a link between data entities has been identified, users executing the same query may not always receive the same result. Nonetheless, each of the data stores in the environment has its consistency semantics.

To handle this heterogeneity in the consistency semantics we propose to extend our language support with operators to allow the user to specify the level of consistency that he expects from each of the supported data stores. We intend to implement this functionality based on the operators that few systems (e.g., Riak 6 , a key-value data store) already provide to trade availability for consistency on a per-request basis.

Crowd Management Issue. We have developed a small utility to manage the crowd of experts. This consists, basically, on a query parser and a small interface where the administrator can check the current state of the crowd links.

CONCLUSIONS AND PERSPECTIVES

In this paper we have presented NoXperanto, an approach to solve queries over an heterogeneus environment of databases using the knowledge of a crowd of experts. This knowledge is extracted from the results of the queries. In NoXperanto we avoid expensive pre-processing. As a result, we are able to scale with respect to the number of the databases within our environment.

Our future work will be devoted to finish the system, implementing an interface for setting up the multi-database environment and allowing the users to specify weather or not the system has to use the crowd links. The approach opens several research direction. In particular, we will investigate other scenarios where the results of a query can be exploited to facilitate forthcoming query answering.

Figure 1 :

 1 Figure 1: An example of property graph.

Figure 2 :

 2 Figure 2: The movie blog environment.

Figure 4 :

 4 Figure 4: The explicit definition of relationships.

Figure 5 :

 5 Figure 5: Crowd links explicitly produced.

Figure 6 :

 6 Figure 6: Crowd links produced in Use case 2.

The modality to fulfil a target by relying on the contributions coming from a large group of people.

http://www.neo4j.org/

https://github.com/jccastrejon/edbt-unql/

http://www.eclipse.org/acceleo/

Acknowledgments. The ideas within this paper were developed during the EDBT Summer School 2013 in Aussois (France). The authors of this paper are grateful to the EDBT association for the organization of the Summer School and to all the speakers for their helpful suggestions.


Marion Baranes
email: marion.baranes@viavoo.com

Benoît Sagot
email: benoit.sagot@inria.fr

A Language-Independent Approach to Extracting Derivational Relations from an Inflectional Lexicon

Keywords: Formal Analogy, Morphological Analysis, Derivational Relation

In this paper, we describe and evaluate an unsupervised method for acquiring pairs of lexical entries belonging to the same morphological family, i.e., derivationally related words, starting from a purely inflectional lexicon. Our approach relies on transformation rules that relate lexical entries with the one another, and which are automatically extracted from the inflected lexicon based on surface form analogies and on part-of-speech information. It is generic enough to be applied to any language with a mainly concatenative derivational morphology. Results were obtained and evaluated on English, French, German and Spanish. Precision results are satisfying, and our French results favorably compare with another resource, although its construction relied on manually developed lexicographic information whereas our approach only requires an inflectional lexicon.

Introduction

Derivational morphology can provide useful information for many natural language processing tasks. Indeed, it can improve any application which has to deal with unknown words in general and neologisms in particular, such as information extraction, spell-checking and others. For example, [START_REF] Bernhard | A Task-based Evaluation of French Morphological Resources and Tools[END_REF] have shown that it can improve question answering systems. [START_REF] Sagot | Extension dynamique de lexiques morphologiques pour le franc ¸ais à partir d'un flux textuel[END_REF] use derivational and compound analysis for morphological lexicon extension, in order to determine if an unknown word should be used to create a new lexical entry. Derivational morphology can also help extending lexical resources with syntactic (e.g., sub-categorisation frames) and semantic information (e.g., wordnets). One could for example infer sub-categorisation frames for nouns which are derived from known verbs for which sub-categorisation information is known. We define a morphological family as a set of semantically related lexical entries which differ by their prefix and/or suffix, thus limiting ourselves to concatenative derivational morphology. For example, the English words learn, unlearn or learner share a common lexical basis, and just differ with respect to derivational affixes. Therefore, they belong to the same morphological family. We shall denote as derivationally related two morphological lexical entries that belong to the same morphological family. Our system performs an analogy-based unsupervized extraction of weighted transformation rules that relate derivationally related lexical entries, and use these rules for extracting derivational relations within an existing inflectional lexicon. 1 Our transformation rules can also be used to infer morphological information (both inflectional and derivational) for wordforms unknown to the inflectional lexicon. 1 We define an inflectional lexicon as a set of entries of the form (citation form, part-of-speech, inflection class) together with a morphological grammar, which allows for generating (citation form, inflected form, part-of-speech, morphological tag) tuples.

Our system is language-independent, although restricted to concatenative derivational morphology. We have evaluated it on four languages, namely English, French, German and Spanish. After a brief overview of the related work in Section 2, we describe our system in Section 3. In Section 4, we introduce our experimental setup and the resulting derivational resources. Finally, we describe and discuss quantitative evaluation results (Section 5).

Related Work

Even though morphological analysis is the subject of numerous studies, it does not give rise to many lexical resources which contain derivational relations between lexical entries. Among the four languages at hand, although we can cite CELEX [START_REF] Burnage | Celex: A guide for users[END_REF] for English, German and Dutch, French seems to have received the most attention in that regard. Some resources try to join French verbs to their related nominals. For example, VerbAction [START_REF] Tanguy | Webaffix: un outil d'acquisition morphologique dérivationnelle à partir du Web[END_REF] pairs verbs with their derivationally related action nouns (accuser 'accuse' accusation 'accusation'), and VerbAgent [START_REF] Tribout | Constitution automatique d'une ressource morphologique : VerbAgent[END_REF] with derivationally related agent nouns (accuser 'accuse'accusateur 'accuser'). Others studies try to do the opposite and pair denominal nouns with their derivationally related verbs, such as Nomage [START_REF] Balvet | Nomage: an electronic lexicon of French deverbal nouns based on a semantically annotated corpus[END_REF] for French or NOMLEX [START_REF] Macleod | Nomlex: A lexicon of nominalizations[END_REF] for English. For French as well, DenALex [START_REF] Strnadová | Construction d'un lexique des adjectifs dénominaux[END_REF] pairs denominal adjectives with their nominal basis (atome 'atom'atomique 'atomic'), whereas the database MORDAN [START_REF] Koehl | Une base de données des noms désadjectivaux du franc ¸ais : le modèle mordan[END_REF] contains 3983 pairs of deadjectival nouns and their base adjective. We can also cite POLYMOTS [START_REF] Gala | A tool for linking stems and conceptual fragments to enhance word access[END_REF], a lexical resource that groups wordforms in morphological families and provides some information about their internal structure. However, the development of all these resources was based on manual work and/or on manually built lexical information (dictionary definitions, derivational morphological grammars, etc). Other studies propose less supervised systems for detecting morphological families or, more generally, for acquiring morphological information. [START_REF] Can | Unsupervised learning of morphology by using syntactic categories[END_REF] describe an usupervised approach based that relies, among others, on parts-ofspeech in order to produce a morphological analysis. [START_REF] Bernhard | Apprentissage non supervisé de familles morphologiques: Comparaison de méthodes et aspects multilingues[END_REF] describes two distinct unsupervised systems (MorphoClust and MorphoNet). The first one is based on hierarchical clustering methods, the second one uses a graph-based algorithm in order to group related wordforms of the same family in a lexical network. We can also cite [START_REF] Goldsmith | Unsupervised learning of the morphology of a natural language[END_REF], [START_REF] Kazakov | Unsupervised learning of word segmentation rules with genetic algorithms and inductive logic programming[END_REF], [START_REF] Neuvel | Unsupervised learning of morphology without morphemes[END_REF], [START_REF] Creutz | Inducing the morphological lexicon of a natural language from unannotated text[END_REF], [START_REF] Monson | Paramor: Minimally supervised induction of paradigm structure and morphological analysis[END_REF] or, in a more general context, works which participate to the Morpho Challenge 2 . In this paper, however, we focus on learning by analogy which is an approach used for morphological systems [START_REF] Lepage | Languages of analogical strings[END_REF][START_REF] Stroppa | An analogical learner for morphological analysis[END_REF][START_REF] Lavallée | Unsupervised morphological analysis by formal analogy[END_REF]. [START_REF] Hathout | Morphonette: a morphological network of French[END_REF] introduces Morphonette, a system restricted to French which uses morphological similarity, lexicographic definition-based semantic similarity and analogy. This system obtains results which are quite close to ours for French. This is why we choose to use it as a reference for our evaluation.

Our approach

Our computational system for derivational analysis is inspired by works based on formal analogy. Analogy aims at relating two pairs of terms: x is to y as z is to t, written x : y :: z : t. In order to match lexical entries which belong to the same morphological family, we look for affixation rules which are shared by both entries. Our system only requires an inflectional lexicon in order to function properly, i.e., an inventory of lexical entries, each associated with its list of inflected forms. For example, one can infer that the English adjective liable belongs to the same morphological family as liability if we find that: (1) liability is known, e.g., it is in the lexicon and (2) there is a rule which allows us to substitute the suffix -ability with -able. This analysis requires the acquisition of such rules, which we call transformation rules. 3 As we aim at relating lexical entries from an inflectional lexicon to the one another, we could try and extract these transformation rules directly on their citation forms. However, it is often the case that the inflected forms of a same lexical entry are based on more than one stem (e.g., in French, aller 'go', vais '(I) go/am going', irai '(I) will go'). Derivational processes do not necessarily use as their starting point the stem that underlies the citation form (e.g., the French noun ouverture 'opening' is related to the verb ouvrir 'open', but can be considered as based on the same stem as its past participle ouvert 'open').

2 http://research.ics.aalto.fi/events/ morphochallenge/ 3 These transformation rules need not be derivation rules. They only model transformations that relate two words belonging to the same morphological family, be them directly derivationaly related or not, and independently of the possible direction of such a derivational relation.

Therefore, we first extract transformation rules which relate inflected forms with citation forms within the lexicon, we then infer relations between inflected forms and lexical entries (through their citation forms), and finally replace in these relations inflected forms by their lexical entry, thus building a set relations between lexical entries. Let us first describe how we extract our transformation rules. We achieve this using a 4-step algorithm:

1. we extract a preliminary set of generic rules than can only be either purely prefixal or purely suffixal;

2. we generate a first set of (inflected form, citation form) pairs based on these generic rules;

3. we extract from these pairs a new set of rules, which can be prefixal and/or suffixal rules and that include POS information;

4. we extract (inflected form, citation form) pairs based on this final set of rules, and then merge these (inflected form, citation form) pairs into pairs relating lexical entries.

We shall now describe these 4 steps in more detail.

Extracting the preliminary set of rules

The aim of this step is to learn prefixes and suffixes particular to the language concerned. In other words, we extract preliminary transformation rules that are either prefixal or suffixal, not both. To do that, we proceed in two stages:

1. The extraction of prefixal rules: in order to extract these rules, we pair all inflected forms with all citation forms of our lexicon. For each possible pair of the form (inflected form, citation form), we compare their structure. If these two forms differ only by their prefixes and share a significant common part (at least 3 characters),4 we create a rule that relates the prefix of the inflected form to that of the citation form. These rules contain the input and output prefix as well as a short context (the first common letter, which immediately follows both prefixes). For example, given the English (inflected form, citation form) pair subtitle-title, the extracted rule will be {sub → }{t} (i.e., before a t, replace sub by the empty string, represented by the symbol ' ').

2. The extraction of suffixal rules: this extraction is the mirror image of the extraction of prefixal rules. We extract all (inflected form, citation form) pairs that differ only by their suffixes and share a common part. Whatever the language processed, this common part have to be at least 6 characters 5 . Reducing this threshold increases significantly the run time (the threshold 5 is three times slowlier than the threshold 6) and, at same time, the many additional prefixal rules, which could be obtained in this way, are virtually never correct. Given such a pair, we extract a suffixal rule in the same way as we do for prefixal rules. For example, given the English (inflected form, citation form) pair laughs-laughing, the extracted rule will be {h}{s → ing}.

In the process, we count the number of times each such rule is extracted. Each rule is stored together with its number of occurrences.

Generating the preliminary set of (inflected form, citation form) pairs

We use the preliminary transformation rules extracted as described in the previous section for relating inflected forms with citation forms. To do that, for each inflected form in our lexicon we try and apply all applicable prefixal rules (i.e., rules such that the inflected form starts with the input prefix followed the one-character context specified in the rule). We also try and apply to the input inflected form all applicable suffixal rules. We finally try and apply to the input inflected form all pairs of applicable rules, one prefixal and one suffixal. Each time the result is a citation form known to the lexicon, we store the pair (original inflected form, resulting citation form). These pairs constitute a preliminary derivational lexicon, which relates inflected forms to citation forms, including cases where both the prefix and the suffix are changed during the transformation. For example, if we have the Spanish inflected form abono 'subscription', we will join it, among other things, to the citation form desabono 'cancellation of subscription' with the prefixal rule { →des}, to the citation form abonar 'to subscribe' with the suffixal rule {o→ar} and to the citation form desabonar 'cancel a subscription' with this two latters affixal rules.

Transformation rules extraction

Based on the preliminary derivational lexicon, generated as described in the previous section, we extract a new set of transformation rules, which can now be simultaneously prefixal and suffixal. We extract from each pair (x, y) in our preliminary derivational lexicon the prefixal and/or suffixal transformation rules which transforms x into y.

We also consider as part of the rule several additional pieces of information:

• First, depending on whether the citation form of the inflected form x is the same as (the citation form) y or not, we mark the rule as inflectional or as derivational.

Rules extracted from the English pairs mediatisationsmediatisation or upgraded-upgrade, for example, will be labelled as inflectional, wheareas rules extracted from English pairs such as accused-unaccusable or communication-communicate will be labelled as derivational.

• Second, as our lexicon provides us with the part-ofspeech and the morphological features (e.g., gender, number) for the inflected form x, as well as the partof-speech and inflection class for the citation form y, we incorporate this information within our rules.

• Third, we store for each rule the number of distinct (inflected form, citation form) pairs in the preliminary derivational lexicon from which it was extracted; this figure will be considered as the number of occurrences of the rule.

As a result, these rules can be writen as follows:

(prefix, suffix, POS, morph. feat.)

infl./der.

-----→ (prefix', suffix', POS', infl. class.')

In order to minimize the noise in the extracted rules, we discard all rules which appear less than 80 times -an empirically-chosen value that we shall discuss in Section 5.1.. A few examples from our French, English, German and Spanish data are shown in table 2.

Derivational relations extraction

Once this final set of rules is extracted, we can relate morphological entries from our inflectional lexicon with the one another. As in section 3.2. above, but using the final set of transformation rules, we relate pairs of the form (x, y), where x is an inflected form (with its part-of-speech and morphological tag) and y is a lexical entry (citation form, part-of-speech, inflection class), provided the rule transforms x into y, while respecting part-of-speech and morphological information at both ends. Next, we replace x by its lexical entry, thus creating pairs of lexical entries (hopefully) belonging to the same morphological family.

Experimental setup and results

We have implemented the language-independent algorithm described in the previous section and have applied it to inflectional lexicons for English, German, Spanish and French. More precisely, we have used the large-scale inflectional lexicons developed for these languages within the Alexina framework [START_REF] Sagot | The Lefff , a freely available and large-coverage morphological and syntactic lexicon for French[END_REF], namely EnLex for English, DeLex for German [START_REF] Sagot | DeLex, a freely-avaible, largescale and linguistically grounded morphological lexicon for German[END_REF], the Leffe for Spanish [START_REF] Molinero | A morphological and syntactic wide-coverage lexicon for Spanish: The Leffe[END_REF] and the Lefff for French [START_REF] Sagot | The Lefff , a freely available and large-coverage morphological and syntactic lexicon for French[END_REF]. We only retained nominal, verbal, adjectival and adverbial entries. The size of the resultig lexicons, more precisely their number of inflected forms and lexical entries, are shown in the Table 3. We define the part-of-speech pattern of a relation between two lexical entries as the pair consisting of the part-ofspeech of its input entry and the one of its output entry. The non-homogeneous distribution of our part-of-speech patterns for the four languages at hand can be explained at least in part by the fact that each lexicon displays a different distribution of parts-of-speech accross lexical entriesthis is at least in part a property of the respective languages involved, but is also certainly influenced by the properties of each lexicons. For example, in English, the most frequent parts-of-speech are nouns and adjectives. It is therefore no surprise that part-if-speech patterns involving these categories cover as much as 66% of all patterns.

French and Spanish lexicons display similar distributions of parts-of-speech accross lexical entry, which results in the fact that their part-of-speech patterns are similarly frequent.

As far as German is concerned, the massive amount of v → adj patterns is a consequence of the fact that our German lexicon, DeLex, (temporarily) models present participle as adjectival lexical entries6 and not, as one could expect, as inflected form of the corresponding verbal lemma. As a result, our algorithm creates a large amount of pairs relating verbal lexical entries with the adjectival entries that covers their present participle forms.

Evaluation

We performed two kinds of evaluation. First, we evaluated our results on all 4 languages at hand by manually assessing the quality of the extracted pairs of lexical entries. Second, we evaluated our French results againt the morphological resource Morphonette [START_REF] Hathout | Morphonette: a morphological network of French[END_REF], in order to assess the recall of our system, the overlap between both resources and the precision of pairs found respectively in our data only, in Morphonette only or in both resources.

Manual evaluation of the precision

In order to evaluate the precision of our pairs of lexical entries, we extracted for each language 100 randomly selected such pairs. We have manually associated each of them with one of the following tags:

CORR: Both lexical entries belong to the same morphological family (e.g., English preconfiguringconfigured); The results of this evaluation are shown in Table 6. One can notice that error rates for English, French and German are rather low (between 1% and 2% -although such figures are to be taken with care given the low amount of pairs evaluated), whereas the error rate for Spanish is higher. This is caused by a noisy rule which creates derivationnal links between words which are distinguished by the suffixes {ear#} and {ar#}. This rule creates wrong derivationnal pairs such as zapar 'sap, mine'zapear 'shoo (a cat)' or copear 'drink (familiar)'copar 'corner (the market)', and is the cause of 9 our the 13 pairs tagged as ERR. 7 .

POS PATTERN ENGLISH GERMAN SPANISH FRENCH EXAMPLE adj → adj 17% 4% 0.4% 1% adaptable → adaptative adj → n 16% 11% 13% 6% random → randomization n → adj 15% 3% 10% 8% compression → compressible n → n 18% 1% 32% 32% self-destruction → self-destructive n → v 5% 2% 10% 17% abandonment → to abandon v → adj 7% 52% 6% 5% to sanction → unsanctioned v → n 8% 21% 17% 20% to tabulate → tabulation v → v 4% 7% 5% 4% labeled → mislabel
Results of this evaluation espacially depend on the quality of the rules used to create our pairs of lexical entries. As mentioned in Section 3.3., we chose to retain only rules 7 Our Spanish result could be easily improved by deleting this noisy rule.

with a frequency at least 80. This choice of this threshold is the result of a two-step analysis, which we shall now sketch.

First, we performed an qualitative analysis of our rules according to their frequency. Our goal here is to determine from which threshold our rules become reliable. To do that, we have randomly extracted 50 rules at each frequency level between 10 and 80 that is a multiple of 10. In other words, we have evaluated 50 rules with a frequency of 10, 50 rules with a frequency of 20, and so on up to 80. For each such set of rules, we evaluated whether at least one pair of lexical entries belonging to the same morphological familly could be built and would be related by the rule at hand. Results for French are given in Figure 1. It shows that a sufficient level of precision can not be expected with a threshold of approximatively 50 or below. Second, as a result of this first step, we evaluated our system on French taking into account all rules with a frequency of 50 or higher (rather than 80 or higher). This allowed us to obtain a new set of 156,064 derivational pairs (vs. 84,927 with a threshold of 80). We have evaluated a set of 100 randomly selected derivational pairs. Out of these 100 pairs, we tagged 74 as CORR (correct), 1 as DIACHR, 15 as INFLEX and 10 tagged as ERR. In other words, 26 out of 100 pairs are incorrect in some way. The set of underlying transformation rules is therefore much less reliable than with a threshold of 80.

Comparative evaluation of our French results

with another resource Next, we compared our French lexical entry pairs to the resource Morphonette [START_REF] Hathout | Morphonette: a morphological network of French[END_REF] which was also built based on analogy, but leveraging previous manual lexicographic work. For comparison purposes, we ignore inflectional class information of our results, as they are not available in Morphonette, and only retain the partof-speech of each entry. Moreover, we remove from Morphonette all inflectional relations and all relations involving neoclassical compounds (e.g., psychopathe -'psychopath'), as our approach only targets formally regular derivational phenomena. This results in 76,754 pairs (out of 96,081 initially). This being done, both datasets have 22,591 pairs in common, 62,336 pairs are created only by our system, whereas 54,163 pairs are only found in Morphonette. To compare our respective datasets, we randomly extracted and manually evaluated 200 pairs of related lexical entries for each of these three subsets. Results are presented in Table 7.

SYSTEM CORRECT OTHER

Pairs found both in Morphonette and in our system 97.5% 2.5% Morphonette only 96.5% 3.5% Our system only 94% 6%

Table 7: Accuracy of our system with respect to Morphonette

Our system and Morphonette share about one third of their results in common, which is not much: The recall of both approaches is still relatively low. If we consider the union of both datasets as the reference, which is obviously optimisic, one can compute recall figures for both datasets: we would then reach a recall of 61%, whereas Morphonette would have a recall of 55%.

Our precision rates are almost as high as those of Morphonette, which is very satisfactory for at least two reasons. First, our system has produced more pairs of lexical entries. Second, it is important to recall that Morphonette does rely on a massive amount of manually built lexicographic information, as it takes advantage of the electronic version of the large-scale dictionary Trésor de la Langue Franc ¸aise, by exploiting the lexicographic definitions it contains. Our system manages to reach accuracy levels which are almost as high as Morphonette's without exploiting any such costly information.

As a result, our system is languageindependent -provided derivational morphology can be considered concatenative -, and we applied it indeed to four different languages, whereas developing an version of Morphonette for another language would require the use of a large-scale electronic dictionary for that language.

Conclusion

In this paper, we introduced an unsupervised languageindependent system which automatically extracts transformation rules and derivationally related pairs of lexical entries from an inflectional lexicon, without the need for any manual supervision. We tested and evaluated it for precision on four languages, namely English, French, German and Spanish. In addition, we performed a comparative evaluation of our French results with the morphological resource Morphonette. Despite the fact that the construction of Morphonette was based on the exploitation of manually built lexicographic definitions, we reach almost the same level of precision and a slightly higher recall with our purely unsupervized approach. In the future, we would like to integrate our results for providing our inflectional lexicons with a derivational layer, e.g., in the form of information about the morphological family of each entry.

Figure 1 :

 1 Figure 1: Evaluation of transformation rules according to their occurrence number

Table 1 :

 1 Example of preliminary pairs extracted from our English lexicon

	PAIRS	PREFIX	SUFFIX
	appreciable → depreciate	{ap → de}{p} {i}{able → ate}
	appreciable → precis	{ap → }{p}	{able → s}
	appreciable → appreciably		{e → y}
	appreciablest → appreciable		{est → e}
	demoded → modest	{de → }	{ed → est}
	demoded → modish	{de → }	{ed → ish}

Two such pairs, say (x, y) and (z, t), are in an analogical relation, x : y :: z : t if they have been obtained using the same transformation rule(s). At this stage, our set of derivational relations is still noisy as shown in the table 1.

Table 2

 2

	contains a few examples of pairs extracted with our
	transformation rules.
	Note that a morphological lexicon does not distinguish
	between the different senses of polysemous words that
	behave in the exact same manner at the morphological
	level. Therefore, it might be the case that we relate two
	morphological entries eventhough this relationship only
	applies to specific senses of both morphological entries
	involved. This is because morphological families are not
	defined only in morphological terms, but also involve
	semantic affinities.

Table 3 :

 3 Number of the entries in the input inflectional lexiconsTable4shows the number of rules and pairs obtained for each language. It provides the number of transformation rules we extracted as explained in Section 3.3., the number of pairs of related lexical entries we created with these rules, and the ratio of the number of created pairs with respect to the number of all possible pairs in each lexicon (i.e., the number of lexical entries times this number minus 1).

	LANGUAGE	TRANF. PAIRS OF EXTRACTED PAIRS
		RULES	LEXICAL	/ POSSIBLE PAIRS
			ENTRIES
	English	11,748	597,148	0.015 ‰
	German	6,812	10,639	0.017 ‰
	Spanish	6,000	69,694	0.005 ‰
	French	8,834	84,927	0.003 ‰

Table 4 :

 4

Number of transformation rules relating an inflected for to a lexical entries, together with the number of pairs of lexical entries extracted for each language based on these rules. See text for details.

Table 5

 5 illustrates, for each language, the most common part-of-speech patterns in the derivational lexicons we have acquired. Percentages in this table indicate the share of relations that follow the corresponding part-of-speech pattern. For instance, 18% of the English derivational pairs we have acquired relate two nouns with one another.

Table 5 :

 5 Most frequent POS-based patterns for each language.

	UNUSUAL: The derivational relation between both lexical
	entries is correct, but only applies to senses that
	are rare for at least one of the lexical entries at
	hand (e.g., French tentement '(fencing) striking the
	adversary's sword twice with one's own' -tenter
	'(fencing) perform a tentement', whereas the most
	common sense is 'try');
	DIACHR: Both lexical entries share indeed a common
	etymology, but cannot be synchronically considered
	as belonging to the same family (e.g., French mariner
	'stew' -marin 'sailor').
	INFLEX: Both lexical entries belong clearly to the same
	morphological family but they are linked by an
	inflexional relation and not a derivational relation
	(e.g., English congratulation -congratulations);
	ERR: The two lexical entries do not belong to the same
	morphological family (e.g., French graver 'engrave'
	grave 'serious');
	LANG.	CORR	UNUSUAL	DIACHR	INFLEX	ERR
	English	98	1	0	0	1
	German	98	0	1	0	1
	Spanish	73	8	2	4	13
	French	89	2	3	4	2

Table 6 :

 6 Evaluation results for pairs of lexical entries

This threshold was set emprically because of running time issues when using lower values.

Afterwards, in order to choose this threshold according to a language, a non-supervised method will have to be implement. Indeed, we realised that the number of prefixal rules, which has been extracted with this threshold, ranges from less than 100,000 (with the English) to more than

millions (with the French).

DeLex is still under development. Future versions will integrate present participle forms as part of the verbal paradigms.

Acknowledgements

This work was partly funded by the French ANR national grant EDyLex (ANR-09-CORD-008).


Jun Zhou
email: junzhou@recherche.enac.fr

Sonia Cafieri
email: sonia.cafieri@enac.fr

Daniel Delahaye
email: daniel.delahaye@enac.fr

Mohammed Sbihi
email: mohammed.sbihi@enac.fr

Optimization of Arrival and Departure Routes in Terminal Maneuvering Area

Keywords: TMA, SID, STAR, Optimization, Fast Marching Method, Simulated Annealing I

Airport is both the starting and ending point of air traffic. The sharp increase in air traffic flow causes directly traffic congestion in Terminal Maneuvering Area (TMA) which affects the normal operation of the flights. Optimizing departure and arrival procedures is therefore crucial to regulate air traffic flow. This research focuses on generating 3D Standard Instrument Departure routes and Standard Terminal Arrival Routes in TMA at a strategic level. We propose an optimization approach to generate 3D routes avoiding obstacles and assuring a minimum separation between routes. The method combines Fast Marching Method and Simulated Annealing.

INTRODUCTION

Nowadays air transport in Europe and North America has basically reached saturation. The sharp increase in air traffic flow causes directly traffic congestion in Terminal Maneuvering Area (TMA), which affects the normal operation of the flights. TMA is designed to handle aircraft arriving to and departing from airports and perhaps is one of the most complex types of airspace.

Currently, the Standard Instrument Departure (SID) and Standard Terminal Arrival Route (STAR) are designed manually based on the airport layout, existing Navaid infrastructures and nearby constraints [START_REF] Pfeil | Optimization of airport terminal-area air traffic operations under uncertain weather conditions[END_REF]. Therefore automatically designing departure and arrival routes at a strategic level in 3D is interesting as it may help to regulate air traffic flow.

Planning optimal aircraft routes is a rich and dynamic research area in Air Traffic Management (ATM). Routes design in TMA is however a specific problem for which to our knowledge there is not a rich literature. In [START_REF] Pfeil | Optimization of airport terminal-area air traffic operations under uncertain weather conditions[END_REF] and [START_REF] Visser | Optimization of noise abatement arrival trajectories[END_REF], two problems closed to the one considered in the present paper are studied. In [START_REF] Pfeil | Optimization of airport terminal-area air traffic operations under uncertain weather conditions[END_REF], for a given weather forecast, the author develops an integer programming approach to optimally choose terminal area arrival and departure fixes as well as sector boundaries. In [START_REF] Visser | Optimization of noise abatement arrival trajectories[END_REF], an optimization algorithm is proposed for aircraft routings that minimizes the noise impact in the residential communities surrounding the airport. The aim of this study is to give an optimization approach to automatically design 3D departure and arrival routes at a strategic level taking into account some operational constraints.

This paper is organized as follows: Section II describes the problem and introduces the TMA model; Section III presents the proposed approach to solve the problem. Section IV gives some preliminary simulation results. Finally, Section V gives conclusions and future directions.

II. PROBLEM DESCRIPTION AND MODELIZATION

A. Problem Description

TMA is a designated area of controlled airspace surrounding one or several airports. It is designed to handle aircraft arriving to and departing from airports. It is one of the most complex types of airspace.

The SID is a flight route followed by aircraft after takeoff from an airport. The STAR is a route which connects the last enroute way-point to the Initial Approach Fix. These routes are specified by a sequence of waypoints. Each aircraft flying under Instrument Flight Rules (IFR) through the TMA must follow a SID when departing an airport, and a STAR when arriving. The design of SIDs and STARs has to take into account operational and environmental constraints, such as vertical and horizontal flow separation, noise restrictions, etc.

In the following, we propose a method to design automatically the SIDs and STARs for a given TMA configuration, characterized by a number of entry/exit points at the boundary of TMA, arrival/departure points around the runways, forbidden areas and some operational constraints.

B. Modelization

In this study, we only consider TMA surrounding one airport. The number and configuration of runways are known. We suppose that the runways have the sufficient distances and equipments for landing and taking off for all types of aircraft. Let be the total amount of flights arriving at and departing from the airport. As TMA is generally designed in a circular configuration centered on the geographic coordinates of the airport, we assume it is composed of two concentric circles 1 and 2 , with radius R1 and R2 respectively. Aircraft enter into or exit from TMA on several points located on 1 . More precisely, let = � 1 , … , , +1 , … , + � be the set of entry and exit points, where the first points are the entry points and the remaining ones are exit points.

Similarly, aircraft arrive to or departure from airport through several points located on 2 . Suppose that = � 1 , … , , +1 , … , + � is the set of arrival and departure points, where the first points are the arrival points and the remaining ones are departure points. An example of TMA is shown in Fig. 1

with = { 1 , 2 , 3 , 4 } and = { 1 , 2 }.
The routes that we want to design connect some points on C1 to some other points on C2. Let ⊂ × be the subset which contains the pairs of points to be connected on C1 and C2. Furthermore, we suppose that the proportion of flights on each route is given.

The design of SIDs and STARs can be done in an optimal way, with respect to a given criterion, such as minimizing the total distance flown by all flights. Therefore, the problem can be expressed as an optimization problem. In the following, we give the main elements of our optimization model. Given (, ) ∈ , a route connecting points and can be defined as a function:

: [0; 1] → ℝ 3 (1)
where (0) represents the starting point and (1) is the ending point. There are two possible cases: route either starts from an entry point on C1 and ends at an arrival point on C2; or it starts from a departing point on C2 and ends at an exit point on C1. This can be expressed by the following equations:

(0) = (1) = � if 1 ≤ ≤ 1 ≤ ≤ (2) (0) = (1) = � if + 1 ≤ ≤ + and + 1 ≤ ≤ + . (3)
We denote the components of in axis (, , ) by ( , , ) respectively.

In this study, we consider two main constraints: the forbidden areas and the minimum separation. In TMA some special areas exist, where an aircraft is not allowed to fly, for instance geographical obstacles, big cities, military areas, etc. We refer to these areas as "forbidden areas". Furthermore, in air traffic control, aircraft have to be maintained at a minimum separation distance to reduce the risk of collision. The minimum vertical separation is 1000ft in TMA for all aircraft. Generally, the minimum horizontal separation in TMA is equal to 3NM. We consider this separation equal to 6NM, in order to take into account the deviation of aircraft from the pre-designed route. The aircraft protection zone is shown in Fig. 2.

The separation constraints are expressed as follows, ∀(, ), (,

) ∈ , ∀( 1 , 2 ) ∈ [0; 1] ICRAT 2014
� � ( 1 ) -( 2 )� 2 + � ( 1 ) -( 2 )� 2 ≥ 6 (4) � ( 1 ) -( 2 )� ≥ 1000 . ( 5
)
We minimize the total distance flown by all the flights during a certain period.

= ∑ (,)∈ (6)
where is the length of route and is the proportion of flights on route .

III. SOLUTION APPROACHES

To deal with the difficulty of the problem, we propose a three-steps solution approach.

a. Compute an individual route by Fast Marching Method (FMM) and Gradient Descent method, where we take into consideration the forbidden areas.

b. Given a fixed order of the routes, compute sequentially the routes taking into account the minimum separation constraints.

c. Find an order minimizing (6) by applying Simulated Annealing (SA).

A. Designing one route

Given (, ) ∈ , we first compute a route yielding the minimal travel time from (0) to (1), see ( 2) and (3). The minimal-time optimal trajectory problem corresponds to a wave front propagation problem [START_REF] Girardet | Generating optimal aircraft trajectories with respect to weather conditions[END_REF], [START_REF] Bertsekas | Dynamic programming and optimal control[END_REF]. In the isotropic case where the wave propagation speed does not depend on the direction, the equation that describes the evolution of the front is in the following form, known as the Eikonal equation:

‖∇()‖() = 1 (7)
supplemented by the boundary condition

� (0)� = 0 (8)
where is the front position (corresponding to the aircraft position); () represents the time at which the front reaches the point and () is the speed at the point . In order to take into account the constraints, we associate a different propagation speed to points belonging to forbidden areas and to points located elsewhere, by expressing the speed at point as follows:

() = �1 -()� • (9)
with () ∈ [0 ; 1) and a constant value. In strictly forbidden area we consider () = 0.99 and elsewhere () = 0.

To solve the wave front propagation problem in the isotropic case, we apply the FMM developed by Sethian in [START_REF] Sethian | Fast Marching Methods[END_REF]. The general idea of FMM is that the front propagates towards the points that it reaches at a minimum time. At the end of the evolution, we get the minimum time to reach any point in space starting from (0) . Then the Gradient Descent method is used to generate the route. It starts from the ending point (1) and moves towards the starting point (0) by taking steps proportional to the opposite of the gradient of () at the current point .

B. Generating all routes

Given an order of the routes, we compute sequentially routes as explained in the first step. In order to satisfy the minimum separation constraints, once a route is computed, this route and its protection zone are considered as additional forbidden area constraints for the remaining routes.

C. Getting an optimal order

By changing the order of routes, the length of each route is modified, because the routes computed previously have an influence on the shapes of the following routes. The number of possible choices for route order is !, where = (), that can be rapidly increase with . To get an optimal order, we apply a Simulated Annealing that is a stochastic global optimization method. It is conveniently applied to large scale problems.

Simulated Annealing works by emulating the physical process whereby a solid is slowly cooled so that when eventually its structure is "frozen", a minimum energy configuration is obtained. For our application, the state space is the permutation group of the routes and a solution is an element of this group, representing a selected order of routes. The algorithm starts with a random solution, then at each iteration a new solution is generated by selecting randomly two positions in the previous solution and inversing the order of the sub sequencing between them.

ICRAT 2014 IV. SIMULATION RESULTS

In this section we present the results obtained at each step A, B, C in Section III.

We work with an airport with two parallel runways and . Their orientations are (12, 30) and (12, 30) respectively. The orientation 12 of runway and the orientation 12 of runway are only used for takeoff; the other two sides are only used for landing. The coordinate of the center of the two circles 1 and 2 is (100 , 100, 0 ). Fig. 3 shows this configuration.

Moreover, 1 = 100 and 2 = 10 ; Entry/exit points are { 1 , 2 , 3 , 4 } and { 5 , 6 , 7 , 8 } respectively. Arrival/departure points are { 1 , 2 } and { 3 , 4 } respectively.

The z-coordinates of points , ∈ {1, … ,8} and , ∈ {1, … ,4} are 25000 and 4000 respectively. Their

x,y-coordinates are presented in Table.

The proportion of flight on each route is 5%, 20%, 15%, 10%, 5%, 15%, 25% and 5% respectively.

A. Designing one route

In this step, we firstly generate a route connecting the pair ( 1 , 1 ). Fig. 4 presents the simulation results. Three obstacles are taken into consideration. The area located in the center of an obstacle in dark gray is the surrounding area that can be flown over considering a penalty. The simulation result shows that the generated route is smooth and avoids the forbidden area.

B. Generating all routes

The simulation result is shown in Fig. 5 where the black routes are the STARs and the gray ones are the SIDs. The obstacles are unchanged.

C. Getting an optimal order

The simulation starts from a randomly generated order, with the initial total distance = 2204141 . By applying Simulated Annealing, we find the minimum total distance = 2008012 . The relative reduction ∆= ( -) ⁄ is equal to 9.7%.

V. CONCLUSION AND PERSPECTIVES

In this paper, we introduce a methodology to generate automatically SIDs and STARs in TMA at a strategic level, ICRAT 2014 considering forbidden areas and minimum separation constraints.

In future work, in order to get closer to the operational context, we plan to consider some other constraints in TMA, for instance the route curvature, noise restrictions, runway capacities, etc. To deal with the more complex problem, the study will focus on mathematical modelization aspects as well as on the development of efficient determinist and stochastic optimization methods. Furthermore, we will address route design at tactical level taking into account weather events. Some routes can be blocked and have to be dynamically redesigned in order to address efficiently the demand.

Figure 1 .Figure 2 :

 12 Figure 1. Example of TMA

1 .

 1 The number of flight is = 20000; The pairs to be connected are = {( 1

Figure 3 :

 3 Figure 3: Runway configuration

Figure 4 :Figure 5 :

 45 Figure 4: Designing one route (the axes x, y, z have different scales; the range of axes x and y is [0; 225km], the one of axis z is [0; 8.5km])

TABLE I .

 I COORDINATES IN AXIS x AND y

	x (km)	100	200	120	0	140	180	40	20
	y (km)	200	100	2	100	194	40	20	160
		x (km)	110	100	100	90
		y (km)	100	90	110	100

ACKNOWLEDGMENT This work has been partially supported by Civil Aviation University of China, by National Natural Science Foundation of China (NNSFC) through grant NNSFC 61201085 and by French National Research Agency (ANR) through grant ANR 12-JS02-009-01 "ATOMIC".