Julie Dumas
email: julie.dumas@cea.fr

Henri-Pierre Charles

Kévin Mambu

Maha Kooli

Dynamic Compilation for Transprecision Applications on Heterogeneous Platform

Keywords: transprecision, dynamic compilation, heterogeneous, just in time, code specialization 16

This article describes a software environment called HybroGen , which helps to experi-1 ment binary code generation at run-time. As computing architectures are getting more complex, 2 the application performances become data-dependent. The proposed experimental platform is 3 helpful in programming applications that can be reconfigured at run-time in order adapted for a 4 new data environment. HybroGen platform is adapted to heterogeneous architectures and can 5 generate instructions for different target. This platform allows to go farther than classical JIT 6 compilation in many directions: the code generator is smaller by three orders of magnitude, faster 7 by three orders of magnitude compared to JIT (Just-In-Time) platforms and allows making code 8 transformation that is impossible in traditional compilation scheme like code generation for non 9 Von Neumann accelerators or dynamic code transformations for transprecision. The latter will 10 be illustrated in a code example: the square root with Newton's algorithm. We also illustre the 11 proposed HybroGen platform with two others examples: a multiplication with a specialization on 12 a value determine at run-time and a convertion of degree Celcius to degree Fahrenheit. This article 13 presents a proof of concept of the proposed HybroGen platform in terms of its functionalities, and 14 demonstrate the working status.

Introduction 17

Compilation and code generation1 are 50 years old research domains, parallel to 18 the computer architecture research domain [START_REF] Patterson | Years of computer architecture: From the mainframe CPU to the domain-specific tpu and the open RISC-V instruction set[END_REF]. Compilers have the difficult task to 19 transform a source code application into a running binary code.

20

Due to the constant evolution of both application domains and computing systems, 21 this task becomes more and more complex. The difficulty comes from the fact that those 22 evolution goes in the opposite direction.

23

From the classical application development point of view, the priority is to make 24 programmers efficient by providing richer programming environments. As an illustra-25 tion the Java SDK environment contained around 100 classes in the 1.0 release (1995) 26 and 13,367 for the 1.5 (J2SE 5.0 2004) release (by counting the .class objects). These two 27 orders of magnitude in complexity gives a very rich programming environment which 28 makes programmers very efficient because of the "job oriented API" (JDBC for database 29 applications, Graphic for gaming, etc).

30

This organization improves programmer efficiency but augments the "distance" 31 between the computing architecture and the problem to solve: the programmer generally 32 focuses on problem-solving by using complex APIs based on high level layers, which 33 augments differences between the data to compute on, and the hardware capabilities.

34

A first solution to this problem was to delay the code generation at run-time by using 35 JIT (Just-In-Time) compilation in Java. The hotspot compiler [START_REF] Paleczny | The java hotspot TM server compiler[END_REF] is efficient, compiles on demand but is based on method count, not on hardware counter, nor on data set characteristics. JIT compilation needs a huge memory footprint and needs a long latency to react to new application behavior.

In another domain, scientific computation applications, the programmer is aware of the underlying hardware, takes care of the performance by using efficient compilers and uses algorithms where the data accuracy is computed at the application level. To illustrate this, many examples are available in the classical book "Numerical Recipes" [START_REF] Press | Numerical recipes: the art of scientific computing[END_REF].

A typical example is the conjugate gradient algorithm where the iteration number relies on a residue value. This value decreases during the computation and controls the end of the program.

In this domain it could be interesting to do the computation with a reduced precision, which allows computing faster because by reducing the memory bandwidth pressure, and switching to an improved precision at the end. This simple scheme is very complex to setup practically.

In this article we present a new compilation infrastructure proof of concept that allows solving the two identified difficulties that classical compilation chain does not solve:

•

Make applications aware of the data-set characteristics and allow to take advantage of this knowledge to optimize code.

• Render possible dynamic transprecision, i.e. allow transforming the binary code at run time to change the data types during the application run.

We presents our compilation flow and the different steps. We also show three demonstrations examples to demonstrate the capabilities of our tool: a conversion of degree Celcius to degree Fahrenheit, a multiplication with a specialization on a data fixed at run-time and finally the computation of the square root with Newton's algorithms.

The article is composed of a section 2 where we introduce some other compilation approaches. The, section 3 presents the compilation objectives ans explains as well as the targeted compilation scenarios. Section 4 illustrates how the compilation chain works on small tutorial examples. Section 5 discusses the future evolution of this compilation infrastructure. Finally, section 6 concludes this paper.

Related Works

Many compiler works can be cited about compilation, but there are not so many works related to delayed code generation or at least a compilation scenario which allows taking optimization decision at a different time than the static compilation.

Code Specialization

All standard C compilers are able to do partial evaluation and, for example, able to replace expression containing constants by a resulting value.

The initial idea to do run-time code specialization (i.e. partial evaluation) for the C language came from C. Consel in the 90' [START_REF] Consel | A general approach for run-time specialization and its application to C[END_REF]. But at that time the underlying hardware was simpler in terms of memory hierarchy and ALU capability.

Install Time

Many works have tried to do detect possible optimization during the program install on a new machine.

ATLAS in 2001 [START_REF] Whaley | Automated empirical optimizations of software and the ATLAS project q[END_REF] is a BLAS implementation with semi-automatic optimization detection. Other works including source code generation push the limit farther for other mathematical kernels: FFTW in 2005 [START_REF] Frigo | The design and implementation of FFTW3[END_REF] for FFT implementations and SPIRAL for linear algebra kernels [START_REF] Puschel | SPIRAL: Code generation for DSP transforms[END_REF].

Interestingly, FFTW has a dynamic scheduler which chooses the best implementation at run-time, depending on the FFT signal size.

High Level Intermediate Representation

86

Leaving the C language offer opportunity to rely on high-level intermediate format.

87

Java hostspot compiler [START_REF] Paleczny | The java hotspot TM server compiler[END_REF] has an interesting strategy using different compiler strategy. It

92

JavaScript also uses just-in-time compilation strategy but both Java and Javascript 93 have a very costly compilation phase as described in [START_REF] Park | Reusing the Optimized Code for JavaScript Ahead-of-Time Compilation[END_REF].

94

A similar approach is described in this Vapor SIMD article [START_REF] Nuzman | Vapor SIMD: Auto-vectorize once, run everywhere[END_REF] but no practical 95 implementation is proposed. Another attempt was made with the deGoal tool [START_REF] Charles | deGoal a tool to embed dynamic code generators into applications[END_REF]. This tool allows implementing 98 similar compilation scenarios. The programming language was portable across similar 99 SIMD architectures but was at assembly level which makes complex applications difficult do implement.

Compiler Level Support for Transprecision

This section presents challenges in terms of compilation for applications using transprecision.

Transprecision and Challenges for Compilers

Transprecision computing [START_REF] Malossi | The transprecision computing paradigm: Concept, design, and applications[END_REF] is explored by the H2020 European project OPRE-COMP. The idea is to reduce energy consumption by using approximate computing. For example, the precision can be decreased using small float, i.e. 8-bit or 16-bit floating point numbers. The precision is adapted during the computation with criteria to use more precision at the end of the computation. This is particularly convenient for iterative mathematical applications where the iteration number is controlled by a diminishing value.

One of the characteristics of transprecision is the fact that is adaptated at run-time and controlled by the application of the data size which is not known at compilation time. Compiler optimization in particular loop statements cannot be used in this case because the compiler does know when applications move to more precision.

HybroLang : a New Language

In this paper we propose HybroLang , a new language, developed within the proposed HybroGen compilation platform. It permits to declare more complex data types, like vector, data with varing length and multiple arithmetics: integer, float, complex numbvers, pixels, IP addresses, etc.

Compiler: When Code Generation Should Arise ?

There are different code generation times to generate a code for an application. In a standard development flow, the code is generated at static compilation time. Data values are resolved at run-time and with only one step of compilation before the execution, some optimization cannot be applied.

Usually programmers want to write a small code with good performance on all computers. This is not the case in the real life, programmers need to specialize code for a specific architecture. Moreover, programmers develop different version of the code to adapt programs to data types like float, integer and different word size.

With HybroGen we propose to generate instructions during the execution to take advantage of data values resolved at run-time. Our platform allows experimentations on multiple scenarios of code generation time. When the data set is not known at compile time, whatever the static compilation time devoted to the kernel compilation, the compiler should be conservative and could not take into account the data characteristics which could be used for optimization (loop bound, data values, needed precision, etc.).

Run-time Code Generation Scenarios

In our case we want to generate the binary code at run-time and use dynamic compilation (b). We list the following code generation scenarios:

Program init: the code generation takes place at the beginning of the application and a minimal knowledge make small optimization possible. The binary code is generated once, and the binary code is called many times.

Kernel init: in the second scenario, code generation is done at each kernel invocation.

The data set information are so rich that the generated code is very efficient, thanks to the optimizer contained in the code generator. The code generation time could be amortized at each kernel call.

Application driven: in some situation, the application has a knowledge of the context and the programmer want to have the control of the code generation. For example many mathematical applications have loops controlled by a "residue" value. This value can be used to decide when the code generation should be called to improve the precision.

Those scenarios will be illustrated on some tutorial examples in section 4.

Language

In this paper, we propose HybroLang is a new language with syntax close to C programming language. We develop HybroLang to add support for dynamic compilation of applications with different targeted architectures. This language uses specific data types which are defined with a triplet type, vector size and word size. This language is used only to describe the part of kernel that we want to optimize, we named this part a compilette. The other part of the program is written with the language targeted, in this paper we have chosen C language, but we can imagine other languages like JavaScript or python.

Data and Code Generation Interleaving

The main characteristics of our HybroGen environment are:

