A (hopefully) friendly introduction to the complexity of polynomial matrix computations

Claude-Pierre Jeannerod INRIA -Laboratoire LIP, ENS de Lyon July 2003

Chief among the mathematical functions that symbolic computation aims to handle are those one can fully describe by integer matrices. Integer matrices are merely tables of whole numbers. The simplest example is the function which maps variable x to, say, 3 times x: here the associated matrix has a single entry, equal to number 3. On the other hand, real life applications such as cryptography often yield integer matrices with thousands of rows and columns and thus millions of entries. As arrays of numbers, matrices are particularly easy to store in a computer; as representations of the mathematical functions used for modelling, they encode the intrinsic properties of the underlying problem. Hence, among all the scientific problems that are to be solved by computers, many of them eventually reduce to matrix formulation.

Solving such problems requires that computers can combine matrices arithmetically, in the same way as solving simple algebraic equations such as 2x+3=4 is governed by combinations of whole numbers. So perhaps the easiest way to think about matrices in computer science is as a generalization of numbers: just like with numbers, what we can do with two matrices of the same sizethat is, the same number of rows and columns-includes addition, subtraction, multiplication and, sometimes, division. The result of any of these arithmetic operations is another matrix with the same size. Having more than one row and one column further allows for some matrix operations that do not exist for numbers: given a matrix, one may transform it into mathematically equivalent matrices whose all non-diagonal entries are equal to zero or whose entries are, in a sense, "as small as possible". We usually call these simplifying operations diagonalization and reduction, respectively. Other operations return some important mathematical characteristics of the matrix that are not immediately visible, like its volume (determinant) or a particular relation between its rows or its columns (linear system solving). Matrix computations usually refer to all to these operations when performed by a computer. It is worth noting at this stage that instead of numbers, matrices may often contain functions of one variable called polynomials: polynomials look very similar to whole numbers but are, perhaps surprisingly, easier to handle mathematically. In this case we say polynomial matrices and polynomial matrix computations. Now assume that you want your computer to perform one of these operations exactly for some large matrices. Before starting, a most legitimate and fundamental question is then "How hard is this computation?" Most of today's computers are "binary computers" and every computation ultimately reduces to a sequence of logical operations on zeros and ones called bit operations. So, by hardness or complexity of a computation, we mean an idea of the number of bit operations associated with this particular computation as a function of the input size: when doubling the size of the input matrix, will producing the exact result take roughly twice as long as before (linear complexity)? Or should this be expected to be four times slower (quadratic complexity) or eight times slower (cubic complexity) or even more? (We recall that 4 = 2 times 2 = 2 squared and that 8 = 2 times 2 times 2 = 2 cubed.)

In a sense, complexity indicates the intrinsic computational hardness of matrix operations, independently of solution methods (or algorithms) and software and hardware. For example, what is the complexity of adding two matrices of size n? Matrix addition is defined entry-wise: for each row and column, we add the two entries lying on the same row and column. Since the result is a matrix of size n whose all entries may differ from the input values, every addition algorithm requires at least n squared operations on whole numbers and the complexity of matrix addition is thus lower bounded by n squared. On the other hand, the definition of matrix addition yields an addition algorithm that costs no more than n squared additions of whole numbers and the complexity is upper bounded by n squared. The two bounds coincide and matrix addition has quadratic complexity.

Of course the same holds for matrix subtraction. But for every other operation, even the fastest known algorithms still yield upper bounds much different from output size-based lower bounds. In particular, evaluating the complexity of matrix multiplication alone seems to be a formidable task. Unlike addition, the classic definition of matrix multiplication yields an algorithm that costs n cubed operations on numbers of the same order of magnitude as the input numbers. This upper bound was improved for the first time in 1969 when Strassen discovered a product formula whose cost is about n to the power w with w strictly between 2 and 3. Since then, exponent w has been decreased to less than 2.39 but no method is known where w = 2. However, right after Strassen's breakthrough, multiplication became central to the understanding of the complexity of all other matrix operations: during the thirty years that followed, algorithms for performing matrix operations have been designed that rely only on matrix products (and on other a priori cheaper operations such as addition and subtraction). The reason for this approach is twofold: we get tighter upper bounds for the complexity of all matrix computations every time w is decreased; it may also give a way to relate complexities without having to know their exact value. For example, if the number of matrix products is "small" and if the magnitude of the size and of the entries of the matrices involved have the same order as those of the input then such computations are not essentially harder than matrix multiplication. Here by "small" we mean a function of the input matrix size n that grows extremely slowly as n increases. Such a function is called a polylogarithm.

Unfortunately, until last year, incorporating matrix multiplication typically meant too many products. Thus it was not known whether some matrix computations are reduceable to matrix multiplication. At ISSAC 2002, however, Storjohann showed that, for polynomial matrices, diagonalization, determinant computation and linear system solving are not essentially harder than matrix multiplication. He got his result by designing clever algorithms that return a provably correct answer while keeping the number of matrix products small enough. This breakthrough has opened up a new path in the study of how the complexities of matrix computations relate to each other. Are there other matrix operations that can be performed within roughly the same amount of time as matrix multiplication? Conversely, is matrix multiplication not essentially harder than some other operations?

This year, at ISSAC 2003, we shall give answers in both directions for polynomial matrices. First, we prove that reduction is not essentially harder than matrix multiplication by combining Storjohann's technique with Villard's earlier work on this particular operation. Then we show that the converse of one of Storjohann's results holds true: in fact, matrix multiplication is not essentially harder than computing the determinant. (This second result might be a little surprising at first sight since, as a volume, the determinant is a single number.)

Yet we are still far from a global view of the complexity of polynomial matrix computations, and even less is known in the more difficult case of integer matrices. In particular, are there operations other than computing the determinant that essentially have the same complexity as matrix multiplication? Are some of them-such as linear system solving-strictly easier? We don't know. On the other hand we do know of operations being much harder, such as dividing a matrix by another matrix. The result of matrix division is a matrix of the same size whose entries are in general not whole numbers but fractions like 2/5 or -7/3. Unfortunately the upper and lower parts of each of these n squared fractions usually have n times as many digits as the entries of the two matrix operands. The complexity of matrix division is thus lower bounded by n cubed which, as seen before, is itself lower bounded by the complexity of matrix multiplication. Hence another open problem is to design a division algorithm whose cost matches this cubic lower bound.

It is important to note that most of the above complexity results have been obtained via the design and analysis of concrete algorithms you can implement quite easily into any computer algebra system. How to make these algorithms practically fast in order to reflect the theory is thus another challenge for researchers in this field.

A. Storjohann. High-order lifting, Proceedings of ISSAC 2002. V. Strassen. Gaussian elimination is not optimal, Numer. Math. 13:4 (1969). G. Villard. Computing Popov and Hermite forms of polynomial matrices, Proceedings of ISSAC 1996.


P Kervella

A Mérand

M G Petr-Gotzens

T Pribulla

F Thévenin

The nearby eclipsing stellar system δ Velorum IV. Differential astrometry with VLT/NACO at the 100 microarcsecond level

Keywords: individual: (HD 74956, δ Vel), Stars: binaries: eclipsing, Methods: observational, Techniques: high angular resolution, Astrometry

Context. The stellar system δ Vel contains the brightest eclipsing binary in the southern sky (δ Vel A), and a nearby third star located ≈ 0.6 away (δ Vel B). The proximity of δ Vel B (usable as a reference) makes it a particularly well-suited target to detect the astrometric displacement of the center of light of the eclipsing pair. Aims. We obtained NACO astrometric observations with two goals: 1) to confirm the orientation of the orbital plane of the eclipsing pair on the sky determined by interferometry (Paper III), and 2) to demonstrate the capabilities of narrow-angle adaptive optics astrometry on a simple system with predictable astrometric properties. Methods. We measured the angular separation vector between the eclipsing binary δ Vel A and the visual companion δ Vel B from narrow-band images at 2.17 µm obtained with the VLT/NACO adaptive optics system. Based on these observations and our previous determination of the orbital parameters of the wide binary δ Vel A-B, we derived the apparent displacement of the center of light of the eclipsing pair at 11 epochs over its orbital cycle. Results. We detect the astrometric wobble of the center of light of the δ Vel A pair relative to B with a typical measurement precision of ≈ 50 µas per epoch, for a total amplitude of the measured displacement of ≈ 2 mas. Conclusions. The detected wobble is in relatively good agreement with the model we presented in Paper III, and confirms the orientation of the Aab orbital plane on the sky. The residual dispersion compared to our model is 110 µas rms, which we tentatively attribute to photometric variability of the fast rotating A-type components Aa and/or Ab in the Brγ line. Based on these results, we conclude that in favorable conditions (bright source with only two resolved components, small angular separation), narrow-angle astrometry with adaptive optics on an 8-meter class telescope can reach an accuracy of 50 to 100 µas.

