Ph Guillemain

A Digital Synthesis Model of Double-Reed Wind Instruments

Keywords: double-reed, synthesis, impedance

We present a real-time synthesis model for double-reed wind instruments based on a nonlinear physical model. One specificity of doublereed instruments, namely, the presence of a confined air jet in the embouchure, for which a physical model has been proposed recently, is included in the synthesis model. The synthesis procedure involves the use of the physical variables via a digital scheme giving the impedance relationship between pressure and flow in the time domain. Comparisons are made between the behavior of the model with and without the confined air jet in the case of a simple cylindrical bore and that of a more realistic bore, the geometry of which is an approximation of an oboe bore.

INTRODUCTION

The simulation of woodwind instrument sounds has been investigated for many years since the pioneer studies by Schumacher [START_REF] Schumacher | Ab initio calculations of the oscillation of a clarinet[END_REF] on the clarinet, which did not focus on digital sound synthesis. Real-time-oriented techniques, such as the famous digital waveguide method (see, e.g., Smith [START_REF] Smith | Principles of digital waveguide models of musical instruments[END_REF]a n d Välimäki [START_REF] Välimäki | Digital waveguide modeling of wind instrument bores constructed of truncated cones[END_REF]) and wave digital models [START_REF] Van Walstijn | Discrete-time modeling of woodwind instrument bores using wave variables[END_REF] have been introduced in order to obtain efficient digital descriptions of resonators in terms of incoming and outgoing waves, and used to simulate various wind instruments.

The resonator of a clarinet can be said to be approximately cylindrical as a first approximation, and its embouchure is large enough to be compatible with simple airflow models. In double-reed instruments, such as the oboe, the resonator is not cylindrical but conical and the size of the air jet is comparable to that of the embouchure. In this case, the dissipation of the air jet is no longer free, and the jet remains confined in the embouchure, giving rise to additional aerodynamic losses.

Here, we describe a real-time digital synthesis model for double-reed instruments based on one hand on a recent study by Vergez et al. [START_REF] V E R G E Z | Toward a simple physical model of double-reed musical instruments: influence of aero-dynamical losses in the embouchure on the coupling between the reed and the bore of the resonator[END_REF], in which the formation of the confined air jet in the embouchure is taken into account, and on the other hand on an extension of the method presented in [START_REF] Ph | Real-time synthesis of wind instruments, using nonlinear physical models[END_REF] for synthesizing the clarinet. This method avoids the need for the incoming and outgoing wave decompositions, since it deals only with the relationship between the impedance variables, which makes it easy to transpose the physical model to a synthesis model.

The physical model is first summarized in Section 2.I n order to obtain the synthesis model, a suitable form of the flow model is then proposed, a dimensionless version is written and the similarities with single-reed models (see, e.g., [START_REF] Kergomard | Elementary considerations on reed-instrument oscillations[END_REF]) are pointed out. The resonator model is obtained by associating several elementary impedances, and is described in terms of the acoustic pressure and flow.

Section 3 presents the digital synthesis model, which requires first discrete-time equivalents of the reed displacement and the impedance relations. The explicit scheme solving the nonlinear model, which is similar to that proposed in [START_REF] Ph | Real-time synthesis of wind instruments, using nonlinear physical models[END_REF], is then briefly summarized.

In Section 4, the synthesis model is used to investigate the effects of the changes in the nonlinear characteristics induced by the confined air jet.

PHYSICAL MODEL

The main physical components of the nonlinear synthesis model are as follows.

(i) The linear oscillator modeling the first mode of reeds vibration. (ii) The nonlinear characteristics relating the flow to the pressure and to the reed displacement at the mouthpiece. (iii) The impedance equation linking pressure and flow.

Figure 1 shows a highly simplified embouchure model for an oboe and the corresponding physical variables described in Sections 2.1 and 2.2.

Reed model

Although this paper focuses on the simulation of doublereed instruments, oboe experiments have shown that the displacements of the two reeds are symmetrical [START_REF] V E R G E Z | Toward a simple physical model of double-reed musical instruments: influence of aero-dynamical losses in the embouchure on the coupling between the reed and the bore of the resonator[END_REF][START_REF] Almeida | Physical study of double-reed instruments for application to soundsynthesis[END_REF]. In this case, a classical single-mode model seems to suffice to describe the variations in the reed opening. The opening is based on the relative displacement y(t) of the two reeds when ad i fference in acoustic pressure occurs between the mouth pressure p m and the acoustic pressure p j (t) of the air jet formed in the reed channel. If we denote the resonance frequency, damping coefficient, and mass of the reeds ω r , q r and µ r , respectively, the relative displacement satisfies the equation

d 2 y(t) dt 2 + ω r q r dy(t) dt + ω 2 r y(t) =- p m -p j (t) µ r . ( 1
)
Based on the reed displacement, the opening of the reed channel denoted S i (t) is expressed by

S i (t) = Θ y(t)+H × w y(t)+H ,( 2 )
where w denotes the width of the reed channel, H denotes the distance between the two reeds at rest (y(t)andp m = 0) and Θ is the Heaviside function, the role of which is to keep the opening of the reeds positive by canceling it when y(t)+H< 0.

Nonlinear characteristics

Physical bases

In the case of the clarinet or saxophone, it is generally recognized that the acoustic pressure p r (t)andvolumevelocity v r (t) at the entrance of the resonator are equal to the pressure p j (t)andvolumevelocityv j (t) of the air jet in the reed channel (see, e.g., [START_REF] Hirschberg | Aero-acoustics of wind instruments[END_REF]). In oboe-like instruments, the smallness of the reed channel leads to the formation of a confined air jet. According to a recent hypothesis [START_REF] V E R G E Z | Toward a simple physical model of double-reed musical instruments: influence of aero-dynamical losses in the embouchure on the coupling between the reed and the bore of the resonator[END_REF], p r (t)isnolongerequal in this case to p j (t), but these quantities are related as follows

p j (t) = p r (t)+ 1 2 ρΨ q(t) 2 S 2 ra , ( 3 )
where Ψ is taken to be a constant related to the ratio between the cross section of the jet and the cross section at the entrance of the resonator, q(t) is the volume flow, and ρ is the mean air density. In what follows, we will assume that the area S ra , corresponding to the cross section of the reed channel at the point where the flow is spread over the whole cross section, is equal to the area S r at the entrance of the resonator.