• The possibility to delay the code generation and have versatile code generation scheme that will be demonstrated later in this article, Those characteristics will be demonstrated in the later examples. The input is a kernel described with HybroLang language described previously. Our compiler HybroGen implements different passes of compilation, like a classic compiler but at the output it produces a code in an existing programming language, for this paper it produces C code. HybroLang requests the database to construct a code generator which writes the correct encoding at run time. After using HybroLang , we use a compiler for the second compilation time (c) like gcc or clang, in this paper we have used gcc. Finally, depending on the scenario choice, at execution time (d), the code of the compilette is executed which generates the instructions that are executed at the backend.

HybroGen Platform

Demonstration of HybroGen for Transprecision Applications

In this section we present demonstrations and results of using HybroGen for transprecision applications on different platforms like power or RISC-V.

Experimental Platform

To run demonstrations a system-level simulator and real platform are used. Qemu [START_REF] Bellard | a fast and portable dynamic translator[END_REF] is used to simulate POWER8 and RISC-V architectures. This simulator exists for different architectures like x86, MIPS or ARM and support different variants. For example, there is a version for RISC-V 32 bits and another for the 64 bits architecture. In this paper we use qemu-riscv32 version 5.0.0 and qemu-ppc64le version 5.0.0. We also verify our results on a physical POWER8. For the static compilation, e.g., the source to binary compilation, we use riscv32-elf-gcc-9.3.0 and powerpc64le-linux-gnu-gcc-8. The figure 3 shows the different steps of our compilation chain from the figure 2 section (b) which rewrites the HybroLang section of the application to a C version which will be able to generate multiple binary version. This capability to generate multiple binary version is very important on muliple contexts: adapt to hardware characteristics, dataset parameter and, as we focus on this article, on dataset precision.

Application Scenarios of HybroGen

Dynamic compilation allows code generation at different times during the execution of a program. Figure 4 presents three moments to generate instructions corresponding to the kernel similar to Figure 1 but in an algorithmic form. In the first case, the code is generated only once and at program initialization. This case illustrates a situation where the generated code is execute more than once, N times in the figure, to amortize the cost of dynamic compilation. In the figure 4 we can see that parameter of the execution, i.e. i, is not used for the code generation but it can use in parameter of the code generated call.

We also see the specialization parameter s which is a parameter of the generated function genAdd in this figure. In the second case figure 4 part (2), the code generation takes place just before the execution of the kernel, this maps to the kernel initialization. In this case, we want to generate the most optimized code which is specific to one execution with constant injection. The cost of the code generation can be amortized because this compilette uses less instructions than a classical compiler. In the last case figure 4 part

(3), code generation can take place several times during the execution and it sets off by a condition on data value. The code generation is driven by the application and especially the execution and results values. In transprecision applications, this ability is very useful to adapt precision according to data value. Code generation time where i is the compilette parameters, s corresponds to the parameters to specialize to compilette and t is the threshold which is a condition to re-generate code

Demonstration Example

To illustrate the three cases described in figure 4, we have chosen three examples: conversion Celcius to Fahrenheit, multiplication with a specialization on a constant value and square root with Newton's algorithm. The latter example demonstrates the advantage of using HybroGen for transprecision applications.

Celcius to Fahrenheit

The first demonstration is the conversion of degree Celcius to degree Fahrenheit.

This example illustrates the case of an expression of mutliple arithmetics operations. We have chosen this code example for its simplicity. The code of the compilette is described with HybroLang language as following: The compilette C2F is called in the main program with different parameters which corresponds to temperature values that we want to convert. This is a typical example of one code generation for several calls to generated code. A more sophisticated version can have data types (int in this example) in parameters and the same compilette can generate code for int, float 16 bits, float 32 bits or whatever. The data value description is very flexible with HybroLang .

Multiplication with Specialization

In this part we focus on a small example of using specialization with HybroLang , which illustrates a functionality specific to HybroGen : injected value at run-time. This code is as small as possible to focus on specialization on data at run-time. We have chosen a compilette which computes a multiplication of a value by a constant. This constant } while ( i s F l o a t || ( ! i s F l o a t && ( d i f f > precd ) ) ) ;

}

In this code, we can see two calls to genIterate, which is the function responsible for code generation, the first with float precision and the second with double precision.

The computation of one step of iterations corresponds to the call of fPtr1 or fPtr2 where value maps to the previous result, af is the precision that we want to obtain. At the end of the loop, we compute the difference between the current and the previous result to decide if the precision has been reached to change to double precision or to stop the program.

An example of HybroGen Compilation for Multiplication with Specialization

To detail the different step of HybroGen flow, we provide an example of the application Multiplication with specialization described previously. A careful reader has noticed that those tutorial codes are not optimal. We know that there is specialized instructions which use constant values, these examples are only to explain the workflow and shows that HybroGen could generate multiple binary code from the same compilette.

Metrics and Evaluation of HybroGen Flow

To evaluate HybroGen compilation flow, the number of Lines of Code (LoC) is a good indicator to evaluate the extra cost to port C code to hybrid HybroLang and C code. Table 1 presents the number of LoC for three applications and for the different parts of the code. Compilette code is written with HybroLang and we can see that it is very small 12 and 14 lines depending on the application. This code is compiled with

HybroLang which generates C code specific for an architecture. For all the applications and the two targeted architecture, the number of lines of C code generated is between 96 and 284. This difference can be explained by the number of instructions in the database for each architecture and for the semantic instructions and arithmetic use in the application. The latter column corresponds to C code use for management like call to the generators, call to generated code and parameters for management. This code is the same for all architectures and depends on applications. For these applications the number of lines of code is between 28 and 55.

Applications

Discussion and working direction

This article has presented a new compilation infrastructure called HybroGen . We have shown that our tool is already working on small examples, which was a challenge in term of compilation chain complexity.

Our technical targeted metrics are (1) code generation speed and (2) code generation size. As we use the same code generation scheme than deGoal [START_REF] Charles | deGoal a tool to embed dynamic code generators into applications[END_REF] we already know that those two metrics are similar and faster and smaller than any JIT compiler.

As scientific targets we want to follow two main objectives which are: Scientific support for transprecision: we target to support applications containing runtime transprecision and support scientific transprecision applications. This objective is very useful on hardware platforms which contains many floating point representations. For example, RISC-V platform from GreenWaves, the GAP9, has support for floating point variants of 8, 16 and 32 bits. RISC-V standard platform has support for 32 and 64 bits while IBM Power8 platform has support for 32, 64 bits. Those platforms are good candidates.

Compilation support for non Von Neumann architecture: we also support code generation for "in memory computing" devices [START_REF] Noel | A 35.6 TOPS/W/mm 2 3-Stage Pipelined Computational SRAM With Adjustable Form Factor for Highly Data-Centric Applications[END_REF]. On those devices the difficulty comes from the fact that there is two synchronized instruction flows to generate. This platform is not in the scope of this article.

Metrics to fight with : this article has showed a proof of concept an initial results. We'll continue to improve our HybroGen tool and in the future experiments we will focus on other metrics which are : Speedup for scientific applications : thanks to our run-time optimization we will have speedups that will help scientific applications which need run-time transprecision support. Mainly those whose rely on a residue value that decrease. We have shown in this article that those capabilities are useful, does not rely on 473 complex and big JIT infrastructures and the binary code is small and fast.

ISA

474

We continue to extend our HybroGen infrastructure and develop demonstrations

88

  starts the execution by interpreting the code, then depending on the number of function 89 calls, it applies different aggressiveness levels of compilation. But the strategy is only 90 based on function call statistics and execution timing. There is no direct relation between 91 the dataset and the compilation strategy and no vectorization strategy.

Figure 1 .Figure 1

 11 Figure 1. Chronograms of different compilation scenarios. On the top the static compiler (a), without any code specialization at run time. On the bottom our proposition for dynamic compilation (b) with 3 scenarios: binary code specialization at program init, kernel init or application controlled Figure 1 explains our goal in terms of code generation. On the top of the figure, we illustrate the timing between static compilation (a) and execution time. We illustrate a classical use case where the execution is composed of a prelude, multiple kernel executions and a postlude.

Figure 2 .

 2 Figure 2. Overview of HybroGen platform with 4 steps: (a) install, (b) compilation source to source, (c) compilation source to binary and (d) execution HybroGen is composed of 4 steps, shown in figure 2 which correspond to different times: install time, source to source compilation time, source to binary compilation time and execution time. At install time (a), the description of the instruction set architecture (ISA) is stored in a database. The compilation time (b) on figure 2 maps to the compilation source to source and is specific to the proposed HybroGen compilation flow.

Figure 3 .

 3 Figure3. HybroLang compilation chain. Containing classical compilation steps: lexer and parser, generic and specific IR optimizations and also specific ones: using a SQL data base to store instructions specifications and C code generation, which will act as polymorphic binary code generator at run-time

Figure 4 .

 4 Figure 4.Code generation time where i is the compilette parameters, s corresponds to the parameters to specialize to compilette and t is the threshold which is a condition to re-generate code

Listing 1 :

 1 Celcius to Fahenreit compilette h 2 _ i n s n _ t * genC2F ( h 2 _ i n s n _ t * p t r ) u r n ( h 2 _ i n s n _ t * ) p t r ; } In all code examples, the compilette begins with the two symbols #[ and finish with ]#. Only the compilette is rewrite in C language by HybroLang . Other lines, corresponds to the prototype of the C function and the last line is the return of the function. This example only uses arithmetic operations and we can see that HybroLang allows affectation with more than one operator. The function named genC2F contains the description of the compilette and returns a pointer to the beginning of the code generated.