Introduction

The bright southern star δ Vel (HD 74956, HIP 41913, GJ 321.3, GJ 9278) is a multiple system comprising at least three stars. Its brightest component, δ Vel A, was identified only in 2000 as one of the brightest eclipsing system in the sky (Otero et al. 2000). We consider here the two main components of the δ Vel system (Aa+Ab and B) as a test case to validate the potential of highprecision narrow-angle astrometry from the ground using adaptive optics. Exciting results were recently obtained using this observing technique, e.g., by Clarkson et al. (2012), Hußmann et al. (2012), and Kölher, Ratzka & Leinert (2012). These authors typically measured differential astrometry within a field of view of a few arcseconds to an accuracy of a few 100 µas (see e.g. Table 4 in Clarkson et al. 2012). We propose here to push this observing technique to its precision limits on δ Vel, which appears to be a particularly favorable target (bright and geometrically simple), in order to evaluate its potential.

Send offprint requests to: P. Kervella Based on observations made with ESO telescopes at the La Silla Paranal Observatory, under ESO programs 081.D-0109(A), 081.D-0109(B), 382.D-0065(A), and 282.D-5006(A).

In previous works on the δ Vel system, Kervella et al. (2009, Paper I) searched for infrared circumstellar excess in the inner δ Vel A-B system, whose present angular separation is approximately 0.6 . Part of the NACO data presented here was also used in this first article, although not for high-precision astrometry. Pribulla et al. (2011, Paper II) and Mérand et al. (2011, Paper III) obtained the orbital elements and fundamental parameters (including the parallax of the system) of the three components of the δ Vel system. In the present study, we take advantage of the well-constrained and accurate model of the system obtained in these previous works to predict the astrometric wobble of the center of light (hereafter CL) of the eclipsing system, and compare it with the measured NACO astrometry. We detail our observations and data analysis procedure in Sect. 2, and describe the method we used to derive the wobble of the CL of the eclipsing component in Sect. 3. We discuss in Sect. 4 the differences between the astrometric wobble predicted by the model and the observed displacement.

Observations and data reduction

Observing log and raw data processing