The relationship between the mouth pressure p m and the pressure of the air jet p j (t) and the velocity of the air jet v j (t) and the volume flow q(t), classically used when dealing with single-reed instruments, is based on the stationary Bernoulli equation rather than on the Backus model (see, e.g., [START_REF] Ollivier | Contribution àl ' étude des oscillations des instruments àv e n tà anche simple[END_REF]for justification and comparisons with measurements). This relationship, which is still valid here, is

p m = p j (t)+ 1 2 ρv j (t) 2 , q(t) = S j (t)v j (t) = αS i (t)v j (t), (4)
where α, which is assumed to be constant, is the ratio between the cross section of the air jet S j (t) and the reed opening S i (t).

It should be mentioned that the aim of this paper is to propose a digital sound synthesis model that takes the dissipation of the air jet in the reed channel into account. For a detailed physical description of this phenomenon, readers can consult [START_REF] V E R G E Z | Toward a simple physical model of double-reed musical instruments: influence of aero-dynamical losses in the embouchure on the coupling between the reed and the bore of the resonator[END_REF], from which the notation used here was borrowed.

Flow model

In the framework of the digital synthesis model on which this paper focuses, it is necessary to express the volume flow q(t) as a function of the difference between the mouth pressure p m and the pressure at the entrance of the resonator p r (t).

From (4), we obtain v j (t) 2 = 2 ρ p m -p j (t) ,( 5 )

q 2 (t) = α 2 S i (t) 2 v j (t) 2 . ( 6
)
Substituting the value of p j (t)givenby(3) into [START_REF] V E R G E Z | Toward a simple physical model of double-reed musical instruments: influence of aero-dynamical losses in the embouchure on the coupling between the reed and the bore of the resonator[END_REF]gives

v j (t) 2 = 2 ρ p m -p r (t) -Ψ q(t) 2 S 2 r . ( 7
)
Using [START_REF] Ph | Real-time synthesis of wind instruments, using nonlinear physical models[END_REF], this gives

q 2 (t) = α 2 S i (t) 2 2 ρ p m -p r (t) -Ψ q(t) 2 S 2 r , ( 8 )
from which we obtain the expression for the volume flow, namely, the nonlinear characteristics

q(t) = sign p m -p r (t) × αS i (t) 1+Ψα 2 S i (t) 2 /S 2 r 2 ρ p m -p r (t) . ( 9
)

Dimensionless model

The reed displacement and the nonlinear characteristics are converted into the dimensionless equations used in the synthesis model. For this purpose, we first take the reed displacement equation and replace the air jet pressure p j (t) by the expression involving the variables q(t)a n dp r (t)( e q u a t i o n (3)),

d 2 y(t) dt 2 + ω r q r dy(t) dt + ω 2 r y(t) =- p m -p r (t) µ r + ρΨ q(t) 2 2µ r S 2 r . ( 10
)
On similar lines to what has been done in the case of singlereed instruments [START_REF] Wilson | Operating modes of the clarinet[END_REF], y(t) is normalized with respect to the static beating-reed pressure p M defined by p M = Hω 2 r µ r . We denote by γ the ratio, γ = p m /p M and replace y(t)b y x(t), where the dimensionless reed displacement is defined by x(t) = y(t)/H + γ.

With these notations, (10)becomes

1 ω 2 r d 2 x(t) dt 2 + q r ω r dx(t) dt + x(t) = p r (t) p M + ρΨ 2p M q(t) 2 S 2 r ( 11
)
and the reed opening is expressed by

S i (t) = Θ 1 -γ + x(t) × wH 1 -γ + x(t) . ( 12
)
Likewise, we use the dimensionless acoustic pressure p e (t) and the dimensionless acoustic flow u e (t)definedby

p e (t) = p r (t) p M , u e (t) = ρc S r q(t) p M , ( 13
)
where c is the speed of the sound. With these notations, the reed displacement and the nonlinear characteristics are finally rewritten as follows,

1 ω 2 r d 2 x(t) dt 2 + q r ω r dx(t) dt + x(t) = p e (t)+Ψβ u u e (t) 2 (14)
and using ( 9)and [START_REF] Ph | Real-time synthesis models of wind instruments based on physical models[END_REF],

u e (t) = Θ 1 -γ + x(t) sign γ -p e (t) × ζ 1 -γ + x(t)
1+Ψβ x 1 -γ + x(t) 2 γ -p e (t) = F x(t), p e (t) , (15)
where ζ, β x and β u are defined by

ζ = √ H 2ρ µ r cαw S r ω r , β x = H 2 α 2 w 2 S 2 r , β u = H ω 2 r µ r 2ρc 2 . ( 16
)
This dimensionless model is comparable to the model described, for example, in [START_REF] Kergomard | Elementary considerations on reed-instrument oscillations[END_REF][START_REF] Hirschberg | Aero-acoustics of wind instruments[END_REF] in the case of single-reed instruments, where the dimensionless acoustic pressure p e (t), the dimensionless acoustic flow u e (t), and the dimensionless reed displacement x(t) are linked by the relations

1 ω 2 r d 2 x(t) dt 2 + q r ω r dx(t) dt + x(t) = p e (t)
,

u e (t) = Θ 1 -γ + x(t) sign γ -p e (t) ×ζ 1 -γ + x(t) γ -p e (t) . ( 17
)
In addition to the parameter ζ, two other parameters β x and β u depend on the height H of the reed channel at rest. Although, for the sake of clarity in the notations, the variable t has been omitted, γ, ζ, β x ,andβ u are functions of time (but slowly varying functions compared to the other variables). Taking the difference between the jet pressure and the resonator pressure into account results in a flow which is no longer proportional to the reed displacement, and a reed displacement which is no longer linked to p e (t) in an ordinary linear differential equation.

Resonator model

We now consider the simplified resonator of an oboe-like instrument. It is described as a truncated, divergent, linear conical bore connected to a mouthpiece including the backbore to which the reeds are attached, and an additional bore, the volume of which corresponds to the volume of the missing part of the cone. This model is identical to that summarized in [START_REF] Ph | Real-time synthesis models of wind instruments based on physical models[END_REF].

Cylindrical bore

The dimensionless input impedance of a cylindrical bore is first expressed. By assuming that the radius of the bore is large in comparison with the boundary layers thicknesses, the classical Kirchhoff theory leads to the value of the complex wavenumber for a plane wave k(ω

) = ω/c - (i 3/2 /2)ηcω 1/2 ,whereη is a constant depending on the radius R of the bore η = (2/Rc 3/2 )( l v +(c p /c v -1) l t ).
Typical values of the physical constants, in mKs units, are l v = 4.10 -8 , l t = 5.6.10 -8 , C p /C v = 1.4 (see, e.g., [START_REF] Pierce | Acoustics-An Introduction to Its Physical Principles and Applications[END_REF]). The transfer function of a cylindrical bore of infinite length between x = 0a n dx = L, which constitutes the propagation filter associated with the Green formulation, including the propagation delay, dispersion, and dissipation, is then given by

F(ω) = exp(-ik(ω)L).
Assuming that the radiation losses are negligible, the dimensionless input impedance of the cylindrical bore is classically expressed by

C(ω) = i tan k(ω)L . ( 18
)
In this equation, C(ω) is the ratio between the Fourier transforms P e (ω)a n dU e (ω) of the dimensionless variables p e (t)andu e (t)definedby [START_REF] Pierce | Acoustics-An Introduction to Its Physical Principles and Applications[END_REF]. The input admittance of the cylindrical bore is denoted by C -1 (ω).

Ad i fferent formulation of the impedance relation of a cylindrical bore, which is compatible with a time-domain implementation, and was proposed in [START_REF] Ph | Real-time synthesis of wind instruments, using nonlinear physical models[END_REF], is used and extended here. It consists in rewriting (18)as

C(ω) = 1 1+exp -2ik(ω)L - exp -2ik(ω)L 1+exp -2ik(ω)L . ( 19
)
Figure 2 shows the interpretation of (19)i nt e r m so f looped propagation filters. The transfer function of this model corresponds directly to the dimensionless input impedance of a cylindrical bore. It is the sum of two parts. The upper part corresponds to the first term of (19) and the u e (t) Although k(ω) includes both dissipation and dispersion, the dispersion is small (e.g., in the case of a cylindrical bore with a radius of 7 mm, η = 1.34.10 -5 ), and the peaks of the input impedance of a cylindrical bore can be said to be nearly harmonic. In particular, this intrinsic dispersion can be neglected, unlike the dispersion introduced by the geometry of the bore (e.g., the input impedance of a truncated conical bore cannot be assumed to be harmonic).

p e (t) -exp -2ik(ω)L -exp -2ik(ω)L

Conical bore

From the input impedance of the cylindrical bore, the dimensionless input impedance of the truncated, divergent, conical bore can be expressed as a parallel combination of a cylindrical bore and an "air" bore,

S 2 (ω) = 1 1/ iωx e /c +1/C(ω) , ( 20
)
where x e is the distance between the apex and the input. It is expressed in terms of the angle θ of the cone and the input radius R as x e = R/ sin(θ/2). The parameter η involved in the definition of C(ω)i n (20), which depends on the radius and characterizes the losses included in k(ω), is calculated by considering the radius of the cone at (5/12)L. This value was determined empirically, by comparing the impedance given by (20)withan input impedance of the same conical bore obtained with a series of elementary cylinders with different diameters (stepped cone), using the transmission line theory.

Denoting by D the differentiation operator D(ω) = iω and rewriting (20) in the form S 2 (ω) = D(ω)(x e /c)/(1 + D(ω)(x e /c)C -1 (ω)), we propose the equivalent scheme in Figure 3.

Oboe-like bore

The complete bore is a conical bore combined with a mouthpiece.

The mouthpiece consists of a combination of two bores, (i) a short cylindrical bore with length L 1 ,radiusR 1 ,surface S 1 , and characteristic impedance Z 1 . This is the backbore to which the reeds are attached. Its radius is small in comparison with that of the main conical bore, the characteristic impedance of which is denoted Z 2 = ρc/S r ,and (ii) an additional short cylindrical bore with length L 0 ,radius R 0 ,s u r f a c eS 0 , and characteristic impedance Z 0 . Its radius is large in comparison with that of the backbore. This role serves to add a volume corresponding to the truncated part of the complete cone. This makes it possible to reduce the geometrical dispersion responsible for inharmonic impedance peaks in the combination backbore/conical bore.

The impedance C 1 (ω) of the short cylindrical backbore is based on an approximation of i tan(k 1 (ω)L 1 )w i t hs m a l l values of k 1 (ω)L 1 . It takes the dissipation into account and neglects the dispersion. Assuming that the radius R 1 is large in comparison with the boundary layers thicknesses, using (19), C 1 (ω) is first approximated by

C 1 (ω) ≃ 1 -exp -η 1 c √ ω/2L 1 exp -2iωL 1 /c 1+exp -η 1 c √ ω/2L 1 exp -2iωL 1 /c , (21)
which, since L 1 is small, is finally simplified as

C 1 (ω) ≃ 1 -exp -η 1 c √ ω/2L 1 1 -2iωL 1 /c 1+exp -η 1 c √ ω/2L 1 . ( 22
)
By noting

G(ω) = (1 -exp(-η 1 c √ ω/2L 1 ))/(1 + exp(-η 1 c √ ω/2L 1 )), and H(ω) = (L 1 /c)(1 -G(ω)), the expression of C 1 (ω)reads C 1 (ω) = G(ω)+iωH(ω). ( 23
)
This approximation avoids the need for a second delay line in the sampled formulation of the impedance. The transmission line equation relates the acoustic pressure p n and the flow u n at the entrance of a cylindrical bore (with characteristic impedance Z n ,lengthL n ,andwavenumber k n ) to the acoustic pressure p n+1 and the flow u n+1 at the exit of a cylindrical bore. With dimensioned variables, it reads

p n (ω) = cos k n (ω)L n p n+1 (ω)+iZ n sin k n (ω)L n u n+1 (ω), u n (ω) = i Z n sin k n (ω)L n p n+1 (ω)+cos k n (ω)L n u n+1 (ω), (24)
yielding Using the notations introduced in (20)a n d( 23), the input impedance of the combination backbore/main conical bore reads p 1 (ω)

p n (ω) u n (ω) = p n+1 (ω)/u n+1 (ω)+iZ n tan k n (ω)L n 1+(i/Z n )tan k n (ω)L n p n+1 (ω)/u n+1 (ω) . (25) u e (t) C 1 (ω) S 2 (ω) D(ω) Z 1 Z 2 -V ρc 2 1 Z 2 p e (t)
u 1 (ω) = Z 2 S 2 (ω)+Z 1 C 1 (ω) 1+ Z 2 /Z 1 S 2 (ω)C 1 (ω) , (26)
which is simplified as

p 1 (ω)/u 1 (ω) = Z 2 S 2 (ω)+Z 1 C 1 (ω), since Z 1 ≫ Z 2 .
In the same way, the input impedance of the whole bore reads

p 0 (ω) u 0 (ω) = p 1 (ω)/u 1 (ω)+iZ 0 tan k 0 (ω)L 0 1+(i/Z 0 )tan k 0 (ω)L 0 p 1 (ω)/u 1 (ω) , (27)
which, since Z 0 ≪ Z 1 , is simplified as

p 0 (ω) u 0 (ω) = p 1 (ω)/u 1 (ω) 1+(i/Z 0 )tan k 0 (ω)L 0 p 1 (ω)/u 1 (ω) . ( 28
)
Since L 0 is small and the radius is large, the losses included in k 0 (ω) can be neglected, and hence k 0 (ω) = ω/c and tan(k 0 (ω)L 0 ) = (ω/c)L 0 . Under these conditions, the input impedance of the bore is given by

p 0 (ω) u 0 (ω) = 1 1/ p 1 (ω)/u 1 (ω) + iω/c L 0 /Z 0 = 1 1/ Z 2 S 2 (ω)+Z 1 C 1 (ω) + iω/c L 0 S 0 /ρc . ( 29
)
If we take V to denote the volume of the short additional bore V = L 0 S 0 and rewrite (29) with the dimensionless variables P e and U e (U e = Z 2 u 0 ), the dimensionless input impedance of the whole resonator relating the variables P e (ω)andU e (ω)becomes

Z e (ω) = P e (ω) U e (ω) = 1/Z 2 iωV/ ρc 2 +1/ Z 1 C 1 (ω)+Z 2 S 2 (ω) . ( 30
)
After rearranging (30), we propose the equivalent scheme in Figure 4.

It can be seen from ( 30) that the mouthpiece is equivalent to a Helmholtz resonator consisting of a hemispherical cavity with volume V and radius R b such that V = (4/6)πR 3 b ,connected to a short cylindrical bore with length L 1 and radius R 1 .

Summary of the physical model

The complete dimensionless physical model consists of three equations,

1 ω 2 r d 2 x(t) dt 2 + q r ω r dx(t) dt + x(t) = p e (t)+Ψβ u u e (t) 2 , ( 31
)
u e (t) = ζ 1 -γ + x(t)
1+Ψβ x 1 -γ + x(t) 2 × Θ 1 -γ + x(t) sign γ -p e (t) × γ -p e (t) , ( 32
) P e (ω) = Z e (ω)U e (ω). (33)
These equations enable us to introduce the reed and the nonlinear characteristics in the form of two nonlinear loops, as shown in Figure 5. The first loop relates the output p e to the input u e of the resonator, as in the case of single-reed instruments models. The second nonlinear loop corresponds to the u 2 e -dependent changes in x. The output of the model is given by the three coupled variables p e , u e ,andx. The control parameters of the model are the length L of the main conical bore and the parameters H(t)a n dp m (t)f r o mw h i c hζ(t), β x (t), β u (t), and γ(t) are calculated.

In the context of sound synthesis, it is necessary to calculate the external pressure. Here we consider only the propagation within the main "cylindrical" part of the bore in (20). Assuming again that the radiation impedance can be neglected, the external pressure corresponds to the time derivative of the flow at the exit of the resonator p ext (t) = du s (t)/dt. Using the transmission line theory, one directly obtains

U s (ω) = exp -ik(ω)L P e (ω)+U e (ω) . ( 34
)
From the perceptual point of view, the quantity exp(-ik(ω)L) can be left aside, since it stands for the losses corresponding to a single travel between the embouchure and the open end. This simplification leads to the following expression for the external pressure

p ext (t) = d dt p e (t)+u e (t) . ( 35
)

DISCRETE-TIME MODEL

In order to draw up the synthesis model, it is necessary to use a discrete formulation in the time domain for the reed displacement and the impedance models. The discretization schemes used here are similar to those described in [START_REF] Ph | Real-time synthesis of wind instruments, using nonlinear physical models[END_REF]f o r the clarinet, and summarized in [START_REF] Ph | Real-time synthesis models of wind instruments based on physical models[END_REF] for brass instruments and saxophones.

Reed displacement

We t a ke e(t) to denote the excitation of the reed e(t) = p e (t)+Ψβ u u e (t) 2 . Using (31), the Fourier transform of the ratio X(ω)/E(ω) can be readily written as

X(ω) E(ω) = ω 2 r ω 2 r -ω 2 + iωq r ω r . ( 36
)
An inverse Fourier transform provides the impulse response h(t) of the reed model

h(t) = 2ω r 4 -q 2 r exp - 1 2 ω r q r t sin 1 2 4 -q 2 r ω r t . ( 37
)
Equation (37) shows that h(t)satisfiesh(0) = 0. This property is most important in what follows. In addition, the range of variations allowed for q r is ]0, 2[. The discrete-time version of the impulse response uses two centered numerical differentiation schemes which provide unbiased estimates of the first and second derivatives when they are applied to sampled second-order polynomials

iω ≃ f e 2 z -z -1 , -ω 2 ≃ f 2 e z -2+z -1 , (38)
where z = exp(i ω), ω = ω/ f e ,a n d f e is the sampling frequency. With these approximations, the digital transfer function of the reed is given by

X(z) E(z) = z -1 f 2 e /ω 2 r + f e q r / 2ω r -z -1 2 f 2 e /ω 2 r -1 -z -2 f e q r / 2ω r -f 2 e /ω 2 r , (39)
yielding a difference equation of the type

x(n) = b 1a e(n -1) + a 1a x(n -1) + a 2a x(n -2). ( 40
)
This difference equation keeps the property h(0) = 0. Figure 6 shows the frequency response of this approximated reed model (solid line) superimposed with the exact one (dotted line).

This discrete reed model is stable under the condition ω r <f e 4 -q 2 r . Under this condition, the modulus of the poles of the transfer function is given by (2 f e -ω r q r )/(2 f e + ω r q r ) and is always smaller than 1. This stability condition makes this discretization scheme unsuitable for use at low sampling rates, but in practice, at the CD quality sample rate, this problem does not arise for a reed resonance frequency of up to 5 kHz with a quality factor of up to 0.5. For a more detailed discussion of discretization schemes, readers can consult, for example, [START_REF] Avanzini | Efficiency, accuracy, and stability issues in discrete time simulations of single reed instruments[END_REF]. The bilinear transformation does not provide a suitable discretization scheme for the reed displacement. In this case, the impulse response does not satisfy the property of the continuous model h(0) = 0.

Impedance

A time domain equivalent to the inverse Fourier transform of impedance Z e (ω)givenby(30)isnowrequired.Herewe express p e (n) as a function of u e (n).

The losses in the cylindrical bore element contributing to the impedance of the whole bore are modeled with a digital low-pass filter. This filter approximates the back and forth losses described by F(ω) 2 = exp(-2ik(ω)L) and neglects the (small) dispersion. So that they can be adjusted to the geometry of the resonator, the coefficients of the filter are expressed analytically as functions of the physical parameters, rather than using numerical approximations and minimizations. For this purpose, a one-pole filter is used,

F( ω) = b 0 exp(-i ωD) 1 -a 1 exp(-i ω) , ( 41
)
where ω = ω/ f e ,andD = 2 f e (L/c) is the pure delay corresponding to a back and forth path of the waves.

The parameters b 0 and a 1 are calculated so that 2 for two given values of ω,a n da r es olutions of the system

|F(ω) 2 | 2 =| F( ω)|
F ω 1 2 2 1+a 2 1 -2a 1 cos ω1 = b 2 0 , F ω 2 2 2 1+a 2 1 -2a 1 cos ω2 = b 2 0 , ( 42
)
where

|F(ω (1,2) ) 2 | 2 = exp(-2ηc ω (1,2) /2L
). The first value ω 1 is an approximation of the frequency of the first impedance peak of the truncated conical bore given by ω 1 = c(12πL+9π 2 x e +16L)/(4L(4L+3πx e +4x e )), in order to ensure a suitable height of the impedance peak at the fundamental frequency. It is important to keep this feature to obtain a realistic digital simulation of the continuous dynamical system, since the linear impedance is associated with the nonlinear characteristics. This ensures that the decay time of the fundamental frequency of the approximated impulse response of the impedance matches the exact value, which is important in the case of fast changes in γ (e.g., attack transient).

The second value ω 2 corresponds to the resonance frequency of the Helmholz resonator

ω 2 = c S 1 /(L 1 V ).
The phase of F( ω) has a nonlinear part, which is given by -arctan(a 1 sin( ω)/(1 -a 1 cos( ω))). This part differs from the nonlinear part of the phase of F(ω) 2 , which is given by -ηc √ ω/2L. Although these two quantities are different and although the phase of F( ω) is determined by the choice of a 1 , which is calculated from the modulus, it is worth noting that in both cases, the dispersion is always very small, has a negative value, and is monotonic up to the frequency ( f e /2π)arccos(a 1 ). Consequently, in both cases, in the case of a cylindrical bore, up to this frequency, the distance between successive impedance peaks decreases as their rank increases,

ω n+1 -ω n <ω n -ω n-1 .
Using (19)a n d( 41), the impedance of the cylindrical bore unit C(ω) is then expressed by

C(z) = 1 -a 1 z -1 -b 0 z -D 1 -a 1 z -1 + b 0 z -D . ( 43
)
Since L 1 is small, the frequency-dependent function G(ω) involved in the definition of the impedance of the short backbore C 1 (ω) can be approximated by a constant, corresponding to its value in ω 2 .

The bilinear transformation is used to discretize D = iω: D(z) = 2 f e ((z -1)/(z + 1)).

The combination of all these parts according to (30) yields the digital impedance of the whole bore in the form

Z e (z) = k=4 k=0 b ck z -k + k=3 k=0 b cDk z -D-k 1 -k=4 k=1 a ck z -k -k=3 k=0 a cDk z -D-k , ( 44
)
where the coefficients b ck , a ck , b cDk ,anda cDk are expressed analytically as functions of the geometry of each part of the bore. This leads directly to the difference equation, which can be conveniently written in the form

p e (n) = b c0 u e (n)+ Ṽ , (45)
where Ṽ includes all the terms that do not depend on the time sample n Figure 7 shows an oboe-like bore input impedance, both approximated (solid line) and exact (dotted line) together with the corresponding impulse responses.

Ṽ =

Synthesis algorithm

The sampled expressions for the impulse responses of the reed displacement and the impedance models are now used to write the sampled equivalent of the system of (31), (32), and (33):

x(n) = b 1a p e (n -1) + Ψβ u u e (n -1) 2 + a 1a x(n -1) + a 2a x(n -2), (47)
p e (n) = b c0 u e (n)+ Ṽ , (48)
u e (n) = W sign γ -p e (n) γ -p e (n) , ( 49
)
where W is

W = Θ 1 -γ + x(n) × ζ 1 -γ + x(n) 1+Ψβ x 1 -γ + x(n) 2 .
(50

)
This system of equations is an implicit system, since u e (n) hastobeknowninordertobeabletocomputep e (n) with the impedance equation (48). Likewise, u e (n) is obtained from the nonlinear equation (49) and requires p e (n) to be known.

Thanks to the specific reed discretization scheme presented in Section 3.1, calculating x(n)w i t h( 47)d o e sn o t require p e (n)a n du e (n) to be known. This makes it possible to solve this system explicitly, as shown in [START_REF] Ph | Real-time synthesis of wind instruments, using nonlinear physical models[END_REF], thus doing away with the need for schemes such as the K-method [START_REF] Borin | Elimination of delayfree loops in discrete-time models of nonlinear acoustic systems[END_REF].

Since W is always positive, if one considers the two cases γ -p e (n) ≥ 0andγ -p e (n) < 0, successively, substituting the expression for p e (n)from(48) into (49)eventuallygives

u e (n) = 1 2 sign(γ -Ṽ ) × -b c0 W 2 + W b c0 W 2 +4|γ -Ṽ | . ( 51
)
The acoustic pressure and flow in the mouthpiece at sampling time n are then finally obtained by the sequential calculation of Ṽ with (46), x(n)with( 47), W with (50), u e (n) with (51), and p e (n)with(48).

Theexternalpressurep ext (n) is calculated using the difference between the sum of the internal pressure and the flow at sampling time n and n -1.

SIMULATIONS

The effects of introducing the confined air jet into the nonlinear characteristics are now studied in the case of two different bore geometries. In particular, we consider a cylindrical resonator, the impedance peaks of which are odd harmonics, and a resonator, the impedance of which contains all the harmonics. We start by checking numerically the validity of the resolution scheme in the case of the cylindrical bore. (Sound examples are available at http://omicron.cnrsmrs.fr/∼guillemain/eurasip.html.)

Cylindrical resonator

We first consider a cylindrical resonator, and make the parameter Ψ vary linearly from 0 to 4000 during the sound synthesis procedure (1.5 seconds). The transient attack corresponds to an abrupt increase in γ at t = 0. During the decay phase, starting at t = 1.3 seconds, γ decreases linearly towards zero. Its steady-state value is γ = 0.56. The other parameters are constant, ζ = 0.35, β x = 7.5.10 -4 , β u = 6.1.10 -3 . The reed parameters are ω r = 2π.3150 rad/second, q r = 0.5. The resonator parameters are R = 0.0055 m, L = 0.46 m. Figure 8 shows superimposed curves, in the top figure, the digital impedance of the bore is given in dotted lines, and the ratio between the Fourier transforms of the signals p e (n)andu e (n) in solid lines; in the bottom figure, the digital reed transfer function is given in dotted lines, and the ratio of the Fourier transforms of the signals x(n)a n d p e (n)+Ψ(n)β u u e (n) 2 (including attack and decay transients) in solid lines.

As we can see, the curves are perfectly superimposed. There is no need to check the nonlinear relation between u e (n), p e (n), and x(n), which is satisfied by construction since u e (n) is obtained explicitly as a function of the other variables in (51). In the case of the oboe-like bore, the results obtained using the resolution scheme are equally accurate.

The case of the beating reed

The first example corresponds to a beating reed situation, which is simulated by choosing a steady-state value of γ greater than 0.5 (γ = 0.56).

Figure 9 shows the spectrogram (dB) of the external pressure generated by the model. The values of the spectrogram are coded with a grey-scale palette (small values are dark and high values are bright). The bright horizontal lines correspond to the harmonics of the external pressure. Increasing the value of Ψ mainly affects the pitch and only slightly affects the amplitudes of the harmonics. In particular, at high values of Ψ, a small increase in Ψ results in a strong decrease in the pitch.

A cancellation of the self-oscillation process can be observed at around t = 1.2 seconds, due to the high value of Ψ, since it occurs before γ starts decreasing.

Odd harmonics have a much higher level than even harmonics as occuring in the case of the clarinet. Indeed, the even harmonics originate mainly from the flow, which is taken into account in the calculation of the external pressure. However, it is worth noticing that the level of the second harmonic increases with Ψ.

Figures 10 and11 show the flow u e (n) versus the pressure p e (n), obtained during a small number (32) of oscillation periods at around t = 0.25 seconds, t = 0.5 seconds, t = 0.75 seconds and t = 1 seconds. The existence of two different paths, corresponding to the opening or closing of the reed, is due to the inertia of the reed. This phenomenon is observed also on single-reed instruments (see, e.g., [START_REF] Avanzini | Efficiency, accuracy, and stability issues in discrete time simulations of single reed instruments[END_REF]). A discontinuity appears in the whole path because the reed is beating. This cancels the opening (and hence the flow) while the pressure is still varying.

The shape of the curve changes with respect to Ψ. This shape is in agreement with the results presented in [START_REF] V E R G E Z | Toward a simple physical model of double-reed musical instruments: influence of aero-dynamical losses in the embouchure on the coupling between the reed and the bore of the resonator[END_REF].

The case of the nonbeating reed

The second example corresponds to a nonbeating reed situation, which is obtained by choosing a steady-state value of γ smaller than 0.5 (γ = 0.498).

Figure 12 shows the spectrogram of the external pressure generated by the model. Increasing the value of Ψ results in a sharp change in the level of the high harmonics at around t = 0.4 seconds, a slight change in the pitch, and a cancellation of the self-oscillation process at around t = 0.8 seconds, corresponding to a smaller value of Ψ than that observed in the case of the beating reed.

Figure 13 shows the flow u e (n) versus the pressure p e (n) at around t = 0.25 seconds and t = 0.5 seconds. Since the reed is no longer beating, the whole path remains continuous. The changes in its shape with respect to Ψ are smaller than in the case of the beating reed.

Oboe-like resonator

Inordertocomparetheeffects of the confined air jet with the geometry of the bore, we now consider an oboe-like bore, the input impedance, and geometric parameters of which correspond to Figure 7. The other parameters have the same values as in the case of the cylindrical resonator, and the steady-state value of γ is γ = 0.4.

Figure 14 shows the pressure p ext (t). Increasing the effect of the air jet confinement with Ψ, and hence the aerodynamical losses, results in a gradual decrease in the signal amplitude. The change in the shape of the waveform with respect to Ψ can be seen on the blowups corresponding to the attack and decay transients.

Figure 15 shows the spectrogram of the external pressure generated by the model.

Since the impedance includes all the harmonics (and not only the odd ones as in the case of the cylindrical bore), the output pressure also includes all the harmonics. This makes for a considerable perceptual change in the timbre in comparison with the cylindrical geometry. Since the input impedance of the bore is perfectly harmonic, it is not possible to determine whether the "moving formants" are caused by a change in the value of Ψ or by a "phasing effect" resulting from the slight inharmonic nature of the impedance.

Increasing the value of Ψ affects the amplitude of the harmonics and slightly changes the pitch. In addition, as in the case of the cylindrical bore with a nonbeating reed, a large value of Ψ brings the self-oscillation process to an end. Figures 16 and 17 show the flow u e (n) versus the pressure p e (n)ataroundt = 0.25 seconds, t = 0.5 seconds, t = 0.75 seconds, and t = 1 seconds. The shape and evolution with Ψ of the nonlinear characteristics are similar to what occurs in the case of a cylindrical bore with a beating reed.

CONCLUSION

The synthesis model described in this paper includes the formation of a confined air jet in the embouchure of doublereed instruments. A dimensionless physical model, the form of which is suitable for transposition to a digital synthesis model, is proposed. The resonator is modeled using a time domain equivalent of the input impedance and does not require the use of wave variables. This facilitates the modeling of the digital coupling between the bore, the reed and the nonlinear characteristics, since all the components of the model use the same physical variables. It is thus possible to obtain an explicit resolution of the nonlinear coupled system thanks to the specific discretization scheme of the reed model. This is applicable to other self-oscillating wind instruments using the same flow model, but it still requires to be compared with other methods.

This synthesis model was used in order to study the influence of the confined jet on the sound generated, by carrying out a real-time implementation. Based on the results of informal listening tests with an oboe player, the sound and dynamics of the transients obtained are fairly realistic. The simulations show that the shape of the resonator is the main factor determining the timbre of the instrument in steadystate parts, and that the confined jet plays a role at the control level of the model, since it increases the oscillation step and therefore plays an important role mainly in the transient parts.

Figure 1 :

 1 Figure 1: Embouchure model and physical variables.

Figure 2 :

 2 Figure 2: Impedance model of a cylindrical bore.

1 Figure 3 :

 13 Figure 3: Impedance model of a conical bore.

Figure 4 :

 4 Figure 4: Impedance model of the simplified resonator.

Figure 5 :

 5 Figure 5: Nonlinear synthesis model.

Figure 6 :

 6 Figure 6: Approximated (solid line) and exact (dotted line) reed frequency response with parameter values f r = 2500 Hz, q r = 0.2, and f e = 44.1kHz.

Figure 7 :

 7 Figure 7: (a) represents approximated (solid lines) and exact (dotted lines) input impedance, while (b) represents approximated (solid lines) and exact (dotted lines) impulse response. Geometrical parameters L = 0.46 m, R = 0.00216 m, θ = 2 • , L 1 = 0.02 m, R 1 = 0.0015 m, and R b = 0.006 m.

Figure 8 :Figure 9 :

 89 Figure 8: (a) represents impedance (dotted line) and ratio between the spectra of p e and u e (solid line), while (b) represents reed transfer (dotted line) and ratio of spectra between x and p e +Ψβ u u 2 e (solid line).

Figure 10 :Figure 11 :

 1011 Figure 10: u e (n)v e r s u sp e (n): (a) t = 0.25 second, (b) t = 0.5 second.

Figure 12 :

 12 Figure 12: Spectrogram of the external pressure for a cylindrical bore and a nonbeating reed where γ = 0.498.

Figure 13 :

 13 Figure 13: u e (n)v e r s u sp e (n): (a) t = 0.25 second, (b) t = 0.5 second.

Figure 14 :

 14 Figure 14: (a) represents external acoustic pressure, and (b), (c) represent attack and decay transients.

Figure 15 :Figure 16 :Figure 17 :

 151617 Figure 15: Spectrogram of the external pressure for an oboe-like bore where γ = 0.4.

1

  Laboratoire de Mécanique et d'Acoustique, Centre National de la Recherche Scientifique, 31 chemin Joseph-Aiguier, 13402 Marseille cedex 20, France Email: guillem@lma.cnrs-mrs.fr

	y/2
	p m	H	p j , v j		p r , q
	y/2
		Reeds	Backbore	Main bore

ACKNOWLEDGMENTS

The author would like to thank Christophe Vergez for helpful discussions on the physical flow model, and Jessica Blanc for reading the English.


Sébastien Ferré
email: ferre@irisa.fr

Answers Partitioning and Lazy Joins for Efficient Query Relaxation and Application to Similarity Search

Query relaxation has been studied as a way to find approximate answers when user queries are too specific or do not align well with the data schema. We are here interested in the application of query relaxation to similarity search of RDF nodes based on their description. However, this is challenging because existing approaches have a complexity that grows in a combinatorial way with the size of the query and the number of relaxation steps. We introduce two algorithms, answers partitioning and lazy join, that together significantly improve the efficiency of query relaxation. Our experiments show that our approach scales much better with the size of queries and the number of relaxation steps, to the point where it becomes possible to relax large node descriptions in order to find similar nodes. Moreover, the relaxed descriptions provide explanations for their semantic similarity.

Introduction

Query relaxation has been proposed as a way to find approximate answers to user queries [START_REF] Gaasterland | Cooperative answering through controlled query relaxation[END_REF]. It consists in applying transformations to the user query in order to relax constraints, and make it more general so that it produces more answers. In previous work on SPARQL queries over RDF(S) graphs [START_REF] Hurtado | Query relaxation in RDF[END_REF][START_REF] Dolog | Relaxing RDF queries based on user and domain preferences[END_REF][START_REF] Elbassuoni | Query relaxation for entityrelationship search[END_REF][START_REF] Huang | Approximating query answering on RDF databases[END_REF][START_REF] Frosini | Flexible query processing for SPARQL[END_REF], typical relaxation steps consist in removing a query element or replacing a class by a superclass or a node by a variable. The major limitation of query relaxation is that the number of relaxed queries grows in a combinatorial way with the number of relaxation steps and the size of the query.

A potential application of query relaxation is similarity search, i.e. the search for the nodes most similar to a given query node in an RDF graph. We propose to start with the query node description as an overly specific query, and to relax it progressively in order to find similar nodes as approximate answers. The relaxed queries can then be used as explanations of the similarity with each node, and for ranking similar nodes. However, existing algorithms for query relaxation are not efficient enough for that purpose because node descriptions make up for large queries, and many relaxation steps are necessary in order to find approximate answers. Various definitions of semantic distance/similarity have been proposed, especially between concepts in ontologies [START_REF] Rodríguez | Determining semantic similarity among entity classes from different ontologies[END_REF] but also between structural symbolic descriptions [START_REF] Horváth | Relational instance-based learning with lists and terms[END_REF][START_REF] Ferilli | A general similarity framework for horn clause logic[END_REF]. However, those distances/similarities are numerical measures, and the explanation of the similarity provided by the relaxed queries is lost. In this paper, we only consider symbolic forms of semantic similarity, i.e. similarities that can be represented with graph patterns [START_REF] Colucci | Common subsumbers in RDF[END_REF][START_REF] Ferré | Graph-FCA in practice[END_REF]. A major drawback of those approaches is that the query node has to be compared to every other node in the RDF graph, and that each comparison is costly because it consists in finding the largest overlap between two rooted graphs.

In this paper, we introduce two algorithms, answers partitioning and lazy join, that together improve the efficiency of query relaxation to the point where it can be applied effectively to semantic similarity search. Despite the higher efficiency, our approach does not trade quality for efficiency as it produces the same results as query relaxation and symbolic semantic similarity. The contribution is that our partitioning algorithm is driven by both relaxed queries and similar nodes so as to prune the space of relaxed queries while avoiding individual comparison to each node. The set of nodes is partitioned into more and more fine-grained clusters, such that at the end of the process each cluster is a set of approximate answers produced by the same relaxed query. That relaxed query is the common subsumer between the query and each approximate answer. Lazy join is an essential optimization of our approach to address similarity search because multi-valued properties (e.g., hasActor) combined with high numbers of relaxation steps imply an explosion of the size of joins.

Section 2 discusses related work. Section 3 gives preliminary definitions. Section 4 defines query relaxation, and introduces its application to similarity search. Section 5 details our answers partitioning algorithm, and Section 6 details its optimization with lazy joins. Section 7 report experimental studies of efficiency and effectiveness. Finally, Section 8 concludes and draws perspectives.

Related Work

The existing approaches for query relaxation consist in enumerating relaxed queries up to some edit distance, and to evaluate each relaxed query, from the more specific to the more general, in order to get new approximate answers [START_REF] Hurtado | Query relaxation in RDF[END_REF][START_REF] Huang | Approximating query answering on RDF databases[END_REF][START_REF] Frosini | Flexible query processing for SPARQL[END_REF]. The main problem is that the number of relaxed queries grows in a combinatorial way with the edit distance, and the size of the query. Moreover, many relaxed queries do not yield any new answer because they have the same answers as more specific relaxed queries. Huang et al [START_REF] Huang | Approximating query answering on RDF databases[END_REF] use a similarity score in order to have a better ranking for the evaluation of relaxed queries. They also use a selectivity estimate to save the evaluation of some relaxed queries that are subsumed by a more general relaxed query. Hurtado et al [START_REF] Hurtado | Query relaxation in RDF[END_REF] optimize the evaluation of relaxed queries by directly computing their proper answer but the optimization only works for the relaxations that replace a triple pattern by a single other triple pattern. They also introduce new SPARQL clauses, RELAX and APPROX [START_REF] Frosini | Flexible query processing for SPARQL[END_REF], to restrict relaxation to a small subset of the query. However, this requires from the user to anticipate where relaxation can be useful. The above approaches [START_REF] Hurtado | Query relaxation in RDF[END_REF][START_REF] Huang | Approximating query answering on RDF databases[END_REF] put some limitations on the relaxation steps that can be applied. Triple patterns can be generalized by relaxation according to RDFS inference but generally can not be removed from the query. URI and literal nodes cannot always be replaced by variables, which may work in some querying use cases but is a dead-end for similarity search. Other approaches [START_REF] Dolog | Relaxing RDF queries based on user and domain preferences[END_REF][START_REF] Elbassuoni | Query relaxation for entityrelationship search[END_REF] present powerful relaxation frameworks but they do not evaluate their efficiency or only generate a few relaxed queries.

Among the numerous similarity/distance measures that have been proposed [START_REF] Cunningham | A taxonomy of similarity mechanisms for case-based reasoning[END_REF], only a few work on complex relational representations, and can be applied directly to RDF graphs. RIBL (Relational Instance-Based Learning) [START_REF] Horváth | Relational instance-based learning with lists and terms[END_REF] defines a distance based on the exploration of a graph, starting from a given node and up to a given depth. Ferilli et al [START_REF] Ferilli | A general similarity framework for horn clause logic[END_REF] define a similarity between Horn clauses, which are analogous to SPARQL queries. However, although the input of those measures are symbolic, their output is numeric. The drawbacks are that they do not provide intelligible explanations for the measured similarity, and also that when two nodes are at the same distance/similarity to a query node, it is not possible to say whether this is by chance or because they share the same explanation. Proposals for a symbolic similarity between graph nodes include Least Common Subsumers (LCS) [START_REF] Colucci | Common subsumbers in RDF[END_REF], and intersections of Projected Graph Patterns [START_REF] Ferré | Graph-FCA in practice[END_REF].

Preliminary Definitions

For ease of comparison with previous work, we largely reuse the notations in [START_REF] Hurtado | Query relaxation in RDF[END_REF]. The only addition is the inclusion of filters in conjunctive queries. We here consider RDF graphs under RDFS inference, although our work can work with no schema at all, and can be extended to other kinds of knowledge graphs, like Conceptual Graphs [START_REF] Chein | Graph-based knowledge representation: computational foundations of conceptual graphs[END_REF] or Graph-FCA [START_REF] Ferré | Graph-FCA in practice[END_REF]. An RDF triple is a triple of RDF nodes (s, p, o) ∈ (I ∪B)×I ×(I ∪B ∪L), where I is the set of IRIs, B is the set of blank nodes, and L is the set of literals. An RDF graph G is a set of RDF triples. Its set of nodes is noted nodes(G). Given an RDF(S) graph G, we note cl(G) the closure of the graph with all triples that can be infered. A triple pattern is a triple (t 1 , t 2 , t 3 ) ∈ (I ∪ V ) × (I ∪ V ) × (I ∪ V ∪ L), where V is an infinite set of variables. A filter is a Boolean expression on variables and RDF nodes. We here only consider equalities between a variable and a node: x = n. A graph pattern P is a set of triple patterns and filters, collectively called query elements. We note var(P ) the set of variables occuring in P . A conjunctive query Q is an expression X ← P , where P is a graph pattern, and X = (x 1 , . . . , x n ) is a tuple of variables. X is called the head, and P the body. We define var(Q) = X ∪ var(P ) the set of variables occuring in query Q. A query is said connected if its body is a connected graph pattern, and contains at least one head variable. A matching of pattern P on graph G is a mapping µ ∈ var(P ) → nodes(G) from pattern variables to graph nodes such that µ(t) ∈ cl(G) for every triple pattern t ∈ P , and µ(f ) evaluates to true for every filter f ∈ P , where µ(t) and µ(f ) are obtained from t and f by replacing every variable x by µ(x). The match-set M (P, G) of pattern P on graph G is the set of all matchings of P on G. A match-set M can be seen as a relational table with dom(M ) as set of columns Relational operations such as natural join ( ), selection (σ), and projection (π) can then be applied to match-sets [START_REF] Codd | A relational model of data for large shared data banks[END_REF]. The answer set of query Q = X ← P on graph G is the match-set of the body projected on head variables: ans(Q, G) = π X M (P, G).

From Query Relaxation To Similarity Search

Query Relaxation. We propose a definition of query relaxation in the line of Hurtado et al [START_REF] Hurtado | Query relaxation in RDF[END_REF] but in a slightly more general form to allow for additional kinds of relaxations. We start from a partial ordering ≤ e on query elements that is consistent with logical inference: e.g., (x,rdf:type,:SciFiFilm) ≤ e (x,rdf:type,:Film). From there, we define the relaxation of query elements.

Definition 1 (element relaxation). The set of relaxed elements of a query element e is the set of immediate ≤ e -successors of e: relax(e) = {e | e ≺ e e }.

If there is no ontological definition, we have relax(e) = ∅ but queries can still be relaxed by removing query elements. In fact, element relaxation is handled as an optional refinement of element removal.

Definition 2 (query relaxation). Let Q = X ← P be a (conjunctive) query. Query relaxation defines a partial ordering ≤ Q on queries. A relaxation step, noted Q ≺ Q Q , transforms Q into a relaxed query Q by replacing any element e ∈ P by relax(e): Q = X ← (P \ {e} ∪ relax(e)). Partial ordering ≤ Q is defined as the reflexive and transitive closure of ≺ Q . The set of relaxed queries is defined as

RQ(Q) = {Q | Q < Q Q }. The relaxation distance of relaxed query Q ∈ RQ(Q)
is the minimal number of relaxation steps to reach it.

A novelty compared to previous work is that an element is not replaced by one of its immediate succesors but by its set of immediate successors. When that set is empty, it allows for the removal of a query element. When that set has several elements, it allows for a more fine-grained relaxation. For example, if class :FullProfessor is a subclass of :Researcher and :Teacher, then triple pattern (x,rdf:type,FullProfessor:) will first be relaxed into pattern {(x,rdf:type,:Researcher),(x,rdf:type,:Teacher)}, which can be further relaxed into either {(x,rdf:type,:Researcher)} or {(x,rdf:type,:Teacher)}.

Another relaxation that is often missing is the replacement of a graph node (URI or literal) by a variable. The difficulty is that a graph node may occur in several query elements, and its relaxation into a variable is therefore not captured by element-wise relaxation. A solution is to normalize the original query in the following way. For each RDF node n occuring as subject/object in the graph pattern, replace its occurences by a fresh variable x n , and add the filter x n = n to the query body. We note N orm(P ) the result of this normalization on pattern P . The node-to-variable relaxation then amounts to the removal of one query element, filter x n = n. For the sake of simplicity, we do not include here the relaxation of property paths [START_REF] Frosini | Flexible query processing for SPARQL[END_REF]. Another kind of relaxation that we let to future work is the gradual relaxation of equality filters.

We define the proper answer of a relaxed query with the same meaning as the "new answers" in [START_REF] Hurtado | Query relaxation in RDF[END_REF], and extend this notion to proper relaxed queries.

Definition 3 (proper relaxed queries). Let Q be a query, and Q ∈ RQ(Q) be a relaxed query, and G be a graph. The proper answers of Q is the subset of answers of Q that are not answers of more specific relaxed queries.

properAns(Q , G) := ans(Q , G) \ {ans(Q , G) | Q ∈ RQ(Q), Q < Q } A proper relaxed query Q is a relaxed query whose proper answer is not empty. We note PRQ(Q, G) the set of proper relaxed queries of Q in G: PRQ(Q, G) := {Q ∈ RQ(Q) | properAns(Q , G) = ∅}.
The objective of query relaxation is to compute as efficiently as possible the proper relaxed queries, their proper answers, and their partial ordering.

Similarity Search. As a contribution to previous work, we lay a bridge from query relaxation to similarity search. Whereas Huang et al [START_REF] Huang | Approximating query answering on RDF databases[END_REF] use a similarity measure to rank the relaxed queries, we propose to use proper relaxed queries to define a semantic similarity that is symbolic rather than numeric. Query relaxation is usually presented as a way to go from a query Q to approximate answers. However, it can in principle be applied to go from an RDF node n to semantically similar nodes. Simply build the original query Q(n) = x ← Norm(P ), where x abstracts over node n, and P is the description of node n, up to some depth in the graph, where n is replaced by x. For every Q ∈ PRQ(Q(n)), properAns(Q ) is a set of similar nodes, and Q describes the semantic similarity as a relaxed description. Compared to similarity (or distance) measures, similarity by query relaxation provides articulate and intelligible decriptions of the similarity. It also provides a more subtle ranking with a partial ordering instead of a total ordering, and the definition of clusters of nodes (proper answers) that share the same relaxed description. Furthermore, several numerical measures can be derived from proper relaxed queries, if desired:

extensional distance: the number of answers in ans(Q , G), i.e. the number of nodes that match what n has in common with nodes in properAns(Q , G); intensional similarity: the proportion of elements in cl(Q) that are in cl(Q ); relaxation distance: the number of relaxation steps from Q to Q .

The latter two may be parameterized with weights on query elements [START_REF] Huang | Approximating query answering on RDF databases[END_REF] and relaxation steps [START_REF] Elbassuoni | Query relaxation for entityrelationship search[END_REF], respectively. Note that those derived measures are total orderings that are compatible with partial ordering ≤ Q on relaxed queries. Indeed, a relaxation step can only increase the relaxation distance, and produce a more general query: hence

Q 1 ≤ Q Q 2 ⇒ cl(Q 1 ) ⊇ cl(Q 2 ) ∧ ans(Q 1 , G) ⊆ ans(Q 2 , G).
Applying query relaxation to semantic similarity is very challenging to compute. The number of relaxed queries grows exponentially with the size of the original query. The description of nodes in real RDF graphs can easily reach 100 triples at depth 1, and grows exponentially with depth. Previous work on query relaxation has so far restricted its application in order to manage the complexity: (a) queries with a few triple patterns only, (b) a RELAX clause to limit relaxations to one or two chosen triple patterns, and (c) a maximum relaxation distance. Our objective is to lift those restrictions and limits to the point where query relaxation can be applied effectively on large queries like node descriptions. The expected benefits are to allow for parameter-free query relaxation, and for similarity search with explanations. We propose a solution that we demonstrate to be significantly more efficient, and that can behave as an anytime algorithm in the hard cases or when responsiveness is important.

Anytime Partitioning of Approximate Answers

We propose a novel approach of query relaxation and symbolic similarity that is based on the iterative partitioning of the set of possible approximate answers. The general idea is that, at any stage of the algorithm, the set of possible answers is partitioned in a set of clusters, where each cluster C is defined by a relaxed query Q , and the subset of ans(Q ) that are not answers of other clusters. Initially, there is a single cluster defined by the fully relaxed query -the query with an empty body -and the set of all possible answers. Each cluster may be split in two parts by using a query element as discriminating criteria. The algorithm stops when no cluster can be partitioned further. The resulting partition is the set of PRQs along with their (non-empty) proper answer. Definition 4. A cluster is a structure C = (X, P , d, E, M, A), where:

-X is the head, and P the body, of the relaxed query Q C = X ← P ; d is the relaxation distance of Q C ; -E is the set of elements that can be used to split the cluster; -M is the match-set of P over graph G;

-A is a subset of ans(Q C , G) = π X M .
A cluster represents a collection of relaxed queries, namely the subset of RQ(X ← P ∪ E) whose body contains P . Relaxed query Q C = X ← P is the most general in the collection, and d is its relaxation distance.

Algorithm 1 details the partitioning algorithm, and Figure 1 shows its first steps on an example query about Science-Fiction films directed by Spielberg. Given a graph and an original query, it normalizes the query body, and initializes the partitioning with a single cluster C init (C0 in Figure 1) that represents the set of all relaxed queries, and covers all possible answers ({A1,A2,A3,A4} in Figure 1). Every iteration picks a cluster C and an available query element e ∈ E in order to split C into C e , and C e . The picked element must be connected to the current relaxed query X ← P in order to avoid building disconnected queries (e.g. e3 is not eligible at C0). C e selects the subset of answers A e ⊆ A where e holds. Element e is moved from available elements to the body, thus restricting the collection of relaxed queries to those containing e. Each matching µ ∈ M is extended to the new element if possible, and removed otherwise: ext(M, e, G) is defined as a join if e is a triple pattern, and as a selection if e is a filter. The set of answers is restricted to those for which there is an extended matching. C e is called the complement of C e because both the collection of relaxed queries and the set of answers are the complement of the respective parts of C e . The relaxed query remains the same, and so does the match-set. The relaxation distance is increased by 1, and element e is replaced by its immediate relaxations relax(e), if any (e1 is replaced by e4 at C2 in Figure 1), so that they are considered in further partitioning. Clusters C e and C e replace their parent cluster C in the partition C, unless their answer set is empty (e.g. the right child of C1 in Figure 1). The number of clusters can only grow, and therefore converges.

Impact of ontology. Ontological definitions such as rdfs:subClassOf axioms allow for more fine-grained relaxations, e.g. replacing query element e1=(f ,rdf:type,:SciFiFilm) by e4=(f ,rdf:type,:Film), instead of simply removing e1. However, the main relaxation work is done by the replacement of URIs and literals by variables, through the removal of filters. For instance, the removal of e3=(f =:Spielberg) allows to relax the query to films by any director. By including the description of Spielberg in the query, and by relaxing that description, the query can be relaxed to films by similar directors, e.g. directors born in the same place and/or having directed similar films. Note that the efficiency of our algorithms is essential to the effective relaxation of such descriptions. In comparison to description relaxation, ontology-based relaxation has a welcome but limited impact.

Complexity. The enumeration-based algorithm evaluates O(2 n ) relaxed queries, given an original query containing n elements, considering element removal only. This number can be lowered by setting a maximal relaxation distance d max , but it grows very quickly with increasing d max . In contrast, assuming p is the number of PRQs, the partitioning algorithm evaluates O(p) queries (binary tree with p leaves). p is bounded by min(N, 2 n ), with N the number of nodes in the graph. As our experiments show (Section 7), p is much smaller than N in practice because many nodes match the same relaxed queries. Note that maximal relaxation distance can be applied in the partitioning algorithm by pruning clusters based on their relaxation distance.

Discussion. The partitioning algorithm does not find PRQs in increasing relaxation distance but it offers a lot of flexibility. The clusters can be split in any ordering, allowing for depth-first or breadth-first strategies or the use of heuristics [START_REF] Huang | Approximating query answering on RDF databases[END_REF]. The choice of the splitting element e is also free, and is independent from one cluster to another. Last but not least, the algorithm is anytime because a partition is defined at all time. If the algorithm is stopped before completion, the partition is simply coarser. Section 7.3 shows that the partitioning algorithm has less latency than enumeration-based algorithms for similarity search.

Optimization with Lazy Joins

The explicit computation of the match-set M of a relaxed query can be intractable, even in simple cases. For example, starting from the description of a film, the relaxed query f ← (f ,rdf:type,:Film), (f ,:actor,p 1 ), . . . , (f ,:actor,p n ) will have in O(N n n ) matchings, assuming there are N films, and each film is related to n actors. For 1000 films related to 10 actors each, it amounts to 10 13 matchings! It is possible to do better because the expected end result is the set of answers A = π X M , whose size is bounded by the number of graph nodes in similarity search. We propose to represent M by a structure -called match-tree -containing several small local joins instead of one large global join. We replace the match-set M of a cluster C = (X, P , d, E, M, A) by an equivalent match-tree T . The match-tree has one node for each element e ∈ P . M is equal to the join of the local match-set M n of all nodes n in T . The initial match-tree is used for the initial cluster C init , and is defined by match-tree T init that has a single node labeled with ( (X), X, ans(X ← ∅, G), X), where (X) is a void query element. During the split of C with a query element e * , the match-set extension ext(M, e * , G) is replaced by LazyJoin(T, root(T ), n * ) (see Algorithm 2), where T plays the role of M , and n * is a new node labeled with (e * , var (e * ) \ var (P ), ans(var(e * ) ← {e * }, G), var (e * ) ∩ var (P )). This "lazy" join consists in inserting n * as a leaf node into T , and in updating local joins M n only as much as necessary to compute A correctly. Figure 2 illustrates lazy join on a richer version of the above example on films. It starts with the match-tree of query f 1 ← (f 1 ,rdf:type,:Film), (f 1 ,:actor,p 1 ), (p 1 ,:sex,:male), (f 2 ,:actor,p 1 ), (f 1 ,:actor,p 2 ), (p 2 ,:sex,:female), and inserts element e * = (f 2 ,:actor,p 2 ) that forms a cycle through f 1 and p 1 . Changes (shown in bold) are propagated from the two nodes that define p 2 and f 2 (see D), and the new leaf is inserted under one of the two nodes as a child (here, under the node defining p 2 ). The insertions of other elements, which led to the first tree in Figure 2, change only one path in the match-tree because they do not introduce a cycle. In Algorithm 2, the computation of ∆ + , ∆ -is used to correctly handle cycles. They are sets of variables of the new query element e * that are not in the match-set of its parent (f 2 in the example), and hence need to be joined with distant nodes in the match-tree. ∆ - propagates up the tree branch of the parent (node (f 1, actor, p2) in Figure 2), and ∆ + propagates up the tree branch of distant nodes (node (f 2, actor, p1)).

∆ + ← ∆ + ∪ ∆ + c ; ∆ -← ∆ -∪ ∆ - c 5: M ← M π∆ c Mc, if
∆ -← ∆ -∪ (∆ * \ D); M ← M π∆ * M * ; parent(n * ) ← n 10: else 11: ∆ + ← ∆ + ∪ (∆ * ∩ D) 12: end if 13: end if 14: ∆ + , ∆ -← ∆ + \ ∆ -, ∆ -\ ∆ + 15: ∆ ← ∆ ∪ ∆ + ∪ ∆ -// update ∆ 16: return ∆ + , ∆ -
When they meet at their common ancestor (node (f 1)), the distant join can be done, and their propagation stops.

Complexity. The dominant factor is the project-and-join operation in lines 5,9 of Algorithm 2. In the worst case, there is such an operation for each node of the match-tree, i.e. one for each element of the relaxed query (m). The cost of the project-and-join depends heavily on the topology of the relaxed query and of the RDF graph. Assuming a tree-shape graph pattern (no cycle) and R triples per predicate, the match-set at each node is a table with at most 2 columns and at most R rows. The space complexity of a match-tree is therefore in O(mR), and the time complexity of each lazy join is in O(mRlogR). In the simpler example on films, m = n + 1, R = N n for property :actor, and R = N for class :Film. The total size is therefore in O(N n 2 ) local matchings instead of O(N n n ). For 1000 films related to 10 actors each, it amounts to 10 5 instead of 10 13 !

Experiments

We have implemented Algorithms 1 and 2, and integrated them to SEWELIS1 as an improvement of previous work on the guided edition of RDF graphs [START_REF] Hermann | An interactive guidance process supporting consistent updates of RDFS graphs[END_REF]. We here report extensive experiments to evaluate their efficiency, in the absolute and relative to other approaches, as well as their effectiveness.

Methodology

We ran all experiments on a Fedora 25 PC with i7-6600U CPU and 16GB RAM.

Algorithms. We compare four algorithms: two baseline algorithms, and two variants of our algorithm. RelaxEnum is the classical approach that enumerates relaxed queries, and computes their answers. NodeEnum does the opposite by enumerating nodes, and computing the associated PRQ as the least common subsumer between the query and the node description [START_REF] Colucci | Common subsumbers in RDF[END_REF]. Partition and Par-titionLJ are our two variants, and differ in that only the latter uses lazy joins.

Parameters. We consider three execution modes. In the NoLimit mode, all PRQs are computed. It is the best way to compare algorithms with different parameters. The MaxRelax mode sets a limit to relaxation distance (not applicable to NodeEnum). The Timeout mode sets a limit to computation time. Datasets. We use three different datasets, Mondial, lubm10, and lubm100. Mondial is a simplification of the MONDIAL dataset [START_REF] May | Information extraction and integration with Florid: The Mondial case study[END_REF] where numbers and reified nodes have been removed because they are not yet well handled by query relaxation. It contains a rich graph of real geographical entities (e.g., countries containing mountains and rivers that flow into lakes), and no ontological definitions. It contains 10k nodes and 12k triples. lubm10 and lubm100 are synthetic datasets about universities, and are based on an ontology introducing class and property hierarchies [START_REF] Guo | LUBM: A benchmark for OWL knowledge base systems[END_REF]. lubm10 contains 315k nodes and 1.3M triples, and lubm100 is 10 times bigger (3M nodes, 13M triples). Both datasets are interesting in our work because they are rich in multi-valued properties, and hence are a challenge for query relaxation.

Queries. For each dataset, we have two sets of queries. The first set is made of queries typically used in query relaxation, having less than 10 triple patterns and having different shapes. The second set is made of object descriptions, having up to hundreds of elements. More details are given below.

Efficiency of Query Relaxation

We here compare all algorithms with (small) queries2 . On Mondial we defined 7 queries having different sizes and shapes. They have between 5 and 21 elements after normalization. On lubm10/100 we reused the 7 queries of Huang et al [START_REF] Huang | Approximating query answering on RDF databases[END_REF]. They have between 3 and 7 elements.

NoLimit mode. Figure 3 compares the runtime (log scale) of all algorithms on all queries of Mondial and lubm10 in NoLimit mode. A few runtimes are missing on Q6 of Mondial because they are much higher than other runtimes. RelaxEnum is sensitive to the query complexity, in particular to multi-valued properties. NodeEnum looks unsensitive to the query complexity but does not scale well with the number of nodes. Partition and PartitionLJ are always more efficient -or equally efficient -and the use of lazy joins generally makes it even more efficient. On lubm10, PartitionLJ is typically one order of magnitude more efficient than RelaxEnum. It can also be observed that PartitionLJ scales well with data size because from Mondial to lubm10, a 100-fold increase in number of triples, the median runtime also follows a 100-fold increase, from 0.01-0.1s to 1-10s. This linear scaling is verified on lubm100 (not shown) where the runtimes are all 10 times higher. We want to emphasize that it is encouraging that the full relaxation of a query over a 1.3M-triples dataset can be done in 4s on average.

MaxRelax mode. In practice, one is generally interested in the most similar approximate answers, and therefore in the relaxed queries with the smaller relaxation distances. It is therefore interesting to compare algorithms when the relaxation distance is bounded. Figure 4 compares RelaxEnum and PartitionLJ on lubm10 queries for increasing values of maximal relaxation distance, here from 1 to 7 relaxations. As expected, the runtime of RelaxEnum grows in a combinatorial way, like the number of relaxed queries, with the relaxation distance. On the contrary, the runtime of PartitionLJ grows more quickly for 1-4 relaxations, and then almost flattens in most cases. The flattening can be explained by several factors. The main factor is that the relaxed queries that are not proper are pruned. Another factor is that query evaluation is partially shared between different queries. That sharing is also the cause for the higher cost with 1-4 relaxations. In summary, PartitionLJ scales very well with the number of relaxations, while RelaxEnum does not. This is a crucial property for similarity search where many relaxation steps are necessary.

Number of relaxed queries. The efficiency of Partition and PartitionLJ is better understood when comparing the number of PRQs to the number of relaxed queries (RQ). Over the 7 lubm10 queries, there are in total 59 PRQs out of 2899 RQs, hence a 50-fold decrease.

Efficiency of Similarity Search

We now consider the large queries that are formed by node descriptions at depth 1 (including ingoing triples), and that include many multi-valued properties. On Mondial we used 10 nodes, one for each class: e.g., country Peru, language Spanish. The obtained queries have 5 to 248 elements (average=61). On lubm10 we used 12 nodes, one for each class: e.g., university, publication. The obtained queries have 5 to 1505 elements (average=201). Main facts and measures are summarized in Table 1. NoLimit mode. PartitionLJ is the only algorithm that terminates under 600s in NoLimit mode, and it does terminate for all queries of both datasets3 . The full runtime has a high variance and a low median, between 0.03s and 269s (average=30s, median=0.13s) for Mondial, and between 0.13s and 535s (average=179s, median=110s) for lubm10. The average number of PRQs is 32 (max=117) for Mondial and 28 (max=52) for lubm10. It is noteworthy that both the runtime and the number of PRQs are relatively close for different datasets with very different sizes. It is also noteworthy that the number of PRQs is very small w.r.t. the size of queries and the number of nodes. It is therefore possible to manually inspect all PRQs, i.e. semantic similarities with all other nodes.

MaxRelax mode. On lubm10, RelaxEnum does not scale beyond 3 relaxations on node descriptions, except for the 3 smallest descriptions. Moreover, using PartitionLJ with a maximum of 10 relaxations, we have observed that only 75 PRQs are produced out of 340 over the 12 queries (0 PRQs for 3 queries), and computation takes 40s on average. To limit the average runtime to 2s, the maximum relaxation distance has to be 1, and then only 3 PRQs are produced out of 340. RelaxEnum and the MaxRelax mode are therefore not effective for similarity search because of their high latency in generating the first PRQs.

TimeOut mode. Although PartitionLJ can compute all PRQs in a reasonable time, it may still be too long in practice. Our anytime algorithm allows to control runtime by timeout. An important question is the latency of the generation of PRQs. Figure 5 shows that most PRQs are generated in a small fraction of the total runtime. For example, 50% PRQs are generated in 30s, and 20% in 2s. This superlinear production of PRQs is confirmed when looking at what happens when moving from lubm10 to lubm100. At timeout=64s, the number of computed PRQs is only divided by 2.6 although the data is 10 times bigger.

Effectiveness of Similarity Search

We assess the effectiveness of PRQs for similarity search with an empirical study that evaluates their use for the inference of property values. The null hypothesis

Algorithm 1 P 3 :Fig. 1 :

 131 Fig. 1: First steps of the partitioning of query Q = f ← {e1,e2,e3} where e1=(f ,rdf:type,:SciFiFilm), e2=(f ,:director,d), e3=(d=:Spielberg), and relax(e1) = {e4} where e4=(f ,rdf:type,:Film).

Definition 5 .Algorithm 2

 52 A match-tree is a rooted n-ary tree T where each node n is labeled by a tuple l(n) = (e, D, M, ∆) where:e is a query element, and var (e) is its set of variables; -D ⊆ var (e) is the set of variables introduced by e; -M is a match-set s.t. dom(M ) ⊇ var (e); -∆ ⊆ dom(M ) is the sub-domain that is useful to the node ancestors. LazyJoin(T, n, n * ) Require: a match-tree T , a current node n in T labeled with (e, D, M, ∆), and a new node n * labeled with (e * , D * , M * , ∆ * ) Ensure: two sets of variables ∆ + , ∆ - 1: ∆ + ← ∅; ∆ -← ∅ 2: for all nc ∈ children(n), labeled with (ec, Dc, Mc, ∆c) do 3: ∆ + c , ∆ - c ← LazyJoin(T, nc, n * ) // recursive call on each child node 4:

Fig. 2 :

 2 Fig.2: Match-tree before and after lazy join with element e * =(f2,:actor,p2).

Fig. 3 :

 3 Fig. 3: Runtime (seconds, log scale) per algorithm and per query for Mondial (left) and lubm10 (right).

Fig. 4 :

 4 Fig. 4: Runtime (seconds) per algorithm and per lubm10 query for increasing maximum relaxation distance (1 to 7). Full height bars represent runtimes over 20s.

Table 1 :Fig. 5 :

 15 Fig. 5: Number of computed PRQs over lubm10 queries (out of 340 PRQs) as a function of timeout(s).

  ∆c or Mc was modified // update of local join 6: end for 7: if D ∩ ∆ * = ∅ then // if this node defines a variable of the new element 8: if n * not yet inserted in T then // insert new node, unless already inserted 9:

This research is supported by ANR project PEGASE (ANR-16-CE23-0011-08).

Source code at https://bitbucket.org/sebferre/sewelis, branch dev, files cnn*

Visit http://www.irisa.fr/LIS/ferre/pub/eswc2018/queries.txt

The ranked list of PRQs and their proper answers is available for the 10 Mondial nodes at http://www.irisa.fr/LIS/ferre/pub/eswc2018/mondial PRQs.txt.

is that using the most similar nodes makes no difference compared to using random nodes. We do not claim here that this value inference method is better than other methods in machine learning, only that PRQs effectively capture semantic similarities. We do not compare our results to other query relaxation algorithms because we have shown in the previous section that they are not efficient enough for similarity search, and because, if given enough time, they would compute the same PRQs. Our experiment consisted in performing value inference for each property p (e.g., :continent) of each country c (e.g., Peru) of the Mondial dataset. Note that a property may have several values (e.g., :language). For each pair (c, p) we computed the PRQs starting with the description of c minus triples (c, p, v) for any value v. Then, we selected the 3 most similar nodes S (e.g., Bolivia, Colombia, and Argentina for Peru) as the proper answers of the most similar PRQs according to intensional similarity (size of the relaxed query). We used S to infer a set of values V for property p using a majority vote. V is compared to the actual set of values to determine precision and recall measures. Table 2 shows the obtained measures for each property and for all properties together, averaged over the countries. The baseline F1-score is obtained by using 3 random countries instead of the most similar nodes. It shows a significant improvement over the baseline, and good results for properties continent and religion. The result is poor for government because values are noisy strings, and for dependentOf because few countries have this property. Overall, 75% of infered values are correct, and 48% of correct values are infered. We obtained very close results when using extensional distance (number of answers) for ranking PRQs.

Conclusion and Perspectives

We have proposed two algorithms that together significantly improve the efficiency of query relaxation and symbolic semantic similarity. In fact, they are efficient enough to tackle the challenging problem of applying many relaxation steps to large queries with hundreds of elements. For a 1M-triples dataset like lubm10 it is possible to explore the entire relaxation space of queries having up to 1500 elements in a matter of minutes. The computation can be stopped at any time while still having a fair approximation of the final result. Many perspectives can be drawn from this work. The partitioning algorithm offers opportunities for strategies and heuristics for choosing the cluster to split and the splitting element. New kinds of element relaxation can be explored, e.g. for the gradual relaxation of URIs and literals. There are potential applications in classification, case-based reasoning, concept discovery, or recommendation.