Listing 4 :

 4 is not known at static compilation time, but only at execution time. HybroGen can inject the value, b in the following code identified by #(b) in the compilette , during the execution. The generator named genMult written using C language and the compilette mult described with HybroLang are given below: Listing 2: Multiplication with specialization compilette h 2 _ i n s n _ t * genMult ( h 2 _ i n s n _ t * ptr , i n t b ) { # [ i n t 32 1 mult ( i n t 32 1 a ) u r n ( h 2 _ i n s n _ t * ) p t r ; } The sentence, which contains #(b) is an example of data injection which implements code specialization at run time. The result of this compilette is a function which multiplies by the specific constant b.4.3.3. Square Root with Newton's AlgorithmThis application is a perfect example of using transprecision for computation. The computation of the square root with Newton's algorithm uses a function for one step of the iteration. At each step, an approximate value of the square root of the value u is computed with the formula: (u + (val/u))/2 where val is the precision. This function written with HybroLang is: Listing 3: Square root with Newton's algorithm compilette h 2 _ i n s n _ t * g e n I t e r a t e ( h 2 _ i n s n _ t * ptr , i n t FloatWidth ) { # [ f l t # ( FloatWidth ) 1 i t e r a t e ( f l t # ( FloatWidth ) 1 u , f l t # ( FloatWidth ) 1 val , f l t # ( FloatWidth ) u r n ( h 2 _ i n s n _ t * ) p t r ; } At the beginning of the application, float precision is sufficient to compute an approximate result but during the execution if there is no difference between the current and the previous result, then the application generates a new code with better precision.The program stops when a step of the iteration has achieved a result with the required precision. The main program is described below: Square root with Newton's algorithm main i n t main ( i n t argc , char * * argv ) { . . . f P t r 1 = ( p i f f ) g e n I t e r a t e ( ptr , FLOAT ) ; do { i f ( ( d i f f < p r e c f ) && i s F l o a t ) { / * Code g e n e r a t i o n w i t h d o u b l e f o r b e t t e r p r e c i s i o n * / f P t r 2 = ( pidd ) g e n I t e r a t e ( ptr , DOUBLE ) ; i s F l o a t = F a l s e ; } value = ne xt ; ne xt = ( i s F l o a t ) ? f P t r 1 ( value , af , 2 . 0 ) : f P t r 2 ( value , af , 2 . 0 ) ; d i f f = ABS ( n extvalue ) ;

4. 4 . 1 .

 41 Static Compilation with HybroLangHybroLang compiler transforms the compilette in C Code which is composed of call to generate function. Each instruction of the compilette corresponds to one or more call to generate functions which are in charge to select instructions based on data types and type of each operand. In Multiplication with specialization, the main operation is the multiplication, HybroLang converts that in a call to power_genMUl_3 or riscv_genMUl_3 respectively for POWER and RISC-V architecture, the number 3 refers to the number of operands because C language does not allow overloaded function. In this example, the first and the second parameters are the same and maps to an integer register with a word size fixed to 32 bits and initialized with value of b to specialize in this code on b. Finally this register contains the result of the multiplication. The third parameter maps to the first register in input which is represented by the variable a in the initial code. To summaize, the generation of the code for the multiplication of a by b to transform on two functions of generation as following: h2_sValue_t a = { REGISTER , ' i ' , 1 , 3 2 , 1 0 , 0 } ; h2_sValue_t h2_0 = { REGISTER , ' i ' , 1 , 3 2 , 6 , 0 } ; riscv_genMV_2 ( h2_0 , ( h2_sValue_t ) {VALUE, ' i ' , 1 , 3 2 , 0 , ( b ) } ) ; riscv_genMUL_3 ( h2_0 , h2_0 , a ) ; 4.4.2. Back-end Code Generation Using Database Request Generation functions are composed of a conditional structure to select the best instruction. For example, riscv_genMV_2 is used to select instruction for move operation with 2 operands. This function is generated by HybroLang as following: void riscv_genMV_2 ( h2_sValue_t P0 , h2_sValue_t P1 ) { i f ( ( P0 . a r i t h == ' i ' ) && ( P0 . wLen <= 3 2 ) && ( P0 . vLen == 1 ) && i s R e g i s t e r ( P0 ) && i s R e g i s t e r ( P1 ) ) { RV32I_MV_RR_I_32 ( P0 . regNro , P1 . regNro ) ; } e l s e i f ( ( P0 . a r i t h == ' i ' ) && ( P0 . wLen <= 3 2 ) && ( P0 . vLen == 1 ) && i s R e g i s t e r ( P0 ) && i s V a l u e ( P1 ) ) { RV32I_MV_RI_I_32 ( P0 . regNro , P1 . valueImm ) ; } e l s e { h2_codeGenerationOK = 0 ; } }In this function, the first case maps to move operation from register P1 to register P0, the second case corresponds to move operation of integer P1 to register P0. We also generated error messages if there is no operation for this operand. For example, move a float into a register is not possible with this selector function. Functions like RV32I_MV_RI_I_32 called by selector function write instruction encodage. This macro is generated with SQL request to a database which contains instructions encodage and format for different architectures and variants. The Application Binary Interface (ABI) is also described in the database and requested by HybroLang to build c code.4.4.3. Binary Code Generation at ExecutionFinally, the execution of this compilette on RISC-V architecture produces these instructions:Register t1 and r15 respectively for RISC-V and POWER, contain the specialize value: 3 in this execution. This value is multiplying with instructions mull and mullw by the value in input register a0 or r15. To improve the performances of HybroGen , some passes of optimization are needed to reduce to number of move. For example, the result of the multiplication can be stored in t1 or r3, the ouput register for respectively RISC-V and POWER.The example below shows instructions generated with a specialize value fixed to -5:

463 6 .

 6 Conclusion 464 In this article we have demonstrated the opportunity to break classical compilation 465 static strategies and open the door to make applications auto-adaptive to the context. 466 We have demonstrated three new code generation scenarios which have binary 467 code generation at run-time in common. The first one shows only binary code generation, 468 the second code specialization at run time and the third shows a code specialization 469 based on transprecision. 470 Our HybroGen infrastructure proof of concept give to the programmer the possibil-471 ity to control his application and link data parameter to the architecture.

  472

475

  of its capabilities in two directions:[START_REF] Patterson | Years of computer architecture: From the mainframe CPU to the domain-specific tpu and the open RISC-V instruction set[END_REF] on scientific demonstrators of the transprecision 476 capabilities because it is a challenge for IA applications and (2) on heterogeneity, i.e. 477 the capability to generate binary code at run-time for multiple processors from high 478 performance Power8 up to small RISC-V compute nodes. 479 Our HybroGen infrastructure will be open-source but has not reached a release 480 quality. Nevertheless, we share the code examples version (HybroLang , generated C 481 code) in the following repository https://github.com/oprecomp/HybroLang. Running 482 those code allows reproducing the code generation scenarios described in this article.

Table 1 :

 1 Lines of Code (LoC) of C and HybroLang for demonstration applications

		Compilette code Generated code	Main without
		(HybroLang )	(C)		compilette (C)
			RISC-V POWER
	Celcius to Fahrenheit	12	179	284	36
	Multiplication	12	96	102	28
	with specialization
	Square root	14	159	188	55
	with Newton algorithm

Table 2 :

 2 Supported hardware platforms, working both in simulation mode and on hardware platforms a Makefile containing the commands to run the application. The public repository is 461 https://github.com/oprecomp/HybroLang and contains a README which explains 462 how to reproduce the experimentation and run the applications.

		Instruction set emulator	Hardware
	RISCV	qemu-riscv32	GreenWave / Gap9 platform
	CSRAM	qemu-riscv32	CEA / RiscV + In MemoryComputing
		+ In Memory Processing plugin
	Power	qemu-ppc64le	IBM / Power8 systems
	Kalray	kvx-mppa	Kalray / Coolidge

This work was supported by theEuropean H2020 FET project OPRECOMP under Grant 732631 Version June 11,

submitted to J. Low Power Electron. Appl. https://www.mdpi.com/journal/jlpea

Code generation speed : as we can regenerate the binary code very often, it's very important to generate it as fast as possible. HybroGen is designed to generate binary code generator which are very fast because our compiler is able to restrict the code generation to the only instructions that are needed by the application.

Code generator size thanks to the previous point, our final code generator are very small (KB order or magnitude), does not rely on external library and can be suited for embedded systems.

The table 2 summarized the current supported platforms.

Our HybroGen infrastructure will be open source but is not yet ready for a public release. Nevertheless, it is possible to the HybroLang input sources, the output C and


Khalid Saleem
email: saleem@lirmm.fr

Zohra Bellahsene

Automatic Complex Schema Mapping Discovery and Validation by Structurally Coherent Frequent Mini-Taxonomies

Keywords: Simple Matching, Complex Matching, Mini-taxonomies, Collaboration, Tree Mining, Large scale

Match cardinality aspect in schema matching is categorized as simple element level matching and complex structural level matching. Simple matching comprises of 1:1, 1:n and n:1 match cardinality, whereas n:m match cardinality is considered to be complex matching. Most of the existing approaches and tools give good 1:1 local and global match cardinality but lack the capabilities for handling the complex cardinality issue. In this paper we demonstrate an automatic approach for creation and validation of n:m schema mappings. Our technique is applicable to hierarchical structures like XML Schema. Basic idea is to propose an n:m nodes mapping between children (leaf nodes) of two matching non-leaf nodes of two schemas. The similarity computation of the two non-leaf nodes is based upon the syntactic and linguistic similarity of node labels; supported by similarity among the ancestral paths from nodes to the root. The n:m mapping proposition is then verified with the help of mini-taxonomies extracted from a large set of same domain schema trees. The mini-taxonomies are automatically extracted using frequent sub-tree mining approach; higher the frequency, higher the confidence of reliability. The verification algorithm performs comparison between the minitaxonomies and the subtrees rooted at non-leaf nodes which guide the system for authenticity of proposed n:m mapping.