We observed δ Vel at 11 epochs in April-May 2008 and January 2009 using the Nasmyth Adaptive Optics System (NAOS, [START_REF] Rousset | Proc. SPIE[END_REF] of the Very Large Telescope (VLT), coupled to the CONICA infrared camera (Lenzen et al. 1998), which is abbreviated as NACO. These observations were obtained primarily to provide high-precision differential astrometry of the eclipsing system δ Vel A relative to B, following the promising demonstration by [START_REF] Seifahrt | Proc. 2007 ESO Instrument Calibration Workshop[END_REF]. We selected the smallest available pixel scale of 13 mas/pixel, giving a field of view of 13.6 ×13.6 . Because of the brightness of δ Vel, we employed a narrow-band filter1 at a wavelength of 2.166±0.023 µm (hereafter abbreviated as 2.17µm) together with a neutral density filter (labeled "ND2_short", that has a transmission of about 1.5%). The 2.17µm filter wavelength corresponds to the Brackett γ line of hydrogen. A detailed list of the NACO exposures obtained in 2008 is presented in Table 2 of Paper I. At each epoch 50 exposures were obtained, always centering component A on the same pixel of the CONICA detector array to mitigate the possible effects of field distorsion.

The raw images were processed in a standard way: dark subtraction, flat fielding, and cosmetics removal. We considered three approaches for the flat-field and dark-frame calibration: using specific dark and flat-field frames obtained separately for each night, using average flat/dark frames, and using median flat/dark frames (the last two computed over our 2008 observation epochs). For these different methods, the star positions extracted from the resulting data cubes are identical within 4 × 10 -3 pixels, or 50 µas. This figure is comparable to our statistical measurement uncertainties, and we conclude that we do not detect a significant astrometric variability induced by the flat field or dark. We therefore chose to use the median flat and dark frames over all observations. This remarkable stability is probably because NACO was kept cold and was not dismounted from the telescope over the period of our 2008 observations. Along this line, Neuhäuser et al. (2008) demonstrated that the plate scale of NACO is extremely stable (to < 5 × 10 -4 , in relative terms) over three years. The cosmetic corrections we applied concerned only pixels located outside of our astrometric windows (Sect. 2.2), as the areas used for each star position were specifically chosen to present no dead or hot pixels. They therefore had no influence on the astrometric measurements.

Star separation measurement

To measure the separation of the two star images on the NACO detector, we treated each image in our data cubes separately. We extracted two sub-images of 21 × 21 pixels centered on the positions of A and B (as shown in Fig. 1). We then used a classical χ2 minimization algorithm to shift and scale the sub-image of δ Vel A over the position of the fainter component B. Our choice of relatively small sub-windows prevents the contamination by the background noise that may present inhomogeneous patterns. We checked that the fit is not sensitive to the chosen size of the sub-windows over a large range of values. To achieve this fit, we computed a sub-pixel interpolation of the shifted image of A, using the Yorick 2 language, and more specifically using an interpolation routine in the Fourier space 3 . We derived four parame- ters: the relative shifts dx and dy in pixels between the two star images, the flux ratio ρ = f A / f B , and the uniform background level C. In order to estimate their associated error bars, we used the bootstrapping technique described in Appendix B of Kervella et al. (2004). We validated the Fourier interpolation method by comparing its results with a simple Gaussian fit of the two PSF cores that give the same relative positions (within 150 µas) although with larger dispersion due to the mismatch of the slightly seeing-distorted PSF and the Gaussian function. Thanks to their angular proximity, δ Vel A and B share the same residual optical aberrations from the adaptive optics system. Because it takes advantage of the similarity of their images, our fitting approach based on Fourier interpolation is particularly efficient.

For the conversion of the star separations measured in pixels to angular values, we adopted the pixel scale of 13.26 ± 0.03 mas/pixel [START_REF] Masciadri | [END_REF]. This value is in good agreement with the pixel scale obtained by Neuhäuser et al. (2008, 13.24 ± 0.06 mas/pix). Our differential astrometric measurements are affected only by the ±0.23% pixel scale uncertainty over the amplitude of the astrometric wobble of the CL of Aa-Ab and not over the full angular separation of A and B. As shown in Sect. 3, the astrometric wobble amplitude is less than 2 mas, and the corresponding ≈ 4 µas systematic error is therefore negligible compared to our statistical accuracy.

Differential atmospheric refraction

The angular separation of δ Vel A and B is only ≈ 0.6 for the epoch of our observations. Although this angle is quite small, the effect of differential atmospheric refraction is not negligible considering that the precision of our measurements (≈ 50 µas per epoch in right ascension and declination) corresponds to only ≈ 1/12 000 th of the separation of the two stars. Figure 2 shows schematically the effect of atmospheric refraction on the apparent positions of the two stars. In this diagram the sky positions of the two stars in the absence of atmosphere are labeled with the "vac" subscript, while the apparent positions measured from the ground are labeled "atm"; ϕ is the parallactic angle (positive after local celestial meridian crossing) at the time of the obser- vation; V atm and V vac are the vector separations of A and B with and without atmosphere, respectively; A and B are the apparent vector displacements of the position of the stars due to atmospheric refraction; and r is the resulting differential astrometry correction vector.

The quantity of interest for our purpose is the vector separation of the two stars V vac (∆α vac , ∆δ vac ). From a simple vectorial closure, the transformation between the measured differential astrometry vector on the sky V atm (∆α vac , ∆δ atm ) is

V vac = V atm + r, (1)
where r = A -B . We computed the values of | A | and | B | using the slaRefro routine from the Starlink library4 and the apparent positions of the two stars. The r = (∆α r , ∆δ r ) vector is always pointing towards zenith. This routine realizes an integration of the effect of the atmospheric crossing on the apparent direction of the incoming star light using a realistic atmospheric model [START_REF] Liebe | Propagation Modeling of Moist Air and Suspended Water/Ice Particles at Frequencies Below 1000 GHz[END_REF]. As input parameters, we used the actual conditions measured at Paranal for each observation epoch (airmass, pressure, temperature, humidity, etc.). Further details on this routine can be found in Gubler & Tytler (1998). The right ascension and declination corrections to add to the measured NACO differential astrometry of B relative to A are

∆α r = |r| sin ϕ, ∆δ r = |r| cos ϕ. (2)
For an additional discussion of the effects of atmospheric refraction on adaptive optics observations, the interested reader is referred to Roe (2002) and Helminiak (2008).

Apparent astrometric displacement of δ Vel A

The measured relative separations between δ Vel A and B, corrected for differential atmospheric refraction, are listed in Table 1. The photometric flux ratio of the two stars is presented in Table 2. The orbital phases of the measurements with respect to the eclipsing binary Aab were computed using the following parameters from Paper II (ROCHE model): T 0 (HJD) = 2452528.950 (epoch of periastron passage) and P = 45.15023 d.

The observed displacement of the CL of Aa-Ab relative to B results from the vectorial sum of the orbital motion of B on its 142-year orbit, and the displacement of the CL of the eclipsing binary system over its ≈ 45-day orbital cycle. In order to measure this second component only, the secular orbital displacement of δ Vel B relative to A must be subtracted from the measured differential astrometry.

In Paper III Mérand et al. (2011) determined the orbital elements of the δ Vel A-B system. We used these parameters to estimate the relative positions of the center of mass of δ Vel A and B at each observation epoch, and subtracted the resulting vectors from our NACO astrometric measurements. The evolution of the measured astrometric position of δ Vel B relative to A as a function of time (over more than a century) is presented in Table 3. The model positions for the different epochs are also listed, with the residuals compared to the observations. Because of uncertainties in the determination of the orbital parameters of the A-B system, we added a constant astrometric shift (∆α = -0.3 mas, ∆δ = 0 mas) to our CL displacement model to match the measured CL positions. To determine this constant shift, we minimized the dispersion of the 2008 measurements with respect to the model. We needed this correction, as our NACO measurements have a limited absolute accuracy caused by the plate scale uncertainty (≈ 2 × 10 -3 ). For the 0.6 separation of δ Vel A and B, this systematic uncertainty is ≈ 1 mas and it does not average out with the number of measurements. We obtained a residual rms dispersion of the NACO measurement points of 110 µas compared to our model (excluding the 2008 May 05, 2008 May 07, and 2009 Jan 07 epochs, see Sect. 4.1).

The measured astrometric wobble of the CL of the eclipsing system is presented in Fig. 4 and the corresponding numerical values are listed in Table 4. Another view of this apparent displacement, including a plot of the differential photometry of δ Vel A-B, is shown in Fig. 5. In these two figures, the prediction from the physical model of the eclipsing pair presented in Paper III is also shown for reference. The derived orientation of the orbital plane of the eclipsing pair is consistent with the interferometric measurements reported in Paper III. The observed amplitude of the CL displacement is also in satisfactory agreement with the predicted value (≈ 2 mas).

It is interesting to note that at the phases of the eclipses in the model curves, the CL of Aab moves over small arcs because of the slight inclination of the orbital plane on the line of sight and also because of the inhomogeneous light distribution on the apparent disks of the two stars (they are both relatively fast rotators and therefore show some gravity darkening). The amplitude of Notes. φ is the orbital phase of the system (relative to periastron passage), θ the DIMM seeing in arcseconds (in the visible), AM the airmass, and ∆α r and ∆δ r the corrections for the differential atmospheric refraction (see Sect. 2.3 for details). The listed differential astrometry [α B -α A ] and [δ B -δ A ] include the atmospheric refraction correction. The angles are all expressed in milliarcseconds. this effect is too small, however, to be detectable in our NACO measurements.

Discussion

Inconsistent NACO measurements

The overall agreement between our NACO astrometric measurements and the model of the eclipsing pair is satisfactory. However, three of our measurement points show a significant departure from the expected CL trajectory, at epochs 2008 May 05, 2008 May 07, and 2009 Jan 07.

For our 2009 epoch, the observed discrepancy is most probably due to the combination of two causes. The first is the instability of the field orientation of NACO over a period of more than 7 months. From the analysis of archival NACO reference astrometric fields, G. Chauvin (private communication) observed that a shift of 0.30±0.03 deg in the true North orientation occured between April and August 2008. We identified an intervention on the instrument in early July 2008 that explains the observed shift (although it does not affect our April-May data). Other actions took place on the instrument later in 2008, that possibly modified or removed part of this rotation shift. The second cause is that the true accuracy of the orbital trajectory of B in our model (Fig. 3) is limited by the accumulation of errors with time. Because of the uncertainties on the A-B orbital parameters, it is practically impossible to relate our 2009 measurement unequivocally to the 2008 epochs at a level of a few 10 µas. We therefore excluded the isolated 2009 epoch from the present astrometric analysis.

For the two epochs in early May 2008, however it is more difficult to reach a solid conclusion on the origin of the deviation. We considered the following possible explanations:

• Atmospheric or instrumental effect. We checked the different observational parameters of all the observations, either environmental (seeing conditions, airmass, etc.) or instrumental (flat or bias properties, etc.), but we could not find a significant particularity of the data collected over these two nights. The observed deviation was present over two nights separated by only two days, and was not present before or after these two nights. Although a peculiar instrumental bias cannot be formally excluded, this points to an astrophysical origin.

• Transit of a dark body (exoplanet or faint star). The geometry of the δ Vel A-B eclipsing system makes it a favorable configuration for the transit of dark bodies in front of the stars of the eclipsing pair. The existence of these systems was predicted by [START_REF] Schneider | [END_REF], and recently demonstrated by Armstrong et al. (2012). A search for transit signatures in the photometry 3. measured with SMEI (Fig. 6) did not give positive results down to about 2% of the total Aa+Ab+B flux. There is still a possibility that a very shallow transit of 1-2% of the total flux may be present (≈ 4 -5% of the flux of one of the main components Aa or Ab), but it would be insufficient to explain the observed astrometric signal. So the transit of a dark component in front of one of the stars appears unlikely.

• Activity of δ Vel Aa and/or Ab in the Brγ line. The NACO images were taken with a narrow-band Brγ filter. It is therefore possible that episodic mass loss created a temporary envelope and circumstellar emission around one of the two eclipsing stars. An emission of this kind could be faint in the broad-band photometry of the system (SMEI data), but would be much more apparent in our narrow-band Brγ filter. This would affect our astrometric measurements by displacing the CL of the eclipsing system towards the star experiencing the circumstellar emission.

According to our model of the system (Paper III), the expected Brγ flux ratio between δ Vel A and B is 10.67. We measure a median value of f (A)/ f (B) = 10.37 ± 0.13 over all our observations (Table 2), which is slightly below the model, but could be explained by interstellar extinction. It should be noted that the flux ratio values observed on 2008-05-05 and 05-07 are both lower than the median value (10.27 to 10.30). Moreover, the observed dispersion of the measurement points (≈ 0.13) is much larger than the uncertainty of the measurements (≈ 0.01). This means that either Aa, Ab, or B experiences photometric variability in the Brγ line. The SMEI photometry presented in Fig. 6 also shows a possible variability at a 2-3% level. If we consider only the case of a change in brightness of one of the eclipsing stars (a change in the flux of B would have no effect on the astrometry), a 1% change in total flux means a ≈ 2% change in the relative brightness of δ Vel Aa and Ab. This change in flux would result in a geometrical shift of the CL of the system of approximately 300 µas when the stars are at maximum elongation (separation ≈ 16 mas). This amplitude is similar to the observed drift of the CL on 2008 May 05 and 2008 May 07. However, the fact that we have only the relative photometry of A and B at high precision means that we cannot exclude a change in the brightness of B that would invalidate this hypothesis.

• Binarity of δ Vel B. The presence of an undetected companion around B would cause a displacement of the photocenter of this component, and thus affect the differential A-B astrometry. The mass of the companion of B would have to be relatively high, and its orbital period short, but we cannot formally exclude Top: Apparent displacement of the center of light of the δ Vel Aab eclipsing pair relative to B as a function of the orbital phase (the secular displacement of B has been subtracted). The two discrepant measurements around φ = 0.7 are discussed in Sect. 4.1. Bottom: Ratio of the photometric fluxes of δ Vel A and B in the NACO narrowband 2.17 µm filter (Table 2), normalized to the median measured ratio (10.372). For both plots, the solid curves are the predictions of the model presented in Paper III, and not the result of a fit to the data. this possibility. As suggested in Paper II, spatially resolved spectroscopy of δ Vel B would be necessary to check this hypothesis, as well as to confirm the physical properties of this star. In summary, the most likely explanations for the inconsistent astrometric measurements of 2008 May 05 and 2008 May 07 are either an unidentified instrumental bias, or a transient activity of one of the fast rotating Aa or Ab stars in the Brγ hydrogen line (e.g. the temporary formation or disappearance of a disk contributing ≈ 1 -2% of the flux in the Brγ line). The sensitivity of our differential astrometric measurements to the flux ratio of Aa and Ab introduces an additive noise on the measurement of the Aab CL displacement. Although the formal accuracy of each individual astrometric measurement is unaffected, the level of agreement with the CL displacement predicted by our model (that assumes non-variable stars) is reduced.

Astrometric accuracy

The dispersion of our NACO astrometric measurements around our model of the system (110 µas rms, excluding the 2008 May 05 and 2008 May 07 epochs, see Fig. 4) is larger than our individual measurement uncertainty (≈ 50 µas per epoch). We therefore estimate that the true accuracy of a single measurement epoch is most probably between 50 and 100 µas. This level of accuracy is consistent with the conclusions of Fritz et al. (2010). This confirms that very high-precision astrometric observations are feasible from the ground with adaptive optics systems on large telescopes. The measurements we presented were obtained on a particularly favorable object, very bright and with only two unresolved objects in the field of view. However, the detected astrometric displacement is particularly subtle, and the fact that we could retrieve the orientation of the orbital plane of the eclipsing pair demonstrates the potential of this technique.

One should also note that we used a neutral density filter and a narrow band filter to prevent the saturation of the CONICA detector. This means that the level of accuracy we demonstrated is directly applicable to significantly fainter targets than δ Vel (probably by at least 10 magnitudes). For even fainter objects (m K > 14), particularly in the Galactic Center region, a detailed discussion is presented by Fritz et al. (2010).

Conclusion

We reported high precision differential astrometric measurements of the triple system δ Vel. They show that it is possible to measure the separation of close binaries of suitable brightness with a repeatable precision of 50 to 100 µas. The comparison of the measured astrometric displacement of the CL of the eclipsing component of δ Vel with a well-constrained model of the system shows that our NACO measurements give a realistic astrometric signal, in terms of amplitude and orientation on the sky. However, this qualitatively good agreement is affected by what we interpret as photometric variability of one of the components of the eclipsing binary (although other explanations are also possible).

High accuracy astrometric measurements have the potential to bring novel constraints in several fields of astrophysics, from the Galactic center (e.g. [START_REF] Gillessen | [END_REF], to faint companion detection (e.g. Tokovinin et al. 2012), or cluster dynamics (e.g. Clarkson et al. 2012;Hußmann et al. 2012). The future instrumentation of extremely large telescopes (see e.g. Trippe et al. 2010) will give access to much fainter objects, although the actual measurement accuracy will probably not be improved significantly beyond the 50 µas limit. The next generation interferometric instrumentation at near-infrared wavelengths, particularly the GRAVITY [START_REF] Gillessen | Proc. SPIE[END_REF]Eisenhauer et al. 2011;Vincent et al. 2011) and ASTRA (Woillez et al. 2012;[START_REF] Stone | [END_REF] instruments, are expected to overcome this limit, down to an accuracy of 10 to 20 µas over a field of view of a few arcseconds.

A&A-DelVel4-Astrom-v3r1, Online Material p 8 Table 3. Observed and model positions of δ Vel B relative to A for the epochs presented in Fig. 3 (see also Argyle et al. 2002)

Fig. 1 .

 1 Fig. 1. Average image of δ Vel obtained on 2008 Apr 01, together with the 21 × 21 pix astrometric windows that we used for the differential astrometry (white squares).

Fig. 2 .

 2 Fig. 2. Geometrical effect of the atmospheric refraction on the differential astrometry of a binary star (see Sect. 2.3 for details).

Fig. 3 .

 3 Fig. 3. Relative orbit of δ Vel B around δ Vel A. The trajectory computed using the orbital elements determined in Paper III is represented as a black ellipse, and the measurements corresponding to our NACO and VISIR astrometry are shown in the enlarged insert box. The axes are labeled in arcseconds, and the numerical values of the positions are listed in Table3.

NACOFig. 4 .

 4 photocenter displacement λ ∼2.20µm NACO

  Fig. 5.Top: Apparent displacement of the center of light of the δ Vel Aab eclipsing pair relative to B as a function of the orbital phase (the secular displacement of B has been subtracted). The two discrepant measurements around φ = 0.7 are discussed in Sect. 4.1. Bottom: Ratio of the photometric fluxes of δ Vel A and B in the NACO narrowband 2.17 µm filter (Table2), normalized to the median measured ratio (10.372). For both plots, the solid curves are the predictions of the model presented in Paper III, and not the result of a fit to the data.

Fig. 6 .

 6 Fig.6. Total flux of the δ Vel A-B system as a function of the phase from SMEI observations, excluding the eclipses, normalized to its average over the observation period.

Table 1 .

 1 Differential astrometry of δ Vel derived from the NACO images. B -α A ] ± σ stat [δ B -δ A ] ± σ stat -54 000 -2 454 000 2008 Apr 01 557.0224 557.5245 0.9294 0.77 1.16 -0.014

	UT date	MJD	HJD	φ	θ	AM	∆α r	∆δ r	[α

Table 4 .

 4 Astrometric displacement of the center-of-light (CL) of δ Vel A.

	UT date	MJD	φ	Model A-B	Model CL	Observ. CL	Nσ
		-54 000		vector	displacement	displacement

  . -0.4301 ± 0.001 -0.42986 0.4520 ± 0.001 0.45209 -0.00019 -0.00012 54580.9917 -0.4300 ± 0.001 -0.42984 0.4512 ± 0.001 0.45157 -0.00013 -0.00042 54591.9748 -0.4290 ± 0.001 -0.42972 0.4485 ± 0.001 0.44863 0.00073 -0.00010 54593.9732 -0.4294 ± 0.001 -0.42969 0.4481 ± 0.001 0.44809 0.00030 -0.00004 54604.0442 -0.4296 ± 0.001 -0.42958 0.4455 ± 0.001 0.44540 -0.00005 0.00010 54838.1347 -0.4246 ± 0.001 -0.42611 0.3813 ± 0.001 0.38198 0.00155 -0.00070Notes. All angles are expressed in arcseconds. The model positions were computed using the orbital elements in Paper III.

	MJD	obs(α) model(α)	obs(δ) model(δ)	∆α	∆δ
	13467.7500	0.11 ± 0.2	0.29308	-2.26 ± 0.2 -2.12963 -0.17874 -0.12748
	15100.3000	0.22 ± 0.2	0.40581	-2.30 ± 0.2 -2.33885 -0.18842	0.03910
	18104.7000	0.48 ± 0.2	0.59401	-2.86 ± 0.2 -2.61761 -0.11537 -0.24262
	19753.3600	0.69 ± 0.1	0.68520	-2.63 ± 0.1 -2.71535	0.00502	0.08438
	21553.8500	0.81 ± 0.1	0.77407	-2.89 ± 0.1 -2.77964	0.03269 -0.10985
	24132.7000	0.95 ± 0.1	0.88042	-2.88 ± 0.1 -2.79750	0.06595 -0.08092
	25568.0800	0.85 ± 0.1	0.92825	-2.67 ± 0.1 -2.77070 -0.07696	0.10325
	27996.4500	1.02 ± 0.1	0.98936	-2.74 ± 0.1 -2.66705	0.03325 -0.06803
	31481.5500	0.97 ± 0.1	1.02966	-2.32 ± 0.1 -2.39249 -0.06104	0.07692
	34342.1300	0.99 ± 0.1	1.01591	-1.99 ± 0.1 -2.05765 -0.02202	0.06694
	34418.8800	0.92 ± 0.1	1.01491	-2.00 ± 0.1 -2.04731 -0.09296	0.05202
	34378.0000	0.96 ± 0.1	1.01545	-1.99 ± 0.1 -2.05283 -0.05359	0.06313
	43828.7000	0.565 ± 0.01	0.57324	-0.277 ± 0.01 -0.27270 -0.00838 -0.00402
	43862.7000	0.567 ± 0.01	0.57025	-0.262 ± 0.01 -0.26477 -0.00289	0.00261
	48074.5000	0.116 ± 0.01	0.10948	0.716 ± 0.01	0.69105	0.00643	0.02462
	48476.0000	0.058 ± 0.01	0.05763	0.755 ± 0.01	0.76601	0.00045 -0.01124
	48805.0000	0.008 ± 0.01	0.01475	0.774 ± 0.01	0.82238 -0.00664 -0.04842
	51464.4300 -0.2886 ± 0.005 -0.30349 1.0200 ± 0.005	1.00667	0.01487	0.01328
	54581.5100 -0.4259 ± 0.001 -0.42983 0.4541 ± 0.001	0.45143	0.00391	0.00262
	54557.0224 -0.4306 ± 0.001 -0.43010 0.4578 ± 0.001	0.45796 -0.00053 -0.00021
	54560.9976 -0.4307 ± 0.001 -0.43005 0.4571 ± 0.001	0.45690 -0.00068	0.00020
	54562.0121 -0.4309 ± 0.001 -0.43004 0.4570 ± 0.001	0.45663 -0.00082	0.00033
	54563.0048 -0.4308 ± 0.001 -0.43003 0.4569 ± 0.001	0.45637 -0.00073	0.00051
	54576.9715 -0.4303 ± 0.001 -0.42988 0.4528 ± 0.001	0.45264 -0.00044	0.00013
	54579.0231

http://www.eso.org/sci/facilities/paranal/instruments/naco/

http://yorick.sourceforge.net/

fft_fine_shift function of the fft_utils.i package

http://starlink.jach.hawaii.edu/ Table 2. Photometric flux ratio f (A)/ f (B) between A and B in the NACO 2.17 µm narrow-band filter. UT date MJD φ f (A)/ f (B) -54 000 2008 Apr 01

557.0224 0.9294 10.547 ± 0.009 2008 Apr 04 560.9976 0.0175 10.413 ± 0.012 2008 Apr 06 562.0121 0.0400 10.426 ± 0.008 2008 Apr 07 563.0048 0.0619 10.332 ± 0.007 2008 Apr 20 576.9715 0.3713 10.469 ± 0.008 2008 Apr 23 579.0231 0.4167 10.147 ± 0.012 2008 Apr 24 580.9917 0.4603 10.589 ± 0.011 2008 May 05 591.9748 0.7036 10.295 ± 0.011 2008 May 07 593.9732 0.7478 10.269 ± 0.011 2008 May 18 604.0442 0.9709 6.993 ± 0.009 2009 Jan 07 838.1347 0.1556 10.385 ± 0.022 Notes. The 2008 May 18 epoch corresponds to the primary eclipse.

 457.959 +0.195, ±0.039 , -0.140 ±0.043 10 2008 Apr 04 560.9976 0.0175 -430.355, 456.900 -0.117, +0.278 -0.314 ±0.043 , +0.170 ±0.055 4 2008 Apr 06 562.0121 0.0400 -430.344, 456.630 -0.191, +0.434 -0.484 ±0.028 , +0.416 ±0.037 8 2008 Apr 07 563.0048 0.0619 -430.334, 456.365 -0.255, +0.566 -0.390 ±0.028 , +0.610 ±0.038 4 2008 Apr 20 576.9715 0.3713 -430.183, 452.639 -0.117, +0.201 -0.084 ±0.035 , +0.226 ±0.039 1 2008 Apr 23 579.0231 0.4167 -430.160, 452.091 -0.051, -0.009 -0.196 ±0.030 , -0.117 ±0.033 8 2008 Apr 24 580.9917 0.4603 -430.139, 451.565 +0.070, -0.201 +0.349 ±0.042 , -0.475 ±0.056 7 2008 May 05 591.9748 0.7036 -430.015, 448.627 +0.449, -0.984 +1.127 ±0.046 , +0.087 ±0.042 28 2008 May 07 593.9732 0.7478 -429.992, 448.093 +0.464, -1.006 +0.758 ±0.036 , -0.134 ±0.033 26 2008 May 18 604.0442 0.9709 -429.876, 445.399 +0.052, -0.082 -0.272 ±0.055 , +0.039 ±0.051 5Notes. "Model A-B vector" is the predicted astrometric separation ([α B -α A ], [δ B -δ A ]) of the centers of light of A and B (with a shift of ∆α = -0.3 mas, see Sect. 3). The shift of the center of light of Aab relative to its center of mass is listed in the column "Model CL displacement". The observed Aab center of light displacement ("Observ. CL displacement") and the distance between the observed positions and the model positions in number of standard deviations (Nσ) are also listed. All angular values are expressed in milliarcseconds.

Acknowledgements. We thank the La Silla Paranal Observatory team for the successful execution of the NACO observations of δ Vel. The visual binary orbit fitting procedures we used were created by Dr Pascal Bordé. We thank

P. Kervella et al.: Differential astrometry of δ Velorum with VLT/NACO Drs Gaël Chauvin and Julien Girard for their help in characterizing the stability of the astrometric calibration of NACO. This work received the support of PHASE, the high angular resolution partnership between ONERA, Observatoire de Paris, CNRS and University Denis Diderot Paris 7. This work was supported by the Slovak Research and Development Agency under the contract No. APVV-0158-11, and partially supported by the VEGA 2/0094/11 project. This research took advantage of the SIMBAD and VIZIER databases at the CDS, Strasbourg (France), and NASA's Astrophysics Data System Bibliographic Services.


Jérôme David

Jérôme Euzenat
email: jerome.david|euzenat@inrialpes.fr

Comparison between ontology distances (preliminary results)

There are many reasons for measuring a distance between ontologies. In particular, it is useful to know quickly if two ontologies are close or remote before deciding to match them. To that extent, a distance between ontologies must be quickly computable. We present constraints applying to such measures and several possible ontology distances. Then we evaluate experimentally some of them in order to assess their accuracy and speed.

Motivations

The semantic web aims at exploiting formal knowledge at the world scale. It is, in particular, based on ontologies: a structure defining concepts used to represent knowledge and their relationships. These concepts are used for specifying semantic web services, annotating web resources (pictures, web pages, music) or for describing data flows.

It is however likely that different information sources will use different ontologies. It is thus necessary to find correspondences between ontologies in order to communicate from one ontology to another. Finding correspondences is called matching ontologies and the resulting set of correspondences is called an alignment [START_REF] Euzenat | Ontology matching[END_REF].

Together with matching ontologies, there are many occasions where it is useful to know if two ontologies are close to each others or not, or what is the closest ontology to another one. In particular, -when one wants to find the community of people with whom she will be more likely to communicate easily, finding if they use similar ontologies can be useful information [Jung and Euzenat, 2007]; This can also help identifying communities in social networks [Jung et al., 2007]; -in semantic peer-to-peer systems, it will be easier to find information if queries can be sent to nodes using similar ontologies because query transformation will miss less information [START_REF] Ehrig | Similarity for ontologies -a comprehensive framework[END_REF]; -in ontology engineering, it is useful to find similar ontologies that can be easily used in conjunction with other ones. For example, when developing an ontology for radiological diagnoses, it would be useful to find anatomy and pathology ontologies that can be used with each other;

-when modularising large ontologies into smaller parts [START_REF] Stuckenschmidt | Structure-based partitioning of large concept hierarchies[END_REF], it is useful to consider the module candidates as sub-ontologies which will be more prone to be separated as they are distant to each others; -in semantic search engines which return ontologies corresponding to a query [d'Aquin et al., 2007], it would be useful to introduce a "Find similar ontologies" button. Distances can also be used in this case for ordering answers to such a query (ontology ranking, [START_REF] Alani | Ontology ranking based on the analysis of concept structures[END_REF]) with regard to ontology proximity; -in some ontology matching algorithms [START_REF] Gracia | Solving semantic ambiguity to improve semantic web based ontology matching[END_REF] when one wants to use an intermediate ontology between two ontologies, it may be useful to select the closest ontology.

In these various applications, there are different requirements for an ontology distance measure. In particular, there is always a trade-off between speed and accuracy. We will review some of these possible measures and propose a first evaluation of their qualities. The remainder of this paper is as follows: we first present and discuss previous work. Then, after recalling general definitions about distance measures, we introduce constraints applying to distances between ontologies. The next section introduces some ontology distances. Finally, we evaluate these measures and with regard to the criteria.

Related works

Most of the work dealing with ontology distance [START_REF] Mädche | Measuring similarity between ontologies[END_REF][START_REF] Hu | Semantic metrics[END_REF][START_REF] Vrandečić | How to design better ontology metrics[END_REF] is in reality concerned with concept distances. Such measures are widely used in ontology matching algorithms [START_REF] Euzenat | Ontology matching[END_REF]. They are quickly extended to ontologies without discussing the different ways to achieve this.

[ [START_REF] Mädche | Measuring similarity between ontologies[END_REF] introduced a concept similarity based on terminological and structural aspects of ontologies. This very precise proposal combines an edit distance on strings and a structural distance on hierarchies (the cotopic distance). The ontology similarity strongly relies on the terminological similarity. This paper evaluates the ontology design process, but not ontology similarity.

The framework presented in [START_REF] Ehrig | Similarity for ontologies -a comprehensive framework[END_REF] aims at comparing concepts across ontologies instead of ontologies themselves. It provides a similarity combining string similarity, concept similarity -considered as sets -and similarity across usage traces.

There is also a quite elaborate framework in [START_REF] Hu | Semantic metrics[END_REF]. This paper is mostly dedicated to the comparison of concepts but can be extended to ontologies. First, concepts are expanded so they are expressed in term of primitive concepts. Each concept is expressed as a disjunction of compound but conjunctive concepts. This works as long as no cycle occurs in the ontology. Then primitive concepts are considered as dimensions in a vector space and each concept is represented in this space. The weights used in this vector space are computed with TF•IDF. The distance between two concepts is the smallest cosine distance between vectors associated with disjuncts describing concepts. The way this is extended to ontology concepts is not clearly explained but the methods that will be explained in §4.3 would work.

Finally, [START_REF] Vrandečić | How to design better ontology metrics[END_REF] more directly considered metrics evaluating ontology quality. This is nevertheless one step towards semantic measures since they introduce normal forms for ontologies which could be used for developing syntactically neutral measures.

A general comment about these works is that they rely of elaborate distance or similarity measures between concepts and they extend these measures to distance between ontologies. This extension is often considered as straightforward. However, they have barely been evaluated. This is what we attempt to do here.

Distances properties

In this section, we first introduce the ontology model which we used and then review the general properties that distances between ontologies must satisfy.

Ontology model

All measure will be based on a set of ontologies O which we refer to as the ontology space. For simplification purposes, an OWL ontology o ∈ O is represented as a set of named entities E o . These entities can be classes (C), properties (P ) or individuals (I): E = C ∪ P ∪ I. Each entity is identified by a URI thanks to the function uri : E -→ U RI. The function l ln : E -→ String returns the local name of the entity which is the specific part of the entity URI in the ontology. Each entity can be also described by annotations, i.e., labels, comments. The function l annot : E -→ P(String) assigns a set of annotations to each entity.

Algebraic distance properties

A dissimilarity is a real positive function d of two ontologies which is as large as ontologies differ.

Definition 1 (Dissimilarity). Given a set O of ontologies, a dissimilarity δ : O × O → R is a function from a pair of ontologies to a real number such that:

∀o, o ∈ O, δ(o, o ) ≥ 0 (non-negativeness) ∀o ∈ O, δ(o, o) = 0 (minimality) ∀o, o ∈ O, δ(o, o ) = δ(o , o) (symmetry)
Some authors consider a 'non symmetric (dis)similarity', [START_REF] Tverski | Features of similarity[END_REF]; we then use the term non symmetric measure or pre-similarity. There are more constraining notions of dissimilarity, such as distances and ultrametrics.

Definition 2 (Distance). A distance (or metric) δ : O × O → R is a dissimilarity function satisfying the definiteness and triangular inequality:

∀o, o ∈ O, δ(o, o ) = 0 if and only if o = o (definiteness) ∀o, o , o ∈ O, δ(o, o ) + δ(o , o ) ≥ δ(o, o ) (triangular inequality)
There are in fact many reasons why an ontology measure may not be a distance. In particular, if we want to consider the semantics of ontologies, a sheer semantic measure should be 0 when the two arguments are semantically equivalent, even if they are not the same. For the sake of finding a distance, we must work in the quotient space in which the congruence relation is semantic equivalence. However, given the cost of computing semantic equivalence we will try to avoid that.

We will see below that there are good reasons to avoid symmetry as well.

Very often, the measures are normalised, especially if the dissimilarity of different kinds of entities must be compared. Reducing each value to the same scale in proportion to the size of the considered space is the common way to normalise.

Definition 3 (Normalised measure). A measure is said to be normalised if it ranges over the unit interval of real numbers [0 1]. A normalised version of a measure δ is denoted as δ.

In the remainder, we will consider mostly normalised measures and assume that a dissimilarity function between two entities returns a real number between 0 and 1.

Application-specific distance properties

One could imagine some properties which are unrelated to the general notion of distance but are specific to its use. In addition to algebraic properties, we would like to express purpose-oriented constraints on the measure. Such constraints must ask that the smaller the distance, -the faster it is to provide an alignment; -the more entities correspond to entities of the other ontology; -the more entities of the other ontology correspond to entities of this ontology; -the closest are corresponding entities; -the easier (the faster) it is to answer queries; -. . . For example, we could take into account a property stating that the addition of specific information in one ontology implies an increase of the distance value:

∀o, o , o ∈ O, o ∩ o = ∅ ⇒ δ(o, o ) ≤ δ(o, o ∪ o )
Contrarily, the addition of information issued from the other ontology implies a decrease of the distance value:

∀o, o , o ∈ O, o ⊆ o -o , ⇒ δ(o, o ∪ o ) ≤ δ(o, o )
These first properties show that more ontologies share concepts, lesser is their distance. Nevertheless, they are useful only if we consider ontologies having entities which match perfectly. In concrete cases, the ontologies are sufficiently heterogeneous and consequently, this property cannot be satisfied.

When only two ontologies are available, ontology distances have to be computed by comparing them. On the basis of such measures, systems will decide between which ontologies to run a matching algorithm. They can measure the ease of producing an alignment (expected speed, expected quality). So naturally, one constraint is that the distance be computed faster than the actual alignment.

There are many possible ways to define a distance between ontologies. First of all, an ontology can be just viewed as a bag of terms. This approach is similar to those used in information retrieval based on the vector space model. These techniques relies on vector representations of ontologies and use distances measures between these vectors.

Another approach is to consider an ontology as a set of entities. These entities will depend on the techniques used for establishing the distance: they will generally be the classes or properties to be found within the ontologies. In this case, defining a distance between the ontologies will very often rely on:

-a distance (δ) or similarity (sim) measure between entities; -a collection distance (∆) which will use the distance between entities for computing a distance between ontologies.

We first present ontology distances based on the vector space model. Then, we consider some distances between entities before presenting various kinds of collection distances.

Ontology distances based on the vector space model

A distance can be computed by comparing the sets of labels appearing in both ontologies and using a measure such as the Hamming distance, i.e., the complement to 1 of the ratio of common terms over the whole set of terms used by any of the ontologies. This distance would certainly run faster than any serious matching algorithm but does not tell a lot about the matching process. However, more elaborate measures based on the vector space model (VSM) have been designed.

In the VSM, each ontology is represented by a vector of terms. These terms are extracted from the annotations of the ontology entities. The set of terms T o contained in an ontology o is build with the help of a term extraction function l te :

T o = e∈Eo l te l annot (e) ∪ l ln (e).
Let O be, a set of ontologies and T be the set of terms contained in these ontologies. The vector of terms representing an ontology o is

-→ D O = (w 1 , ..., w n )
where each w i represents the weight of term t i ∈ T for the ontology o. We have selected three types of weights :

-boolean weights: [START_REF] Robertson | Relevance weighting of search terms[END_REF] :

w i = 1 if t i occurs in o, w i = 0 otherwise. -frequency weights : w i = T F (t i , o) -TF•IDF
w i = T F (t i , o). ln |O| |{o|ti∈lte(o}|
Then for comparing ontologies, it is possible to apply various similarity measures:

-Jaccard index with boolean weights; -cosine index with frequency weights; -cosine index with TF•IDF weights.

The first measure (Jaccard index with boolean weights) is close to the complement to 1 of the Hamming distance on class names.

Distances between ontology entities

The main way to measure a distance between ontologies is to compare their entities, e.g., their classes, properties, individuals. So any sort of distance that has been developed for matching ontologies can be extended as a distance between ontologies. There are such entity distances mentioned in [START_REF] Euzenat | Ontology matching[END_REF] since they are the most common basis of ontology matching. where M (e, e ) is a maximum weight matching of T (e) × T (e ), and sim jw is the Jaro Winkler similarity.

Label-based distances

Structural distances There has been many proposals for distances between ontology concepts. Indeed most of the proposed distances in the literature are based on concept distances [START_REF] Mädche | Measuring similarity between ontologies[END_REF][START_REF] Euzenat | Similarity-based ontology alignment in OWL-lite[END_REF][START_REF] Hu | Semantic metrics[END_REF][START_REF] Vrandečić | How to design better ontology metrics[END_REF].

OLA similarity One good candidate as structural similarity is the those defined for OLA [START_REF] Euzenat | Similarity-based ontology alignment in OWL-lite[END_REF] because it relies on every feature of ontologies. OLA first encodes the ontologies into a labelled graph called OL-graph. Then, given an OL-Graph node, the similarity between two OL-graph nodes depends on:

-the similarity of the terms used to designate them, i.e., URIs, labels, names, etc., -the similarity of the pairs of neighbor nodes in the respective OL-Graphs that are linked by edges expressing the same relationships, e.g., class node similarity depends on similarity of superclasses, of property restrictions and of member objects, -the similarity of other local descriptive features depending on the specific category, e.g., cardinality intervals, property types Datatype and datavalue similarities are external and therefore they are either userprovided or measured by a standard function, e.g., string identity of values and datatype names/URIs.

Formally, given a category X together with the set of relationships it is involved in, N (X), the similarity measure Sim X : X 2 → [0, 1] is defined as follows:

Sim X (x, x ) = F ∈N (X) π X F M Sim Y (F(x), F(x )).
The function is normalized, i.e., the weights π X F sum to one, F ∈N (X) π X F = 1. The set functions M Sim Y compare two sets of nodes of the same category. Table 1 illustrates the set of similarities used by OLA.

Funct. Node Factor

Measure The value of these similarities is computed as a fix-point of the set of equations defining the similarity. This process always converges towards a solution. Since this similarity is already computed as an optimization problem, it generates a match of maximal weight.

Sim O o ∈ O λ(o) sim L a ∈ A, (o, a) ∈ A M Sim A Sim A a ∈ A r ∈ R, (a, r) ∈ R Sim R o ∈ O, (a, o) ∈ U M Sim O v ∈ V , (a, v) ∈ U M Sim V Sim V v ∈ V value literal type dependent Sim C c ∈ C λ(c) sim L p ∈ P , (c, p) ∈ A M Sim P c ∈ C, (c, c ) ∈ S M Sim C sim D d ∈ D λ(r) XML-Schema Sim R r ∈ R λ(r) sim L c ∈ C, (r, domain, c) ∈ R M Sim C c ∈ C, (r, range, c) ∈ R M Sim C d ∈ D, (r, range, d) ∈ R Sim D r ∈ R, (r, r ) ∈ S M Sim R Sim P p ∈ P r ∈ R, (p, r ) ∈ S Sim R c ∈ C, (p, all, c) ∈ R M Sim C n ∈ {0, 1, ∞}, (p, card, n) ∈ R
Triple-based iterative similarity measure We have also defined a new measure based on RDF triple similarity. This similarity is defined as a convergent sequence. Initially, some similarity values between nodes in the RDF graph are initialized via string similarity.

In a triple-based representation of an ontology, we consider 4 types of nodes:

-blank node: node having no URI, -local node: named node defined in the ontology, i.e., node having the same namespace as the ontology, -external node: named node not defined in the ontology : node imported from other ontologies, or node from the language, -literal node.

simN 0 (n 1 , n 2 ) =          1 if n 1 = n 2 , simS(n 1 , n 2 ) if n 1 and n 2 are literals, simS(n 1 , n 2 ) if n 1 and n 2 are local nodes, 0 otherwise.
where simS is a syntactic similarity such as JaroWinkler or Levenstein.

Then, this measure is iteratively refined until the amount of change reaches a userdefined threshold. Given two nodes n 1 and n 2 , the node similarity simN i+1 between n 1 and n 2 is defined, for the stage i + 1, by:

simN i+1 (n 1 , n 2 ) = 1 N max k∈{sub,pred,obj} ∆ tx∈T k x ty∈T k y simT i (t x , t y ) × max(|T k x |, |T k y |)
where

T k x = {t x |t x .k = 1 }, T k y = {t y |t y .k = n 2 }, and
N max = k∈{sub,pred,obj} max(|T k x |, |T k y |)
∆ is a collection similarity such as those introduced in Section 4.3. simT i is a similarity between two triples defined as the average values of similarities between nodes of two triples at stage i:

simT i (t 1 , t 2 ) = simN i (t 1 .pred, t 2 .pred) 3 k∈{sub,pred,obj} simN i (t 1 .k, t 2 .k)
In the evaluations, we instantiate this measure with JaroWinkler similarity as simS and MWMGM similarity (presented Section 4.3) as ∆. We choose to stop iterations when n1,n2∈N odes 2 |simN i (n 1 , n 2 ) -simN i+1 (n 1 , n 2 )| ≤ 1.

Collection distances

Once one has a distance δ (or similarity sim) among concepts available, turning it into an ontology distance is not straightforward. There are different choices for extending measures at the concept level to the ontology level. This is achieved with the help of a collection measure ∆ which computes the ontology measure value from the concept measures values. We present some of these below. These collection measures are defined as distance measures, but they can be turned into similarity measures easily.

Definition 4 (Average linkage). Given a set of entities E and a dissimilarity function δ : E × E → [0 1], the average linkage measure between two ontologies is a dissimilarity function The problem with the Hausdorff distance, as with other linkage measures, is that its value in function of the distance between one pair of members of the sets. The average linkage, on the other hand, has its value function of the distance between all the possible comparisons. None of these are satisfactory. Matching-based dissimilarities [START_REF] Valtchev | Construction automatique de taxonomies pour l'aide à la représentation de connaissances par objets[END_REF] measure the dissimilarity between two ontologies by taking into account an alignment (matching) between these two ontologies. It can be defined independently of any alignment by using the minimum weight maximum matching. The quality of such a measure is thus that closeness depends on the actual correspondences between two ontologies (not an average). It will thus be possible to translate the knowledge of one ontology into another. However, these measures will be more difficult to compute.

∆ alo : 2 E × 2 E → [0 1] such that ∀o, o ⊆ E, ∆ alo (o, o ) = (e,
Definition 6 (Minimum weight maximum graph matching distance). Given a set of entities E and a dissimilarity function δ : E × E → [0 1], for any ontologies o, o ⊆ E, a minimum weight maximum graph matching is a one-to-one matching M ⊆ o × o , such that for any one-to-one alignment

M ⊆ o × o , p,q ∈M δ(p, q) ≤ p,q ∈M δ(p, q)
Then, one can define the distance between these two ontologies as:

∆ mwmgm (o, o ) = p,q ∈M δ(p, q) + max(|o|, |o |) -|M | max(|o|, |o |)
Computing the minimum weight maximum graph matching distance (MWMGM) from a similarity, involves two related steps: extracting an alignment between the ontology and computing the distance value. The value depends on the extracted alignment and usual algorithms extract a matching, i.e., a one-to-one alignment. While this may be a reasonable choice mathematically, this may not be the needed alignment on which to ground such a distance. Hence, MWMGM leaves space for improvement.

Experimental setting

The presented measures have to our knowledge, not been evaluated on ontology distances. We have emitted opinion on their relevance only grounded on their mathematical form. It is necessary to enhance this judgement through evaluation. We want to evaluate both the speed of distance computation and the accuracy with regard to asserted similarity.

The ideal experimental setting comprises a corpus of ontologies with clear expectations about the distances that should be found between them. We do not have such a corpus annotated with distances values between ontologies. However, the most important thing is to know the proximity order between ontologies.

Finding a relevant corpus is not an easy task. For this reason we provide only preliminary results here. We first describe the tested methods, the test set and various tests performed with this test set.

Selected measures

In order to be representative, we selected both terminological and structural measures usually used in ontology matching. For each kind of measures, we chose to evaluate basic measures and more elaborated ones as shows Table 2. The JaccardVM(TF) measure is the simplest one since it only represents the proportion of shared terms in two ontologies. CosineVM has been used with two types of weights: TF and TF•IDF. All other measures are entity based measures and then, they have been tested with the three collection measures presented Section 4.3: the Average Linkage, the Hausdorff distance, and the MWMGM distance. For normalization purpose, all measures evaluated here are similarity measures. Table 2. Selected measures.

Evaluation on the OAEI benchmark suite

We have considered the Ontology Alignment Evaluation Initiative1 benchmark test set because it offers a set of ontologies that are systematically altered from one particular ontology which will play the role of o. There are here 6 categories of alterations:

Name Name of entities that can be replaced by (R/N) random strings, (S)ynonyms, Name with different (C)onventions, (F) strings in another language than English. Comments Comments can be (N) suppressed or (F) translated in another language. Specialization hierarchy can be (N) suppressed, (E)xpansed or (F)lattened. Instances can be (N) suppressed Properties can be (N) suppressed or (R) having the restrictions on classes discarded. Classes can be (E)xpanded, i.e., replaced by several classes or (F)latened.

Since, these ontologies are generated by applying successive transformations to o we know that the ontologies resulting from applying less transformations (for inclusion) should be closer to o. This is this property that we have exploited in this first test set.

Order between ontologies of benchmark We can to build a partial order relation ≤ representing the alteration relation over all generated ontologies. o ≤ o seems that the ontology o is an alteration of o (o can be obtained by altering some features of o ).

For each category of alteration c ∈ {N ame, Comments, Specialization, Instances, P roperties, Classes} and each ontology o, c(o) represents the type of alteration made on the reference ontology for the category c. For each category, these alterations are ordered in the following way: Initially we were considering all triples of ontologies related by a transformation path. But we observed that this procedure was biased towards lexical measures since it compares only labels and thus only changes its value between equal labels and non equal ones. Since our test is based on ≤, very often the distances are the same and thus the property was satisfied. Given the huge proportion of such tests in our test set we restricted ourselves comparing two ontologies with the initial ontology.

Name {R, N } ≤ {S, C, F } ≤ ∅ Instance N ≤ ∅ Comments N ≤ F ≤ ∅ Property N ≤ R ≤ ∅ Specialization hierarchy {N, E, F } ≤ ∅ Classes {E, F } ≤ ∅ From these rules, an ontology o is an alteration of o , noted o ≤ o , if for each category of alterations c, we have c(o) ≤ c(o ).
Another bias given by this test set is that the transformations were of the all-ornothing kind: either all labels are changed, or they are preserved. For countering this bias, we produced a larger altered test set in which the label scrambling transformation is applied in (always the same) 20, 40, 60 and 80% of the labels. The new lattice is given in Figure 2.

Results

According to the experimental settings introduced in the previous section, we have collected and analyzed 3 kinds of results. The first results concern the comparison of the orders induced by measures and those really observed on the benchmark suites. The second results show how measures behave when we introduce unrelated ontologies. The last results are about the time consumption of evaluated measures.

Order comparison on benchmark

This first experiment aims at checking if the tested similarities are compatible with the order induced by the alterations. It checks if the assertion sim

(o, o ) ≤ sim(o, o ) (or δ(o, o ) ≤ δ(o, o ) for distances) is verified for any triple o, o , o such as o < o < o.
1372 triples can be formed with the original benchmark suite and 15780 triples with the enhanced benchmark suite.

Table 3 shows results obtained respectively on the original benchmark and the enhanced one. This table presents, for each measure, the proportions of triples o, o , o

(such as o < o < o) verifying sim(o, o ) ≤ sim(o, o ).
On the original benchmark, the triple-based similarity performs the best with all structural measures. Cosine measure with TF weights also obtains good results and outperforms measures based on OLA similarity. Then, Jaccard similarity on TF weights gives satisfactory results. The measures based on lexical similarity and cosine with TF•IDF weights are the worst measures since they successfully passed only the half of the tests. Concerning, structural measures, MWMGM seems to be the best collection measure with the lexical and triple-based similarities. greater than 0 with OLA and none with lexical similarity (which explain the N aN value). Surprisingly, OLA similarity obtains its best result with AverageLinkage.

Measures tend to perform better on the enhanced benchmark than on the original benchmark. This improvement is especially noteworthy with lexical measures such as lexical entity, vector-based similarities. Triple-based similarity improves it results with all collection measures. OLA similarity almost obtain the same results. This owes to the fact that ontologies are, on average, more lexically similar in the enhanced benchmark. Results of MWMGM are better with all tested measures, but average linkage obtains worse results with lexical and OLA similarities. Results of Hausdorff are still not relevant with OLA and lexical similarities.

These results show that structural measures are more robust to the lexical alterations than lexical based measures. In cases where ontologies are lexically close, the use of vectorial measures seems to be relevant. The entity lexical measure is more sensitive to the collection measure used than structural measures. This can be explained by the fact that structural entity distances values are more dependent each other than lexical entity distances values. The advantage of TF against TF.IDF is probably due to the nature of the benchmark: since the altered ontologies are generated from one reference, a term tends to appear in a lot of ontologies and then its IDF weight is around 0.

Tests with different cardinality matching

Finally, the benchmark test set is still biased towards 1-1 matching, so algorithms which are enforcing them (and in particular maximal matching algorithms) should be favored by our tests. In order to counter this problem, we used two imperfect tests:

-we compared with similar but different ontologies: 301, 303, 304 to be compared with the higher level of the hierarchy where what has changed is added/suppressed classes (248,251,252,221,222,223,228,250) and suppressed properties (228, 250); -we compared with irrelevant ontologies (confious, iasted and paperdyne from the conference test).

The expected result here is that the slightly altered ontologies are closer than the 30x which are still better than the conference ontologies (2xx > 3xx > CONFERENCE). Table 4 presents, for each measure, the ontologies which have not been correctly ordered and the observed order. For example, 250 < 304 means that the measure finds that 304 is closer to 101 than 250 (sim(101, 250) < sim(101, 304)). In this experiment MWMGM similarities perform the best. Results given by Hausdorff measure combined with lexical and OLA similarities are not relevant since a lot of values are equals to 0. Nevertheless, triple-based similarity with Hausdorff gives good results. Results obtained by average linkage with lexical and triple-based similarities are not satisfactory since a lot of ontologies are not correctly ordered. Vectorial measures fail on the same tests: they do not work very well when the names of classes have been removed (ontologies 248, 250, 251, 252).

In this experiment, ontologies having different cardinality do not penalize MWMGM in comparison with other measures. These results also show the limits of lexical measures on tests where structure is preserved but not the lexical data.

Time consumption

We compared the CPU time used by each measure. The testing platform is powered by a quad-core 3GHz Xeon processor with a Linux OS. All evaluated measures (but OLA) have been implemented and evaluated using the same framework. For each measure, we computed all similarity values between ontologies of the original benchmark. This test was performed two times with no significant differences in taken times. These results are those of the second round. Table 5 shows the CPU time spent to compute these 1225 similarities and the average time spent to compute one similarity value.

These results clearly shows that measures based on OLA are runtime intensive. Measures using triple-based entity similarity are 5 times less expensive than the first family. Lexical Entity based similarities and those based on the vector space model measures are computed largely faster.

Globally, these results confirm that entity-based measures are more time intensive than VSM measures. Among the entity-based measures, structural measures (OLA and triple-based entity similarities) are more extensive than lexical ones since they rely on an iterative refinement process. The observed runtime is consistent with theoretical complexity of measures (and the computation of all but the more complex is deterministic), so we do not observe a significant effect from coding.

This experimentation shows that only lexical measures are useable at large scale.

Conclusion

Measuring distances between ontologies can be useful in various tasks for different purposes (finding an ontology to replace another, finding an ontology in which queries can be translated, finding people using similar ontologies). Hence there is no universal criterion for deciding if an ontology is close or far from another. There exist many measures using different aspects of ontologies. In order to know the behaviour of these methods, we have evaluated them on specific test benches. Results shows that structural similarities tends to more reliable and robust than lexical similarities. This is especially true when the ontologies to compare do not share a lot of common vocabulary. Nevertheless, due their complexity, structural measures are not adapted for real-time applications or for measuring similarities between large ontologies. We can also notice that some basic measures such cosine on TF vector give quite accurate results. Such kind of measures can be useful for quickly select a subset of close ontologies and thus allowing the use of structural measures in order to refine the proximity relation between the selected ontologies. Hence, more work must be developed for finding trade-offs between accuracy and efficiency.

This paper only restricts the study to measures used for matching ontologies. It could be interesting to test others measures relying on some global ontology characteristics (size, graphs densities, etc.).

  Lexical aggregation-based similarity measure This first local measure only relies on the lexical information coming from annotations and the local name. Given an entity e, T (e) = {l ln (uri(e))} ∪ l annot (e) represents the set containing the annotations and the local name of e. The lexical similarity between two entities e ∈ o and e ∈ o is given by: sim l (e, e ) = (a,b)∈M (e,e ) sim jw (a, b) min(|T (e)|, |T (e )|)

  e )∈o×o δ(e, e ) |o| × |o | . Definition 5 (Hausdorff distance). Given a set of entities E and a dissimilarity function δ : E × E → [0 1], the Hausdorff distance between two sets is a dissimilarity function ∆ Hausdorf f : 2 E × 2 E → [0 1] such that ∀o, o ⊆ E, ∆ Hausdorf f (o, o ) = max(max

  Figure 1 displays a transitive reduction of this partial order.

Fig. 1 .

 1 Fig. 1. Order lattice on benchmark ontologies set.

Fig. 2 .

 2 Fig. 2. Order lattice on the enhanced benchmark ontologies set.

Table 3 .

 3 Hausdorff is only relevant with triple-based similarity because only 10% of tests have a reference similarity, sim(o, o ), Results on the original and enhanced benchmark test sets.

	Measure	Tests Passed (ratio) Original Enhanced
	MWMGM (EntityLexicalMeasure)	0.53	0.72
	Hausdorff (EntityLexicalMeasure)	NaN	NaN
	AverageLinkage (EntityLexicalMeasure) 0.44	0.31
	MWMGM (OLAEntitySim)	0.75	0.78
	Hausdorff (OLAEntitySim)	0.75	0.65
	AverageLinkage (OLAEntitySim)	0.79	0.74
	MWMGM (TripleBasedEntitySim)	0.86	0.92
	Hausdorff (TripleBasedEntitySim)	0.86	0.89
	AverageLinkage (TripleBasedEntitySim) 0.82	0.91
	CosineVM (TF)	0.82	0.92
	CosineVM (TFIDF)	0.57	0.81
	JaccardVM (TF)	0.71	0.87

Table 4 .

 4 Ordering error between ontologies on a selection of ontologies.

Table 5 .

 5 CPU time consumption on the original benchmark.

	Measure	Total time	Average time
		(s)	per value (s)
	MWMGM(EntityLexicalMeasure)	558	0.46
	MWMGM (OLAEntitySim)	39 074	31.9
	MWMGM (TripleBasedEntitySim)	7 950	6.49
	Hausdorff (EntityLexicalMeasure)	451	0.37
	Hausdorff (OLAEntitySim)	38 912	31.76
	Hausdorff (TripleBasedEntitySim)	7 410	6.05
	AverageLinkage (EntityLexicalMeasure)	444	0.36
	AverageLinkage (OLAEntitySim)	38 995	31.83
	AverageLinkage (TripleBasedEntitySim) 7 671	6.26
	CosineVM (TF)	101	0.08
	CosineVM (TFIDF)	102	0.08
	JaccardVM (TF)	101	0.08

http://oaei.ontologymatching.org