INTRODUCTION

Schema matching relies on discovering correspondences between similar elements of two schemas. Several different types of schema matching tools [START_REF] Rahm | A survey of approaches to automatic schema matching[END_REF][START_REF] Shvaiko | A Survey of Schema-Based Matching Approaches[END_REF] have been studied, demonstrating their benefit in different scenarios. In data integration schema matching is of central importance [START_REF] Batini | A Comparitive Analysis of Methodologies for Database Schema Integration[END_REF]. The need for information integration arises in data warehousing, OLAP, data mashups [START_REF] Jhingran | Enterprise Information Mashups: Integrating Information, Simply -Keynote Address[END_REF], and work flows. Omnipresence of XML as a data exchange format on the web and the presence of metadata available in that format force us to focus on schema matching, and on matching for XML schemas in particular.

Match cardinality aspect in schema matching is categorized as simple element level matching [START_REF] Rahm | A survey of approaches to automatic schema matching[END_REF] and complex structural level matching. Simple matching comprises of 1:1, 1:n and n:1 match cardinality, whereas n:m match cardinality is considered to be complex matching. Research literature shows numerous works [START_REF] Bernstein | Industrial-Strength Schema Matching[END_REF][START_REF] Do | Matching large schemas: Approaches and evaluation[END_REF][START_REF] Ehrig | QOM -Quick Ontology Mapping[END_REF][START_REF] Giunchiglia | S-Match: an Algorithm and an Implementation of Semantic Matching[END_REF][START_REF] Hernedez | Clio: A semi-automatic tool for schema mapping[END_REF][START_REF] Melnik | Rondo: A Programming Platform for Generic Model Management[END_REF][START_REF] Saleem | Porsche: Performance oriented schema mediation[END_REF] on simple matching. Most of the existing approaches and tools give good 1:1 local and global match cardinality but lack the capabilities for handling the complex cardinality issue. Therefore, in this paper, we try to propose a technique for complex match discovery.

In this work, we consider schemas to be rooted, labeled trees. This supports the computation of contextual semantics in the tree hierarchy. The contextual aspect is exploited by tree-mining, making it feasible to use almost automated approximate schema matching [START_REF] Doan | Learning to match ontologies on the Semantic Web[END_REF], even in a large-scale scenario (schemas have large number of nodes). The individual semantics of node labels have their own importance. We utilize linguistic matchers, based on tokenisation, and synonym and abbreviation tables, to extract the concepts hidden within them.

Tree mining techniques extract similar subtree patterns from a large set of trees and predict possible extensions of these patterns. A pattern starts with one node and is incrementally augmented. There are different techniques [START_REF] Chi | Frequent subtree mining -an overview[END_REF] which mine rooted, labeled, embedded or induced, ordered or unordered sub-trees. The function of tree mining [START_REF] Zaki | Efficiently Mining Frequent Embedded Unordered Trees[END_REF] is to find sub-tree patterns that are frequent in the given set of trees. We have utilised this aspect of tree mining for computing the mini-taxonomies for domain specific concepts, from a given set of schemas, input as trees [START_REF] Saleem | Automatic extraction of structurally coherent mini-taxonomies[END_REF]. The method is a combination of concept terms analysis, using syntactic, lexical and contextual meanings of terms and tree mining algorithm.

Our Contributions

In this paper, we focus particularly, though not exclusively, on n:m complex mappings. We present a new methodology for matching two schemas, covering the element level and structural level mappings discovery. The main features of our approach are as follows:

1. The approach is almost automatic and hybrid in nature.

2. It is based on a tree mining technique supporting large size schema matching. To support tree mining, we model schemas as rooted ordered (depth-first) labelled trees.

3. It extends the tree mining data structure proposed in [START_REF] Zaki | Efficiently Mining Frequent Embedded Unordered Trees[END_REF]. It uses ancestor scope properties (integer logical operations) on schema nodes to enable fast calculation of contextual (hierarchical) similarity between them.

4. Our methodology discovers semantically approximate 1:1, 1:n, n:1 simple mappings between nodes of the two schema trees.

5. It suggests perspective n:m complex mappings between the two schemas and then validates these propositions using already available mini-taxonomies, representing schema concepts. 7. It intuitively highlights the use of automatically extracted mini-taxonomies from a large set of domain specific schemas, supporting the collective intelligence aspect.

8. The approach is implemented as a prototype. We report on experiments using different real1 and synthetic scenarios.

Outline

The remainder of the paper is organized as follows. Section 2 presents the preliminaries of our matching approach, related definitions and concepts. Section 3 gives the related work in schema matching, specifically complex schema matching.

In Section 4 we describe our approach for discovering and validating complex schema matching between schemas processed as tree structures. Section 5 demonstrates a running example to support our approach. Section 6 presents the experimental evaluation along with discussion on the results. Section 7 outlines future perspective and concludes.

PRELIMINARIES

Schema matching finds similarities between elements in two or more schemas. We model the schemas as tree structures for fast contextual semantics extraction.

Definition 1 (Schema Tree):

A schema S = (V, E) is a rooted, labelled tree [START_REF] Zaki | Efficiently Mining Frequent Embedded Unordered Trees[END_REF], consisting of nodes V = {0, 1, . . . , n},

and edges E = {(x, y) | x,y ∈ V }. One distinguished node r ∈ V is called the root, and for all x ∈ V , there is a unique path from r to x. Further, lab:V → L is a labelling function mapping nodes to labels in L = {l1, l2, . . . }.•

Match Cardinality

There can be several types of correspondences between elements of two schemas, depending upon the number of elements participating in a match, as schema match cardinality [START_REF] Rahm | A survey of approaches to automatic schema matching[END_REF]. The match cardinality is mainly categorized as global or local. Global cardinality is related to the number of appearances of an element in the total match results between two input schemas. Local schema match cardinality characterises the number of elements participating in a certain match. Local schema match cardinality can be of four types.

There are three simple element level match cardinalities and one structural level complex match cardinality [START_REF] Rahm | A survey of approaches to automatic schema matching[END_REF]. Since we are matching schema tree structures (elements are nodes), where the leaf nodes hold data (XML schemas), we place more emphasis on leaf node matching. Our categorisation of node match cardinalities is driven by the node's leaf or non-leaf (inner node) status.

i) 1:1 -one node of source schema corresponds to one node in the target schema; leaf:leaf or non-leaf:non-leaf.

ii) 1:n -one node in the source schema is equivalent to a composition of n leaves in the target schema; leaf:non-leaf, where a source leaf node is mapped to a set of n leaf nodes of the subtree rooted at the non-leaf node in the target schema. iii) n:1 -n leaves in source schema compositely map to one leaf in the target schema; non-leaf:leaf, allowing a set of n leaf nodes of the subtree rooted at the non-leaf node in the source schema, to be mapped to a target leaf. iv) n:m -n leaves in source schema compositely map to a composition of m leaves in the target schema; non-leaf:nonleaf, allowing a set of n leaf nodes of the subtree rooted at the non-leaf node in the source schema, to be mapped to a set of n leaf nodes, of subtree rooted at the non-leaf node in target schema.

The first three types of local match cardinality are normally evaluated using the element level information. Whereas the n:m cardinality also requires structural information of the input schemas.

Example 1 (Match Cardinality): For 1:1, cardinality is straightforward. Let us consider Figure 1 for 1:n and n:1 match. A match is found between Ssourcename[2, 2]2 , child of author, and Stargetname [START_REF] Batini | A Comparitive Analysis of Methodologies for Database Schema Integration[END_REF][START_REF] Boukottaya | Schema matching for transforming structured documents[END_REF], child of writer, with children first and last. We have a 1:2 mapping (name)source : (namefirst, namelast)target 3 . Also, there is a match between Ssourcepublisher [START_REF] Bernstein | Industrial-Strength Schema Matching[END_REF][START_REF] Boukottaya | Schema matching for transforming structured documents[END_REF] and Stargetpublisher [START_REF] Dhamankar | imap: Discovering complex semantic matches between database schemas[END_REF][START_REF] Dhamankar | imap: Discovering complex semantic matches between database schemas[END_REF], implying a n:1 mapping of (publishername)source : (publisher)target, i.e, 1:1 mapping.• Semantically speaking, a match between two nodes is fuzzy. It can be either an equivalence or a partial equivalence. In a partial match, the similarity is partial. It is highlighted in the example 2.

Label Semantics

Label semantics correspond to the meaning of the label (irrespective of the node it is related to). It is a composition of meanings attached to the tokens making up the label. As shown by Examples 3 and 4, different labels can represent similar concepts.

Definition 2 (Label Semantics)A label l is a composition of m strings, called tokens. We apply the tokenisation function tok which maps a label to a set of tokens T l = {t1, t2, . . . , tm}. Tokenisation [START_REF] Giunchiglia | S-Match: an Algorithm and an Implementation of Semantic Matching[END_REF] helps in establishing similarity between two labels. tok : L → P(T ), where P(T ) is a power set over T.

Node Semantics

Semantics of node are given with combination of the semantics of the node's label and its contextual placement in the tree [START_REF] Giunchiglia | S-Match: an Algorithm and an Implementation of Semantic Matching[END_REF]. Contextual placement of a node within the tree is calculated with the help of the concept Node Scope.

Definition 3 (Node Scope)In schema S each node x ∈ V is numbered according to its order in the depth-first traversal of S (the root is numbered 0). Let SubTree(x) denote the sub-tree rooted at x, and x be numbered X, and let y be the rightmost leaf (or highest numbered descendant) under x, numbered Y . Then the scope of x is scope(x)=[X,Y]. In-tuitively, scope(x) is the range of nodes under x, and includes x itself, see Figure 1. The count of nodes in SubTree(x) is Y -X + 1.

Scope Properties

Scope properties help in discovering the contextual placement of a node [START_REF] Zaki | Efficiently Mining Frequent Embedded Unordered Trees[END_REF]. Property testing involves simple integer comparisons. We utilise these properties in frequent subtree detection. Example 5 gives an overview of the use of scope values.

Node Scope Properties

Given 1. The nodes name [START_REF] Batini | A Comparitive Analysis of Methodologies for Database Schema Integration[END_REF][START_REF] Batini | A Comparitive Analysis of Methodologies for Database Schema Integration[END_REF], name [START_REF] Boukottaya | Schema matching for transforming structured documents[END_REF][START_REF] Boukottaya | Schema matching for transforming structured documents[END_REF] and title [START_REF] Chi | Frequent subtree mining -an overview[END_REF][START_REF] Chi | Frequent subtree mining -an overview[END_REF] are leaf nodes according to Property 1. Whereas book[0, 5],author [START_REF] Aumueller | Schema and ontology matching with coma++[END_REF][START_REF] Batini | A Comparitive Analysis of Methodologies for Database Schema Integration[END_REF] and publisher [START_REF] Boukottaya | Schema matching for transforming structured documents[END_REF][START_REF] Chi | Frequent subtree mining -an overview[END_REF] satisfy Property 3, thus these are the non-leaf nodes. There are two nodes with label name. If we have to check for the name of author, we can perform the Ancestor check (Property 3) on each of the two nodes with respect to node author [START_REF] Aumueller | Schema and ontology matching with coma++[END_REF][START_REF] Batini | A Comparitive Analysis of Methodologies for Database Schema Integration[END_REF]. The check returns true for node name [START_REF] Batini | A Comparitive Analysis of Methodologies for Database Schema Integration[END_REF][START_REF] Batini | A Comparitive Analysis of Methodologies for Database Schema Integration[END_REF] and false for node name [START_REF] Boukottaya | Schema matching for transforming structured documents[END_REF][START_REF] Boukottaya | Schema matching for transforming structured documents[END_REF]. Consider node author [START_REF] Aumueller | Schema and ontology matching with coma++[END_REF][START_REF] Batini | A Comparitive Analysis of Methodologies for Database Schema Integration[END_REF] and node publisher [START_REF] Bernstein | Industrial-Strength Schema Matching[END_REF][START_REF] Boukottaya | Schema matching for transforming structured documents[END_REF]. The two nodes have non-overlapping scope according to Property 3, and can be considered as cousin nodes.

RELATED WORK

Previous work on schema matching was developed in the context of schema translation and integration [START_REF] Bernstein | Industrial-Strength Schema Matching[END_REF][START_REF] Aumueller | Schema and ontology matching with coma++[END_REF], knowledge representation [START_REF] Giunchiglia | S-Match: an Algorithm and an Implementation of Semantic Matching[END_REF], machine learning, and information retrieval [START_REF] Doan | Learning to match ontologies on the Semantic Web[END_REF]. All these approaches aimed to provide a good quality matching but require significant human intervention.

The direct human participation in large scale scenarios requires very user friendly interfaces, and abates the overall performance of the tool. Therefore we need to automate the schema matching approaches to the maximum.

Simple matching with quality has been successfully demonstrated in [START_REF] Aumueller | Schema and ontology matching with coma++[END_REF][START_REF] Giunchiglia | S-Match: an Algorithm and an Implementation of Semantic Matching[END_REF][START_REF] Melnik | Similarity flooding: A versitile graph matching algorithm and its application to schema matching[END_REF] by utilising element level and structural level schema knowledge. There has been very limited work on complex schema mapping. Use of data instance and machine learning techniques for simple and complex schema matching has been shown in [START_REF] Doan | Learning to match ontologies on the Semantic Web[END_REF][START_REF] Dhamankar | imap: Discovering complex semantic matches between database schemas[END_REF] for relational and XML schemas. [START_REF] Wang | Towards user centric schema mapping platform[END_REF] presents a user-centric approach using fixed point iteration algorithm similarity flooding (SF) [START_REF] Melnik | Similarity flooding: A versitile graph matching algorithm and its application to schema matching[END_REF] and other linguistic techniques to calculate complex mappings.

Authors in [START_REF] Dhamankar | imap: Discovering complex semantic matches between database schemas[END_REF] demonstrate a semi-automatic tool called iMAP, which discovers 1:1 and 1:n mappings between two relational schemas. The approach utilises machine learning algorithms on data instances to predict 1:n mapping expressions. It employs knowledge like past complex matches, domain integrity constraints, and overlap data. In [START_REF] He | Discovering complex matchings across web query interfaces: a correlation mining approach[END_REF], He et al. workout a mining technique for integrating a large number of web query interfaces, considered as schemas. The [START_REF] Saleem | Porsche: Performance oriented schema mediation[END_REF] 2008 PORSCHE: Provides a large scale schema matching and integration method using tree mining technique 1:1,1:n Wang et al. [START_REF] Wang | Towards user centric schema mapping platform[END_REF] 2007 SCIA: Presents an interactive schema matching tool with the ability to create executable mappings create executable mappings n:m Lee et al. [START_REF] Lee | Computing simple and complex matchings between xml schemas for transforming xml documents[END_REF] 2006 Computes similarity based upon domain ontology (evolves on user feedback), and ancestral path similarity 1:1,1:n Boukottaya et al. [START_REF] Boukottaya | Schema matching for transforming structured documents[END_REF] 2005 The approach exploits the ancestor, child and leaf context of elements to compute similarity 1:1 Do et al. [START_REF] Do | Matching large schemas: Approaches and evaluation[END_REF] 2007 COMA++:Finds similarities between two large schemas/ontologies, using several lexical and contextual algorithms, compositely 1:1

Bernstein et al. [START_REF] Bernstein | Industrial-Strength Schema Matching[END_REF] 2004 PROTOPLASM:Presents a interactive framework to incorporate state of the art matching techniques, ranging from string similarity to data mining algorithms 1:1

He et al. [START_REF] He | Discovering complex matchings across web query interfaces: a correlation mining approach[END_REF] 2004 MGS/DCM:Proposes automatic correlational data mining techniques for schema matching and integration, holistically n:m Dhamankar et al. [START_REF] Dhamankar | imap: Discovering complex semantic matches between database schemas[END_REF] 2004 iMAP: Computes complex match expressions using data instance based machine learning techniques n:m Ehrig et al. [START_REF] Ehrig | QOM -Quick Ontology Mapping[END_REF] 2004 QOM:Matches large ontologies with time performance in view, employing iteratively lexical match algorithms to reduce the search space for an element with each iteration 1:1

Giunchiglia et al. [START_REF] Giunchiglia | S-Match: an Algorithm and an Implementation of Semantic Matching[END_REF] 2004 S-Match is a hybrid matcher, which utilizes Wordnet and tackles schema matching as propositional satisfiability problem 1:1

Embley et al. [START_REF] Embley | Automatic direct and indirect schema mapping: Experiences and lessons learned[END_REF] 2004 Utilizes manually constructed small ontology snippets and data ranges to discover schema matchings n:m Melnik et al. [START_REF] Melnik | Rondo: A Programming Platform for Generic Model Management[END_REF] 2003 RONDO:Uses an algorithm which propogates nodes similarity to neighbouring nodes within the iterative fix point computation Another interesting work regarding XML documents transformation in [START_REF] Lee | Computing simple and complex matchings between xml schemas for transforming xml documents[END_REF] presents comprehensively the 1:1, 1:n and n:1 schema matching approach between two schemas. The algorithms used in this work are massively dependent on structural information of schemas. The proposed method worked in two step. First, preliminary matching between leaf nodes of the two schemas are computed using an external domain ontology and leaf node similarity. In second step the contextual aspect of nodes is computed as path similarity, i.e., similarity between the ancestor nodes of the current node being matched. In the same application domain, work by Boukottaya and Vnoirbeek [START_REF] Boukottaya | Schema matching for transforming structured documents[END_REF] further enhances the contextual aspect of the nodes. The approach takes into account three levels of context similarity; ancestor, child and leaf. The two research works help in exploiting the hierarchical structures with larger depth.

[21] presents a large scale schema integration framework, which uses a top down matching approach. The technique follows the idea that some level of ancestor similarity is must for an element down the hierarchy. Linguistic and tree mining algorithms are used to compute element level matchings. Like wise QOM [START_REF] Ehrig | QOM -Quick Ontology Mapping[END_REF] is a robust, time performance method for RDF based schema and ontology matching. Use of ontologies/ontologies for finding complex matchings have also been demonstrated in some works. [START_REF] Embley | Automatic direct and indirect schema mapping: Experiences and lessons learned[END_REF] uses manually created mini-ontologies for domain specific concepts, to generate n:m correspondences between two schemas. We give a brief survey of schema matching with reference to local match cardinality in Table 1 .

COMPLEX MATCH DISCOVERY -OUR APPROACH

In this section we describe our approach toward complex match discovery. We base our work on some previous research presented in [START_REF] Saleem | Porsche: Performance oriented schema mediation[END_REF][START_REF] Saleem | Automatic extraction of structurally coherent mini-taxonomies[END_REF]. Our work is based on the concepts defined as Schema Tree, Label Semantics, Node Semantics and Scope Properties (Ancestor and Right-handside node) as given in section 2.

Architecture

The architecture of our approach for complex match discovery is shown in Figure 2. The approach is composed of four modules: (i) Pre-Phase, (ii) Mini-Taxonomies Generation, (iii) Simple Schema Matching, and (iv) Complex Match Proposition Validation, supported by a repository which houses oracles and concepts' mini-taxonomies, schemas and match results for future reuse.

Pre-Phase module processes the input as trees, calculating the depth-first node number and scope (Figure 6), for each of the nodes in the input schema trees. At the same time, for each schema tree a listing of nodes is constructed, sorted in depth-first traversal order. As the trees are being processed, a sorted global list of labels over the whole set of schemas is created by the Terms Extraction sub-module.

In Similar Terms Computation and Clustering sub-module, label concepts are computed using linguistic techniques. We tokenise the labels and expand the abbreviated tokens using an abbreviation oracle. Currently, we utilise a domain specific user defined abbreviation table. Further, we make use of token similarity, supported by an abbreviation table and a manually defined domain specific synonym table.

Label comparison is based on similar token sets or similar synonym token sets. The architecture is flexible enough to employ additional abbreviation or synonym oracles or arbitrary string matching algorithms (details in [START_REF] Saleem | Porsche: Performance oriented schema mediation[END_REF]). Similar labels are clustered together and each cluster is represented by a label from the respective cluster, which is the most frequent label with in the set of input schemas (details in [START_REF] Saleem | Automatic extraction of structurally coherent mini-taxonomies[END_REF]).

Mini-Taxonomies Generation module uses a tree mining approach to extract frequent sub-trees from the set of schema trees. We use frequent pattern growth mining algorithm based on research in [START_REF] Zaki | Efficiently Mining Frequent Embedded Unordered Trees[END_REF]. During the process all labels with in a cluster of similar labels are logically replaced by the cluster representative label. This helps in computing the right count of frequency for a label concept [START_REF] Saleem | Automatic extraction of structurally coherent mini-taxonomies[END_REF].

Simple Schema Matching module, generates simple matchings, along with complex match propositions, based upon labels' linguistic similarity and node's contextual similarity using node scope values. The node scope criteria is used to evaluate the ancestor similarity factor with time performance. Complex Match Proposition Validation (CMPV) module forms the main core of this research work. We use a novel algorithm to validate the proposed complex matches with the help of automatically generated domain specific mini-taxonomies. These two modules form the core of our work, presented in this paper. Following sections provide a detail discussion about them.

The Repository is an indispensable part of the system. It houses oracles: thesauri and abbreviation lists. It also stores schemas and mappings, and provides persistent support to the mapping process.

Simple Match Discovery

In this section we describe the Simple Schema Matching module. Before we move on, first we give a brief description of Pre-Phase module.

Pre-Phase

Algorithm nodeScope (Figure 3) is a recursive method, for calculating node scope of each node in the schema, generating a schema node list V . It takes as input the current node, its parent reference, and the node list. In its first activation, reference to the schema root is used as the current node: there is no parent, and V is empty. A new node list element is created (L3.2-6) 4 and added to V . Next, if the current node is a leaf, a recursive method update (Figure 4) is called. This adjusts the rightmost node reference for the current V element and then goes to adjust its ancestor entries in V . This method recurses up the tree till it reaches the root, and adjusts all elements on the path from the current node to the root. Next, in nodeScope (L3.11-12), the method is called for each child of the current node. Parameter d gives the depth level with in the tree during the depth-first traversal. We utilise the node depth value for adjusting the match confidence related to ancestor mapping. Simple Schema Matching module matches two schemas for possible mappings based upon the linguistic and contextual (ancestor) similarities. The method discovers mappings with 1:1, 1:n and n:1 cardinality and proposes n:m complex matches between the elements of the two schemas. The proposed n:m mappings are validated with the help of minitaxonomies representing possible domain concepts.

During simple match process, a match for every node (L5.8) from source schema tree list V1 to target schema tree list V2 is calculated. For each input node x, a set Vt of possible mappable target nodes in the target schema is created, producing the target search space for x. The criterion for the creation of this set of nodes is node label equivalence or partial equivalence (L5.9,10 for each perspective matching node (L5. [START_REF] Lee | Computing simple and complex matchings between xml schemas for transforming xml documents[END_REF][START_REF] Maedche | Measuring similarity between ontologies[END_REF][START_REF] Melnik | Similarity flooding: A versitile graph matching algorithm and its application to schema matching[END_REF][START_REF] Melnik | Rondo: A Programming Platform for Generic Model Management[END_REF][START_REF] Rahm | A survey of approaches to automatic schema matching[END_REF][START_REF] Saleem | Automatic extraction of structurally coherent mini-taxonomies[END_REF]. The candidate target node with the highest α value is selected as the mappable target node.

In ancestorMap method two functions are executed in parallel. Firstly, it checks for map existence for some ancestor node of current source node and secondly the proximity of the ancestor node from the current node. Ancestor node check is performed by utilising the ancestor node scope prop-erty, and if a map exists, then the proximity is calculated and returned as α. To proceed further, another added check is confirmed that the target schema node to which the source schema ancestor node is mapped to, is also an ancestor of the candidate target node. This is a variation of upward cotopy distance discussed in research [START_REF] Maedche | Measuring similarity between ontologies[END_REF]. The ancestor map checking also helps us partially solving the inverted node mapping problem; example 6 describes this advantage. The following formula shows the proximity calculation.

α = 1/(ddifs+ddift)
where ddifs is the depth difference between the current source node and the ancestor node for which a mapping exists and ddift is the depth difference between the candidate target node and the ancestor node in target schema to which the source ancestor node is mapped to. The maximum value for α is 0.5, i.e., when the source schema ancestor node is the parent of current source node and the target schema node to which it is mapped to is the parent node of candidate target node.

Example 6 (Inverted Node Similarity): Consider the two schema trees S1 and S2 in Figure 6. Top-down depth first matching traversal guides us to match S1[0,5]book <-> S2[0,5]book, S1 [START_REF] Aumueller | Schema and ontology matching with coma++[END_REF][START_REF] Chi | Frequent subtree mining -an overview[END_REF]author <-> S2 [START_REF] Aumueller | Schema and ontology matching with coma++[END_REF][START_REF] Chi | Frequent subtree mining -an overview[END_REF]writer (author is synonym of writer). Next, we have S1 [START_REF] Batini | A Comparitive Analysis of Methodologies for Database Schema Integration[END_REF][START_REF] Batini | A Comparitive Analysis of Methodologies for Database Schema Integration[END_REF]name <-> S2 [START_REF] Bernstein | Industrial-Strength Schema Matching[END_REF][START_REF] Bernstein | Industrial-Strength Schema Matching[END_REF]name with alpha = 0.33 and following is the S1 [START_REF] Bernstein | Industrial-Strength Schema Matching[END_REF][START_REF] Chi | Frequent subtree mining -an overview[END_REF]address <-> S2 [START_REF] Batini | A Comparitive Analysis of Methodologies for Database Schema Integration[END_REF][START_REF] Chi | Frequent subtree mining -an overview[END_REF]address. Thus overcoming the problem when address and name have siblings relationship in source schema tree and parent child relationship in target schema tree.• After selecting the best match for the source node, the method proposes the type of mapping. By default it is a 1:1 mapping, since we are comparing one node from source schema to one node in target schema. Our method is more XML schema oriented where leaf nodes denote the real data values. Therefore we propose the type of mapping biased toward the leaf nodes as discussed in section 2.1. This aspect is handled in simple match algorithm with the help of parameter β (L5.21-31). Finally, the map function creates the possible mapping from source node to target node (L5.32). The n:m complex match propositions between non-leaf nodes are further exploited in the complex match proposition validation module. The related algorithm is given in Figure 7.

Mini-Taxonomy Snippets Aspect

Before we move to the complex match proposition validation part, we present another data structure, Mini-Taxonomy Snippets, which helps in the validation process. In this section we present briefly our approach for detection of these Mini-Taxonomy Snippets or ontological concepts, as a hierarchical structure, from available domain specific schema tree structures. A domain concept is considered to be small tree structure which we call a Mini-Taxonomy. The idea is similar to research done in [START_REF] Embley | Automatic direct and indirect schema mapping: Experiences and lessons learned[END_REF]. We follow the automatic approach [START_REF] Saleem | Automatic extraction of structurally coherent mini-taxonomies[END_REF] rather then the manual snippet designing in [START_REF] Embley | Automatic direct and indirect schema mapping: Experiences and lessons learned[END_REF].

The technique has an iterative nature based on incrementally extracting frequent sub-trees from a given set of trees. The sub-tree frequency in the forest of trees is user defined parameter. The algorithm takes as input the list of terms, with similar terms linked together to form a cluster (each cluster can have one or more terms). First task performed by the algorithm is to compute the frequency of each term in the forest of trees. Next, with in each cluster, the term with the highest frequency in the forest of trees is taken as the symbol representing the cluster. The frequency of the cluster symbol is computed by adding frequencies of all the terms in the cluster. From here on the algorithm executes similar to frequent sub-tree mining algorithm given in [START_REF] Zaki | Efficiently Mining Frequent Embedded Unordered Trees[END_REF], with similar label cluster symbols as the starting labels for the data structure showing frequent sub-tree patterns. After the process is complete, and we have a list of sets of mini-taxonomies. Each list representing set of mini-taxonomies of same size.

Next we replicate this list of sets of mini-taxonomies, by replacing the cluster level similar labels in the list. Thus giving us all possible mini-taxonomies which can be considered as concept representation, frequently utilised by domain users.

Complex Match Proposition Validation

The basic idea behind the Complex Match Proposition Validation (CMPV) is to some how validate the n:m match propositions created in simple matching module. Our approach tries to utilise small conceptual taxonomies already generated from large number of schemas with in a specific domain as enumerated above. For simplicity, we structure these mini-taxonomies as individual XML schema instances and generate a data structure MiniT ax for them, similar to the input source and target schema, using the same node-Scope algorithm given in Figure 3.

Algorithm ComplexM atchV alidation takes as input V1, V2 (source and target schema nodes lists respectively) and MiniT ax (list of lists of mini-taxonomies nodes). The algorithm traverses each node x of source schema, V1, with a n:m map type (depicted as nn) toward xt node of target schema, V2 (L7.6,9). The objective of the algorithm is to certify that the leaf nodes of the sub-tree rooted at such a node x in the source schema can form a n:m mapping with the leaf nodes of sub-tree rooted at node xt in the target schema. The algorithm extracts leaf nodes labels from sub-tree rooted at x into a temporary set data structure sLeaf and similarly populates a data structure tLeaf for xt (L7.11,12).

Next, the algorithm traverses the MiniT ax data structure (L7.15) for mini-taxonomies with root node label similar to node labels of x and xt (L7.17,21). Further, the leaf nodes labels of these mini-taxonomies are extracted into temporary set data structures mT sLeaf (root label similar to x label) and mT tLeaf (root label similar to xt label) at L7.18,22.

Finally, the validation check is executed, i.e., if sLeaf is a subset of mT sLeaf and tLeaf is a subset of mT tLeaf . If such mini-taxonomies are found in MiniT ax, it certifies that the concepts at x and xt are similar and their respective leaf nodes can form a n:m mapping (L7.27-29), since the minitaxonomies have been frequently used in the domain. Thus utilising the collective intelligence over a specific domain.

Algorithm : ComplexMatchValidation

Data: V 1 , V 2 , MiniT ax V 1 , V 2 :

COMPLEX MATCH VALIDATION EXAMPLE

Figure 8 shows two schema trees related to books domain. A list of correspondences is shown in Figure 9 after the execution of simple matching (Figure 5). Simple match algorithm discover's one to one match between two corresponding elements of the two schemas. In parallel, it also proposes any possible complex match, according to the leaf/non-leaf status of the elements participating in the mapping. The possible complex match propositions are shown in brackets. The scenario presents one n:1 and four n:m complex match situations. The n:1 match given by S1.author [START_REF] He | Discovering complex matchings across web query interfaces: a correlation mining approach[END_REF][START_REF] Hernedez | Clio: A semi-automatic tool for schema mapping[END_REF]<-> S2.writer [START_REF] Embley | Automatic direct and indirect schema mapping: Experiences and lessons learned[END_REF][START_REF] Embley | Automatic direct and indirect schema mapping: Experiences and lessons learned[END_REF] proposes that all leaf nodes of S1.author [START_REF] He | Discovering complex matchings across web query interfaces: a correlation mining approach[END_REF][START_REF] Hernedez | Clio: A semi-automatic tool for schema mapping[END_REF] compositely correspond to S2.writer [START_REF] Embley | Automatic direct and indirect schema mapping: Experiences and lessons learned[END_REF][START_REF] Embley | Automatic direct and indirect schema mapping: Experiences and lessons learned[END_REF]. Thus establishing the fact, the data against element S1.name [START_REF] Hernedez | Clio: A semi-automatic tool for schema mapping[END_REF][START_REF] Hernedez | Clio: A semi-automatic tool for schema mapping[END_REF] matches to data represented by S2.writer [START_REF] Embley | Automatic direct and indirect schema mapping: Experiences and lessons learned[END_REF][START_REF] Embley | Automatic direct and indirect schema mapping: Experiences and lessons learned[END_REF] element. The general analysis of the four complex matches (S1.books[0,15]<-> S2.book [0,[START_REF] He | Discovering complex matchings across web query interfaces: a correlation mining approach[END_REF], S1.library [START_REF] Aumueller | Schema and ontology matching with coma++[END_REF][START_REF] Do | Matching large schemas: Approaches and evaluation[END_REF]<->S2.writer [START_REF] Aumueller | Schema and ontology matching with coma++[END_REF][START_REF] Chi | Frequent subtree mining -an overview[END_REF]) show that two propositions have relatively large sub-trees rooted at the non-leaf elements. Therefore presenting a collection of concepts rather than a single concept. This fact is enumerated by scanning the scope of the non-leaf node. The scrutiny of other two complex match propositions (S1.date [START_REF] Bernstein | Industrial-Strength Schema Matching[END_REF][START_REF] Dhamankar | imap: Discovering complex semantic matches between database schemas[END_REF]<->S2.dat [START_REF] Batini | A Comparitive Analysis of Methodologies for Database Schema Integration[END_REF][START_REF] Boukottaya | Schema matching for transforming structured documents[END_REF], S1.publisher [START_REF] Ehrig | QOM -Quick Ontology Mapping[END_REF][START_REF] Giunchiglia | S-Match: an Algorithm and an Implementation of Semantic Matching[END_REF]<->S2.pub [START_REF] Dhamankar | imap: Discovering complex semantic matches between database schemas[END_REF][START_REF] Ehrig | QOM -Quick Ontology Mapping[END_REF]) show that small size sub-trees reside at the elements of interest. The validation of of these proposed complex matchings is done by the ComplexMatchValidation algorithm given in Figure 7. For this purpose, the set of already acquired mini-taxonomies (using ExSTax method [START_REF] Saleem | Automatic extraction of structurally coherent mini-taxonomies[END_REF]) are considered. There are two sets of mini-taxonomies as shown in Figure 10. Set (a) presents the mini-taxonomy representing the date concept, which can be represented by date, dat or some other similar string, as the root node for the concept.

The leaf nodes collection of month, day, year, mm, yy represent attributes describing the concept. Within one instance of the mini-taxonomy, the presence of synonymous leaf nodes is not possible e.g. if month and mm are synonymous then the two nodes will not exist together in a mini-taxonomy with root node date or dat. The execution of the validation algorithm occurs for each of the four n:m propositions. In case of S1.books[0,15]<->S2.book [0,[START_REF] He | Discovering complex matchings across web query interfaces: a correlation mining approach[END_REF] and S1.library [START_REF] Aumueller | Schema and ontology matching with coma++[END_REF][START_REF] Do | Matching large schemas: Approaches and evaluation[END_REF]<->S2.writer [START_REF] Aumueller | Schema and ontology matching with coma++[END_REF][START_REF] Chi | Frequent subtree mining -an overview[END_REF], no minitaxonomy is found with root element similar to books or book and library or libinf o. As a result the two propositions are discarded and only 1:1 simple match is considered. Whereas in the other two cases the algorithm finds frequent mini-taxonomies in the form of date-month/day/year, datmm/yy, publisher-name/address and pub-nam/street/city 5 . The algorithm substantially authenticates the propositions and creates two more complex mappings as S1.(month [START_REF] Boukottaya | Schema matching for transforming structured documents[END_REF][START_REF] Boukottaya | Schema matching for transforming structured documents[END_REF], day [START_REF] Chi | Frequent subtree mining -an overview[END_REF][START_REF] Chi | Frequent subtree mining -an overview[END_REF], year [START_REF] Dhamankar | imap: Discovering complex semantic matches between database schemas[END_REF][START_REF] Dhamankar | imap: Discovering complex semantic matches between database schemas[END_REF])<->S2.(mm [START_REF] Bernstein | Industrial-Strength Schema Matching[END_REF][START_REF] Bernstein | Industrial-Strength Schema Matching[END_REF],yy [START_REF] Boukottaya | Schema matching for transforming structured documents[END_REF][START_REF] Boukottaya | Schema matching for transforming structured documents[END_REF]) and S1.(name [START_REF] Embley | Automatic direct and indirect schema mapping: Experiences and lessons learned[END_REF][START_REF] Embley | Automatic direct and indirect schema mapping: Experiences and lessons learned[END_REF], address [START_REF] Giunchiglia | S-Match: an Algorithm and an Implementation of Semantic Matching[END_REF][START_REF] Giunchiglia | S-Match: an Algorithm and an Implementation of Semantic Matching[END_REF])<->S2.(nam [START_REF] Do | Matching large schemas: Approaches and evaluation[END_REF][START_REF] Do | Matching large schemas: Approaches and evaluation[END_REF], street [START_REF] Doan | Learning to match ontologies on the Semantic Web[END_REF][START_REF] Doan | Learning to match ontologies on the Semantic Web[END_REF],city [START_REF] Ehrig | QOM -Quick Ontology Mapping[END_REF][START_REF] Ehrig | QOM -Quick Ontology Mapping[END_REF]). The final mappings are shown in Figure 11.

EVALUATION

The prototype implementation uses Java 5.0. A PC with Intel Xeon, 2.33 GHz processor and 2 GB RAM, running Win-5 -and / delimiters denote downward and upward traversal within the tree, respectively dows XP was used. We selected several data sets, BOOKS1, BOOKSEARCH 6 , JOBS, AUTO, AIRTRAVEL, REALESTATE and COURSES, as the input hierarchical structures for our experiments. Characteristics of these sets of schemas in given in Tab. 2.

A manual analysis of the above mentioned real domain schemas showed that there existed very limited possible sets of elements (set of leaf nodes representing some concept), which may participate in a complex map. Since such sets are rare, finding them as frequent mini-taxonomies is even more scarce. Following is a possible list of concepts against which n:m mappings may exist in the above schemas.

( To verify our CMPV method, we induced some of these sets of elements to several real schemas, to extract them as minitaxonomies. Our implementation showed the expected results, since the overall test scenarios have been synthetically generated.

Discussion

The idea of using mini-taxonomies works well, if their leaf nodes can represent some real complex match with a contextual map at ancestor level. And the ancestor level mapping is highly dependent on label matching. Working with real world schemas showed (i) the possibility of complex match is very limited, and (ii) the label matching framework should be exceptionall good.

Considering the first issue of complex match possibility, manual scrutiny of above mentioned schemas showed very limited number of n:m matches. For example in 20 schemas of AIRT RAV EL domain (with average of nodes per schema equal to 14), there were three concepts, passengers, return and depart, which could be considered for complex match. But the second issue of good label matching deficiency abates the matching process. For example, there existed 13 different labels for passenger concept in the domain, i.e., How many travelers are going, Number of passengers, NumAdults, adultsChildren, persons, adultnoChildno, passengers, number of travelers, how many people are going, num-pax, travelers, who is going on this trip, passengers-adults-num. Computing a high frequency of passengers concept (mini-taxonomies) existence was unaccomplishable because of the multi-word, cryptic labels also including homonyms.

Our idea has some similarity to Embley et al. [START_REF] Embley | Automatic direct and indirect schema mapping: Experiences and lessons learned[END_REF] work, which uses manually created concept ontology snippets for complex match discovery. Our approach tries to show that it can be done automatically in a scenario, where there is the availability of large number of domain schemas. Secondly using the ancestor level contextual map, the simple match results overcome the inverted parent-child match problem. Thus making the system more robust and dependable. Although the approach is similar to upward cotopy distance measure, but it is more flexible in execution. We do a top-down traversal during match process, i.e. parents are matched before children. Therefore, the nearest ancestor with an adequate match in the target schema is enough to verify the context.

CONCLUSION AND FUTURE WORK

In this paper, we have presented an automatic approach for discovering complex match. It is based on a tree mining technique supporting large size schema matching. It extends the tree mining data structure proposed in [START_REF] Zaki | Efficiently Mining Frequent Embedded Unordered Trees[END_REF] and exploites ancestor scope properties (integer logical operations) on schema nodes to enable fast calculation of contextual (hierarchical) similarity between them. It originality lies in the use of mini-taxonomies in complex match discovery. Mini-taxonomies are frequent subtrees within this forest of schema trees. Furthermore, our approach is implemented as a prototype and validated by experiments using different real schemas.

Firstly, the method computes simple element level matchings between two schemas. The algorithm linguistically matches nodes labels and ancestor level match existence (in ontology matching called upward cotopy distance) for this purpose. At this point, the matches have 1:1 cardinality, but our method also proposes the possible complex matches intrinsically. Our approach is based on the leaf or non-leaf status of the node, putting forward the match proposition that when a non-leaf node is matched to a non-leaf node, there is the probability of n:m match between the leaf nodes of the two non-leaf nodes. The algorithm CMPV certifies this proposition, indirectly utilising the collective intelligence of the domain users. This is achieved by using mini-taxonomies snippets, extracted from large number of input schemas developed and used over the specific domain by users.

The work presented in this paper has lots of prospective applications. Our approach can provide an automatic matching environment, supported by the collective intelligence of the domain users. In future, we plan to extend the label level matching techniques. We intend to utilize state of the art lexical matchers and linguistic dictionaries. Secondly, we will be extending the idea to evolving schemas matching in the large scale scenario. Finally, our aim is to fully incorporate our technique for web based interface forms (containing hierarchical nested fields) matching and collaboration among different metadata based virtual social environments.

Figure 1 :

 1 Figure 1: Two schemas with Node Scope values for each node.

Figure 2 :

 2 Figure 2: Architecture for complex matching discovery and validation using automatically generated mini-taxonomies.

9 d ← d + 1 10for each child of c do 11 nodeScope 12 end 13 Figure 3 : 1 x c .rightM ostN ode ← x r 2 if x c ¬ Root Node then 3 update(x c .parentN ode, x r ) 4 end 5 Figure 4 :

 911112133123454 Figure 3: Algorithm for schema tree node scope calculation, along with node depth.

Figure 5 :

 5 Figure 5: Algorithm for simple matching between two schemas.

Figure 6 :

 6 Figure 6: Input hierarchical structures with partial inverted node scenario.

Figure 8 :

 8 Figure 8: Two schema (trees) S1 and S2 for complex match discovery.

Figure 9 :

 9 Figure 9: Element level mappings between schemas S1 and S2 after execution of simple match algorithm; complex match proposition shown in brackets.

Figure 10 :

 10 Figure 10: Mini-taxonomies extracted from large input of books domain schemas, using ExSTax method for complex match validation.

Figure 11 :

 11 Figure 11: Mappings between schemas S1 and S2 after execution of complex match validation algorithm.

Example 2 (Partial Match): In

	source schema Name
	= 'John M. Brown', is partially matched to LastName =
	'Brown' and FirstName = 'John' in the target, because
	Name also contains the MiddleInitial = 'M'. •
	Example 3 (Label Equivalence): 'FirstName', tokenised
	as {first,name}, and 'NameFirst', tokenised as {name, first},
	are equivalent, with 100 % similarity.•

Example 4 (Synonymous Labels): 'WriterName

	', to-
	kenised as {writer,name}, and 'AuthorName', tokenised as
	{author, name} are equivalent (they represent the same con-
	cept), since 'writer' is a synonym of 'author'.•

Table 1 : A brief survey of schema matching techniques with local cardinality

 1

	Authors	Year Characteristics

  At the start of the recursive algorithm for node scope calculation, value of d is 0, depicting level 0 or root node level. It is incremented at L3.10, before the recursive call for next level (L3.12).

	Algorithm : NodeScope
	Data: p, c, V , d

p: parent node list element, c: current node, V : nodes list, d: node depth Result: V begin 1 x ← New nodesListElement(c) 2 x.number ← length(V ) 3 x.parentN ode ← p 4 x.rightM ostN ode ← ∅ 5 x.depth ← d 6 Add x to V 7 if c has no children then 8 update(x, x)

32 end 33

  ). Vt can have one or several (L5.11) candidate target nodes. Next step is the ancestor map existence check. The method returns a value α based on the ancestor node mapping and the proximity of the mapping node to the current node. If the target search space Vt has more than one node, method ancestorMap is executed

		Algorithm : SimpleMatch
		Data: V 1 , V 2 Lists of nodes of Schema 1 and 2
	1	L x Source list V 1 node label
	2	L xtl Set of labels of candidate nodes in target list V 2
	3	V t Set of candidate nodes in target list V 2
	4	xt Target node
	5	α Similarity Confidence
		β Match Type

6 begin 7 for each node x ∈ V 1 do 8 L x ← lab(x) 9 L xtl ← similarLabels(L x , V 2 ) 10 if L xtl ¬ ∅ then 11 V t ← VT(L xtl ) 12 α temp ← 0.0 13 α ← 0.0 14 for each node xt i ∈ V t do 15 α i ← ancestorMap(x, xt i ) 16 if α i > α temp then 17 α temp ← α i 18 α ← α i 19 xt ← xt i

20 if (Leaf(x)∧Leaf(xt)) then 21 β ← 11 22 else 23 if (¬Leaf(x)∧ ¬Leaf(xt)) then 24 β ← nn 25 else 26 if (Leaf(x)∧ ¬Leaf(xt)) then 27 β ← 1n 28 else 29 if (¬Leaf(x)∧ ¬Leaf(xt)) then 30 β ← n1 31 map(x,xt,β,α)

31 end 32 Figure 7: Algorithm for validation of complex matching between two schemas.

  Lists of nodes of schema 1 (source) and 2(target)MiniT ax : List of lists of mini-taxonomies Each mini-taxonomy list, mT ,V 1 and V 2 sorted on depth-first order sLeaf : Set of labels of leaf nodes of non-leaf node of V 1

	1
	2	tLeaf : Set of labels of leaf nodes of non-leaf node of V 2
	3	mT sLeaf , mT tLeaf : Sets of labels of leaf nodes of
	4	mini-taxonomy
	5	F s , F t : Boolean flags
	6	begin
	7	for each node x ∈ V 1 do
	8	F s ← false
	9	F t ← false
	10	if (¬Leaf(x) ∧ exists(map(x,xt,β,α)) ∧ β= nn) then
	11	// xt is non-leaf node in V 2
	12	sLeaf ← leafNodesLabels(x)
	13	tLeaf ← leafNodesLabels(xt)
	14	L x ← lab(x)
		L xt ← lab(xt)
	24
	25	if tLeaf ⊂ mT tLeaf then
	26	F t ← true
	27	if F s ∧ F t then
	28	break
	29	if F s ∧ F t then
	30	β ← nn
		map(leafNodes(x),leafNodes(xt),β)

15

for each mT ∈ MiniT ax do 16

L mT root ← lab(mT root) 17 // mT root is root node of mT 18 if (¬F s ∧ L mT root = L x ) then 19 mT sLeaf ← leafNodesLabels(L mT root ) 20 if sLeaf ⊂ mT sLeaf then 21 F s ← true 22 if (¬F t ∧ L mT root = L xt ) then 23 mT tLeaf ← leafNodesLabels(L mT root )

Table 2 : Characteristics of domain schema trees used in the mini-taxonomy computation experiments.

 2

	Domain	BOOKS1 BOOKSEARCH JOBS AUTO AIRTRAVEL REALESTATE COURSES
	Type	Synthetic	Real	Real	Real	Real	Real	Real
	Number of Schemas	176	19	20	14	20	14	42
	Average nodes per schema	8	6	5	5	14	9	8
	Largest schema size	14	12	8	10	21	20	17
	Smallest schema size	5	3	4	3	6	4	2
	Schema Tree Depth	3	2	2	2	2	2	4
	n:m match propositions	2	2	1	1	3	2	2

http://www.metaquerier.cs.uiuc.edu/repository/, http://www.cise.ufl.edu/project/thalia.html

In figure1, for each node [x,y], x denotes the depth-first traversal number and y denotes the last node number of subtree rooted at x.

-delimiter is used to show the downward traversal within the tree.

Lx.y refers to line y of algorithm in figurex

http://metaquerier.cs.uiuc.edu/repository