Member, IEEE Jean-Marc Girault

Member,IEEE EDIC: SPL Denis Kouamé

Sptm

Length and Frequency of bandlimited signals

Keywords: Bandlimited signal, estimator, length, frequency

The main purpose of this letter is to show that measurement of length is an interesting tool to characterize bandlimited signals. We showed the link between the length of a signal and that of the complex instantaneous frequency (CIF). We propose original length and instantaneous frequency estimators which we illustrate by examples.

I. INTRODUCTION

This letter has a dual aim. The first purpose is to familiarise the reader with a technique peripheral to the traditional techniques of signal processing, the second objective is to show that length measurement of bandlimited signals is really an interesting approach.

Although developed at the outset to study signals with the properties of self-similarity or self-affinity such as Tricot chirps (deterministic) or fractional brownian motion (stochastic), we propose applying length measurement to characterize analytic deterministic bandlimited signals.

We therefore initially summarize the length and frequency concepts and then we apply them to the case of analytic deterministic bandlimited signals.

II. LENGTH AND FREQUENCY CONCEPTS

A. Length concept

Measurement of curve lengths, often combined with assessment of fractal dimension, is a major technique to characterize the degree of irregularity of curves or signals [?]. Such length measurement is usually encountered in fields such as the study of traffic on networks, interplanetary magnetic fields, biomedical signals, speech and image compression, to name a few.

The major aspect developed in our study is related to the concept of instantaneous length, also called length elements.

A.1 Length elements and instantaneous velocity

Having specified beforehand that the signals studied are analytic, it is more convenient initially to express a length element --→ dL E in polar coordinates (see Fig. 1). The Euclidean length elements are vector --→ dL E = -→ u ρ dρ+ρdφ -→ u φ and the angular length element vector -→ dζ = ρdφ -→ u φ respectively, where -→ u ρ and -→ u φ are the unitary magnitude and phase vectors respectively, and dρ and dφ are the corresponding small elements respectively. The moduli of the two length elements are expressed by:

   dL E = dζ 1 + ( dρ ρ 1 dφ ) 2 , dζ = ρdφ.
(1)

We will define thereafter the physical sense of the term Q = dρ ρ 1 dφ .

The authors work at LUSSI/GIP ULtrasons, Tours, France. E-mail: jmgirault@univ-tours.fr.

The temporal derivative of this length element is also called instantaneous velocity [?], and can be expressed according to the angular velocity dζ/dt as follows:

v(t) = dL E dt = dζ dt 1 + Q 2 .
(2)

The length concept can also be considered by calculating the local velocity integral of a signal with a limited support [0, T ]. Allowing a short-time approach, the latter is expressed by:

L E = T 0 dL E = T 0 v(t)dt = T 0 ρdφ 1 + Q 2 .
(3)

A.2 Example

Before going into further detail, we analyze a typical example. Let us consider two truncated sinusoids, x 1 (t) and x 2 (t). The two signals have the same amplitude and one has twice the frequency of the other: f 2 = 2f 1 . A geometrical approach, associated with the study of the curves of the two signals, shows that the length of the curve connected to x 2 (t) seems to be the double that of x 1 (t) (see Fig. 2).

At this stage, several features must thus be elucidated:

• Does the length of the first curve correspond to double the length of the second curve?

• Are the frequencies and lengths related?

B. Frequency concept

The frequency concept is often a controversial subject because behind this concept there are three different concepts which are often confused: the concept of frequency which is the inverse of the period (f = 1/T ), the concept of Fourier frequency and instantaneous frequency. We focus here on the temporal definition of the instantaneous frequency of the signal studied x(t) [?], [?].

B.1 Instantaneous frequency

Instantaneous frequency (f L i (t)), also called linear instantaneous frequency (LIF), is written as the derivative of the instantaneous phase of the analytic signal z(t) associated with the signal x(t), and applies only to mono-component signals. Linear instantaneous frequency is defined as follows:

f L i (t) = 1 2π dφ(t) dt ,
where φ(t) is the instantaneous phase of the analytic signal. The analytic signal is expressed by:

z(t) = x(t) + jy(t) = ρ(t)e jφ(t) ,
where y(t) = HT (x(t)) is the Hilbert transform of the signal studied x(t). However, there is a more general definition of instantaneous frequency, i.e. complex instantaneous frequency. As will be seen below, this is the central point of our study.

B.2 Complex instantaneous frequency

The concept of complex instantaneous frequency (CIF) was introduced by Hahn [?] in order to design oscillators. The CIF (f C i (t)) is obtained by calculating the temporal derivative of the logarithm of the analytic signal z(t):

f C i (t) = 1 2π d dt ln(z(t)) .
After calculation, it is easily demonstrated that the CIF is expressed according to a coefficient σ f (t) image of the band-width and according to the LIF:

f C i (t) = σ f (t) + jf L i (t) = |f C i (t)|e jθ(t) ,
where

   |f C i (t)| = σ 2 f (t) + f L i (t) 2 = f L i (t) 1 + Q 2 (t), θ(t) = tan -1 (1/Q(t)), (4)
where

     σ f (t) = 1 2πρ(t) dρ(t) dt , f L i (t) = 1 2πρ(t) dζ(t) dt ,
and where

Q(t) = σ f (t) f L i (t) = 1 ρ(t) dρ(t) dφ(t) .
Note that in the case of narrow band signals (Q(t) ≪ 1 involving θ → π/2), the LIF can be obtained either by evaluating the modulus of the CIF or directly by taking the imaginary part of the CIF (which is always consistent):

   f L i (t) ≈ |f C i (t)| if Q(t) ≪ 1, f L i (t) = Im f C i (t) ∀ Q(t), (5)
where Im() represents the imaginary part.

C. Relationship between length and frequency

After having introduced the various concepts, and using (1), ( 2), (4) it can be seen that the length element dL E is directly connected to the modulus of the CIF:

dL E (t) dt = 2πρ(t)|f C i (t)|. ( 6
)
In the example above, the length measurement of the two sinusoids (implying Q(t) = 0 because of its narrow band nature) imposes equality between the LIF and the modulus of the CIF. Furthermore note that under this assumption the signal length is expressed by [?]:

L E (t) = 2πT ρ(t)f L i (t), (7)
where f L i (t) is the instantaneous frequency evaluated over the interval [0, T ] corresponding to the duration of the signal studied.

Consequently, eq.( 7) confirmes that measuring the length of a narrow band signal is a matter of evaluating the LIF.

III. ESTIMATORS

Extending this to evaluation of numerical signals we at the same time propose a length estimator and frequency estimators. We first consider the case of discrete analytic bandlimited signals defined by: z

(n) = x(n) + jy(n) = ρ(n)e jφ(n) ,
where y(n) = HT (x(n)).

A. Length estimator

Several length estimators are described in the literature [?], [?]. Here we will use the generalized Euclidean length element estimator referred to as d LE (n, k) and expressed by:

d LE (n, k) = z(n + k) -z(n) k = 1 k k p=1 z(n + p) -z(n + p -1) , (8)
where k, referred to as a gauge, plays the role of zoom and n is the current time.

From eq.( 8) several comments can be made:

• Eq.( 8) shows a local average operation of the increment function (z(n + p) -z(n + p -1)). Note that LE (n, k) = n i=1 d LE (i, k). • Eq.( 8) is an extended version of the classical Euclidean length element estimator: d LE (n) = z(n + 1) -z(n) • In the case of analytic signals, estimators proposed by Higuchi [?], Burlaga and Klein [?] are a global version of eq.( 8)except for a coefficient 1/k.

Knowing that the increment function (z(n+k)-z(n)) is a first order interpolation operation (straight line between two consecutive samples), length measurement is equivalent to a low-pass filter operation. Note that measuring d LE (n, k) comes down to evaluating d LE (n) at a rate of 1/k times the original sample rate, this is a decimation operation. Finally, measured length is not that of the studied signal, but that of a decimated and first-order interpolated signal (low-pass filter). Although we chose to limit ourselves to a first-order interpolation polynomial, this interpolation can obviously also be extended to higher orders or even to other families of interpolation polynomials.

B. Frequency estimators

In the case of discrete signals eq.( 6) can be rewritten taking into account the estimate of the complex instantaneous frequency:

| fi C (n, k)| = 1 2πρ(n) d LE (n, k) T s , (9)
where T s = 1/f s is the sampling period. The estimator | fi C (n, k)| can be written in the same form as in eq.( 4):

| fi C (n, k)| = (σ f (n, k)) 2 + ( fi L (n, k)) 2 , ( 10
)
where (see Appendix)

           σf (n, k) = 1 2πkTs 1 -ρ(n+k) ρ(n) , fi L (n, k) = 1 πkTs ρ(n+k) ρ(n) sin(πkT s fi L (n, k)) ,
and where fi L (n, k) expresses an average frequential quantity evaluated from the last k values (see appendix).

It should be noted that: 1) by converging to the continuous case, i.e. by considering the high sampling frequency (f s → ∞) compared with the highest frequency of the signal, eq.( 10) becomes:

lim fs→∞ | fi C (n, k)| = σ2 f (n, k) +    fi L (n, k) ρ(n + k) ρ(n)    2 ,
2) from 1) and using the minimum integer value of the gauge k = 1, eq.( 10) tends to eq.( 4):

lim fs→∞ | fi C (n, 1)| = σ2 f (n, 1) + fi L (n, 1) 2 ,
where fi L (n, 1) = f L i (n + 1) ρ(n+1) ρ(n) . Note that σf (n, 1) is exactly the discrete form of σ f (t) whereas fi L (n, 1) is only for a narrow band hypothesis: fi L (n, 1) ≈ f L i (n + 1). 3) By considering the narrow band assumption only, i.e. ρ(n + k)/ρ(n) ≈ 1 ⇒ σf (n, k) ≈ 0, eq.( 10) becomes:

| fi C (n, k)| ≈ fi L (n, k) sinc(πkT s fi L (n, k)) . (11)
Owing to the periodic nature of eq.( 11),

| fi C (n, k)| = 0 for any kα (n) = αf s / fi L (n) with α = 1, 2, 3, ....
Therefore it is possible to evaluate the mean instantaneous frequency by detecting zero-crossings. In particular, estimation of the first minimum of the eq.( 11), i.e. k1 (n

) = min {k / fi C (n, k) = 0} , also leads to: fi L (n) = f s k1 (n) . ( 12
)
This is the first estimator of the mean instantaneous frequency. As it has been suggested above, this can be extended to the detection of several zero-crossings and even provide an additional average. 4) by considering 2) and 3), eq.( 10) becomes:

lim fs→∞ | fi C (n, 1)| = f L i (n + 1). (13)
The latter estimate which constitutes our second estimator is the discret form of eq.( 5).

C. Examples

To illustrate the behavior of the proposed estimators (eq.( 12), eq.( 13)), we consider two examples:

• A complex sinusoid embedded in a white complex noise η for different SNR, defined by: z(t) = Aexp(2πjf L i t) + η(t). • A bandlimited FM signal (gaussian envelope and sinusoidal frequential law) defined by: z(t) = exp(-(t -t 0 ) 2 /(2σ 2 0 ))exp 2πjtf c + jβcos(2πtf 0 ), where t 0 = 0.5 s, β = 40π, σ 0 = 0.0194, and where f 0 = 4 Hz, f c = 1500 Hz and f s = 10000 Hz.

By way of illustration, Fig. 3, presents the evolution of | fi C (n, k)| (9) or d LE (n, k) (8) in the case of sinusoids embedded in a white noise. It can be seen in Fig. 3 that for weak SNR the second estimator fi C (n, 1) is strongly biased whereas the first is not. Moreover it is shown that the first estimator is less sensitive to noise than the second because it represents an average estimate of instantaneous frequency.

In addition, Fig. 3 shows that for weak SNR (< -5 dB), neither estimator provides a more precise value of the frequency. Finally, Fig. 4 shows the sinusoid law of the FM signal (gaussian envelope) for both estimators.

In the case of filtered random signals [?], for example 1/f α noise, it is possible to establish the link between deterministic and random narrow band signals and to provide additional information on fractal features.

IV. CONCLUSION

In conclusion, we have shown that a simple geometrical approach makes it possible to illustrate the dependence existing between the length of a signal and its complex instantaneous frequency. Furthermore, we have demonstrated here that it is possible to estimate the average instantaneous frequency by length measurement.

Appendix

By using eqs.( 8),(9), eq.( 10) becomes:

| fi C (n, k)| = ρ(n) -ρ(n + k)e j∆φ 2πkT s ρ(n) , where ∆φ = φ(n + k) -φ(n). | fi C (n, k)| =   ∆ ρ 2πT s ρ(n)   2 +    ρ(n + k) ρ(n) sin(∆φ/2) πkT s    2 , where ∆ ρ = ρ(n + k) -ρ(n), with ∆φ/2 = πT s fi L (n, k) = πT s   n+k l=0 f L i (l) - n l=0 f L i (l)   ,
and where fi

L (n, k) = 1 k k l=1 f L i (n + l).

Re(y)

Im(y) Sinusoid ( , f 1 ) ρ

ρ d 0 dL E φ d ρ u φ u dL = ρ φ d d ρ E + u ρ u φ φ e ρ z(t)= (t) j (t) ρ (t) φ (t)
L( ) x 1 E L( ) x E 2 LENGTH SIGNAL Sinusoid ( , f 2 ) ρ f = 2 f 1 2 x 1 T 0 x 2 T 0 Fig. 2.
Lengths of two sinusoids of same amplitude and different frequencies.

Fig. 1 .

 1 Fig. 1. Polar representations. a) Polar representation of a modulated signal. b) Polar representation of a length element.

Fig. 3 .

 3 Fig. 3.Instantaneous frequency estimate for sinusoids embedded in white noise for various SNR (-10 dB, up to 30 dB). The solid line curves are disturbed signals whereas the dotted lines represent only the white noise.

Fig. 4 .

 4 Fig. 4. Frequency estimation of a bandlimited FM signal. a) Spectrogram of the analyzed signal, b) zoom of the real part of the analytic signal z(t) (noted Re(z(t))) delimited in the spectrogram, c) first estimator: Bidimensional plan of | fi C (n, k)|, d) second estimator | fi C (n, 1)|.

List of Figures


Jean-Marc Girault

Souad Oudjemia

Iulian Voicu

Multi-Scale Similarity Entropy as a Complexity Descriptor to discriminate Healthy to Distress fetus

Keywords: Entropy, Similarity, complexity, time series

This paper deals with the discrimination between suffering foetuses and normal foetuses by means of a multi-scale similarity entropy. Sample entropy and similarity entropy are evaluated in multi-scale analysis on foetal heart rate signals. Without multi-scale analysis, our results show that only the similarity entropy differentiate suffering foetuses to normal foetuses. Furthermore with the multi-scale analysis, our results show that both the sample entropy and the similarity entropy can discriminate the distressed foetuses to normal foetuses. In all cases the similarity entropy outperforms the sample entropy that is encouraging for another biomedical applications.

INTRODUCTION

One of the most important purpose in foetal monitoring antepartum is the detection of the foetal distress since it can help the obstetrician to rapidly decide whether it is necessary or not to deliver the foetus by caesarean section. However this is not the only one reason that explains its usefulness since the obstetrician needs also to understand the fundamental reasons leading to such a foetal distress. This quest was made difficult due to the wide range of possible pathologies and the different degrees of severity and symptoms encountered during the gestational period. Although the foetal distress was in a general way characterized by a reduction of the maternal-foetal respiratory exchanges leading the foetus metabolism to an anaerobic state, all the underlying reasons were not yet elucidated.

Recently, it has been shown by [START_REF] Liston | Surveillance du bienetre foetal: Directive consensus d'antepartum et intrapartum[END_REF] that a foetal heart rate (FHR) monitoring completed by a certain numbers of indicators could reduce the morbidity and mortality rate up to 7 per thousand. Among all these proposed indicators, the most simple and commonly used were those based on the estimation of the FHR acceleration-deceleration and based on the short and mean terms FHR variability to name a few. The second class of indicators was based on the assessment of the FHR complexity. The most well-known descriptors were based on different kinds of entropy as for instance the approximate entropy or the sample entropy (SamEnt). These descriptors developed for characterizing time series without any a priori information on the nature of the underlying system, measured the degree of regularity of the analysed time series. These measures were realized by evaluating the probability of finding similar m-patterns that are templates composed of m samples.

Recently, the work performed by [START_REF] Costa | Multiscale entropy analysis of complex physiologic time series[END_REF] showed that the multi-scale analysis could still improve the characterization of physiological time series. This multiscale analysis of entropy was then applied by [START_REF] Ferrario | Comparison of Entropy-Based Regularity Estimators: Application to the foetal Heart Rate Signal for the Identification of foetal Distress[END_REF], [START_REF] Ferrario | Complexity analysis of the foetal heart rate variability: early identification of severe intrauterine growth-restricted foetuses[END_REF] for studying the suffering foetuses. This work that was the starting point of our study showed that it was possible to discriminate suffering foetuses to healthy foetuses.

Our study aimed to improve the differentiation between normal and suffering foetuses by investigating deeper the links between m-patterns. To do so we investigated the similarity entropy previously introduced by [START_REF] Xie | Measuring time series regularity using nonlinear similarity-based sample entropy[END_REF] and we extended its definition with a multi-scale point view. By assessing the multi-scale similarity entropy, we showed that it was possible to better discriminate healthy foetuses to suffering foetuses in comparison to the multi-scale sample entropy.

To prove it, we firstly present the materials used to measure the foetal heart rate (FHR), secondly we present the multi-scale similarity analysis and thirdly we present some results derived from our dataset. We close this research work by a discussion and a conclusion.

MATERIALS

Our system was composed of a personal computer and our home-made Actifoetus unit. The Actifoetus unit contained three groups of four transducers and a Doppler acquisition board. The transducers exploring the foetal heart were non-focused and mono-element. They were circular in shape, with a diameter of 13.5 mm and an acoustic power of 1 mW/cm 2 . Geometrically, the transducers were located at the center of gravity and at the tops of an equilateral triangle of sides measuring 40.7 mm.

The transducers were placed on the mother's abdomen. They transmitted a sinusoidal pulse at 2.25 MHz with a pulse repetition frequency of 1kHz. The wave was propagated through the mother's abdomen towards the foetal heart. The backscattered signal was recorded from five different depths, annotated D1... D5. Note, only one channel was considered in the present study.

The ultrasound signal received was converted into an electrical signal and amplified to compensate the attenuation of 1 dB/cm/MHz. The signal was then The Doppler signals were acquired at CHRU "Bretonneau" Tours, France. The consent of each patient was obtained and the study was approved by the ethics committee of the Clinical Investigation Centre for Innovative Technology of Tours 806 CHRU of Tours). Patients are older than eighteen years and pregnancy was singular. Six patients (three normal foetuses and three suffering foetuses) were included in this study. Foetuses whose gestational age ranged from the 25th to the 39th week were monitored during 30 minutes. FHR was evaluated as proposed by [START_REF] Voicu | Improved estimation of the foetal heart rate using directional Doppler signal and YIN[END_REF] that is every 250 ms leading to 7200 samples for a recording of 30 minutes.

METHODS

From FHR recordings, each time series x(n) composed of M = 7200 points were represented by a vector X. To catch the fluctuations present in the time series at different scales, the multi-scale analysis was introduced. This method consisted in evaluating approximate versions of the original time series from a local average of neighbouring points. This procedure proposed by [START_REF] Costa | Multiscale entropy analysis of complex physiologic time series[END_REF] is named "coarse-grained". The new time series composed of M/α samples at the scale α writes:

y α (k) = kα i=(k-1)α+1 x i , (1)
for 1 ≤ k ≤ M/α, y 1 (k) = x(k) being the original time series. To ensure the same length for each time series after the coarse-grained process, time series were interpolated by a factor α. The vector of the interpolated times series, composed of M samples, was then obtained. For each vector a short term similarity measure was performed on a sub-vector Y α composed of N = 720 points (3 min.).

The method that was tested here was based on a non multi-scale analysis initially proposed by [START_REF] Xie | Measuring time series regularity using nonlinear similarity-based sample entropy[END_REF]. Unlike conventional approaches where the probability of finding a m-pattern whose amplitude was similar, in this method the probability of finding similar centred m-patterns was evaluated instead. This centring process that seems to the untrained eye looks completely benign enabled to compare similar m-patterns located everywhere into the time series while for conventional approaches only m-patterns located at the same amplitude were accounted. The originality of our proposed method was to extend the method proposed by [START_REF] Xie | Measuring time series regularity using nonlinear similarity-based sample entropy[END_REF] with a mutli-scale point of view. Note that a preliminary study on this subject was presented by [START_REF] Voicu | Multi-scale Similarity Entropy as a New Descriptor to Differentiate Healty to Suffering foetus[END_REF].

In this paper two kinds of entropy were evaluated: the sample entropy (Sa-mEnt) and the sample entropy of centred m-patterns that was named similarity entropy (SimEnt). This pattern centring process came down to remove the FHR base-line of the FHR, it was similar to a detrending process.

To exemplify, an illustration was proposed in Fig. 1. At the top of Fig. 1 a part of the sample entropy process was presented. In this case, the probability of finding the first 2-pattern was evaluated and only two 2-patterns were found similar. At the bottom of Fig. 1 a part of the similarity process was presented. In this case the probability of finding the first centred 2-pattern was evaluated and eight centred 2-patterns were found similar. The similarity seeking process was thus a matter of studying fluctuations around the trend.

From the time series vector Y α , a vector sequence was formed:

Y (m) α,i = {y α (i), y α (i + 1), ..., y α (i + m -1)} - Ȳ(m) α,i (2)
with

Ȳ(m) α,i = 1 m m-1 l=0 y α (i + l) for i ranging from 1 to N -m + 1. Y (m) α,i
represents m consecutive y α values starting from the ith point, m being the length of the pattern. The distance d

(m) i,j between Y (m) α,i and Y (m)
α,j is defined as:

d (m) i,j = d Y (m) α,i , Y (m) α,j
= max k∈(0,m-1)

y α (i + k) -y α (j + k) . (3)
The average degree of similarity between Y (m) α,i and its neighbouring vectors Y (m) α,j within tolerance r can then be defined as

B (m) i (r) = 1 N -m -1 N -m j=1,j =i Θ(d (m) i,j -r) ( 4
)
where Θ is the Heaviside function, j ranges from 1 to (N -m) and j = i to exclude self-matches. When vector Y (m) α,i is very close to its neighbouring vector Y (m) α,j , that is when the distance d (m) i,j < r, then a pattern match occurs. Finally, define the function B (m) (r) as follows:

B (m) (r) = 1 N -m N -m i=1 B (m) i (r). (5)
Similarly, form the vector sequence

Y (m+1) α,i
and get the function A (m) (r) where

A (m) (r) = 1 N -m N -m i=1 A (m) i (r), (6)
A (m) i (r) = 1 N -m -1 N -m j=1,j =i Θ(d (m) i,j -r). (7)
The similarity entropy SimEnt(m, r, N ) for a finite dataset of N samples writes at a scale α:

SimEnt(α, m, r, N ) = log(B (m) ) -log(A (m) ). ( 8
)
Note that the similarity entropy possesses the same definition of the sample entropy, the one difference was on the definition of the m-patterns which were centred for the similarity entropy.

APPLICATION TO THE FOETAL HEART RATE SIGNAL

From our dataset composed on six recordings of 30 minutes, three recordings corresponded to healthy foetuses and three to distressed foetuses. As an illustration, it was reported on Fig. 2 two FHRs. On the top of Fig. 2 was reported the FHR of a normal foetus while in the bottom of Fig. 2 was depicted a FHR of a suffering foetus. In the both cases, the FHR fluctuated around 135 beats per minutes. Note that the FHR of the suffering foetus seemed to be more variable. For convenient, each FHR recordings were centred and normalized. For each recordings, a short term analysis was performed on the vector Y (m) α,i by using a sliding window composed of 720 points with an overlap of 97 %. SamEnt(α, m, r, N ) and SimEnt(α, m, r, N ) were evaluated for each extracted signal at different scale α ranging from 1 to 6 and for m = 2, r = 0.1, N = 720. For the healthy group and for the suffering group, each estimation of sample entropy and similarity entropy were gathered in a view to estimate the mean and the standard deviation of each estimation. In Fig. 3 was reported such estimations. On the top of Fig. 3, the sample entropy for normal and suffering foetuses was reported in regards with the scale. On the bottom of Fig. 3, the similarity entropy for normal and suffering foetuses was reported in regards with the scale. In both cases, the sample entropy and the similarity entropy decreased as the scale increased. This behaviour seemed corroborate the fact that as the scale increased, the time series became smoother thus reducing its complexity. However this behaviour was not confirmed by the work of [START_REF] Ferrario | Comparison of Entropy-Based Regularity Estimators: Application to the foetal Heart Rate Signal for the Identification of foetal Distress[END_REF][START_REF] Ferrario | Complexity analysis of the foetal heart rate variability: early identification of severe intrauterine growth-restricted foetuses[END_REF] where the sample entropy increased with the growing of the scale.

In any event, note that it was impossible to discriminate suffering to normal foetuses by comparing the sample entropy for each scale value independently whereas it was the case for the similarity entropy with a scale ranging from 1 to 2. Finally, note that both the sample entropy and the similarity entropy were higher for distressed foetuses than for healthy foetuses. This point seemed to be corroborated by the more fluctuating nature of FHR for suffering foetuses than for normal foetuses as obtained in Fig. 2.

With this in mind, we can now turn to fully take into account the multiscale analysis. As proposed by [START_REF] Ferrario | Complexity analysis of the foetal heart rate variability: early identification of severe intrauterine growth-restricted foetuses[END_REF], it seemed much more interesting to evaluate the deviation of both descriptors at different scale. To do so we evaluated the relative error between similarity entropies and the sample entropies at different scales α and α ′ :

RE 1 (α, α ′ ) = SimEnt(α) -SimEnt(α ′ ) SimEnt(α) , (9)
RE 2 (α, α ′ ) = SamEnt(α) -SamEnt(α ′ ) SamEnt(α) , (10)
where SimEnt(α) and SamEnt(α) were the mean values at each scale.

In table 1, RE 1 (1, 6) and RE 2 (1, 6) were reported. Findings derived from table 1, showed that it was possible to separate healthy to suffering foetus by using α = 1,α ′ = 6. In such a case, a deviation of 56% -41% = 15% and a deviation of 74% -51% = 23% were obtained, respectively. By using the multiscale analysis, it was easier to differentiate with similarity entropy than with sample entropy. This result confirmed that the slope of the similarity entropy obtained for the normal and the suffering foetus were very different (see the bottom of Fig. 3) to enable the discrimination.

DISCUSSION AND CONCLUSION

The multi-scale analysis of similarity or sample entropies, has shown its efficiency to discriminate suffering to normal foetuses. In this study this was the multi-scale similarity entropy that gave the best performances and thus seemed to be more adapted to our dataset. Even if our findings did not match exactly with the results derived from the work [START_REF] Ferrario | Comparison of Entropy-Based Regularity Estimators: Application to the foetal Heart Rate Signal for the Identification of foetal Distress[END_REF][START_REF] Ferrario | Complexity analysis of the foetal heart rate variability: early identification of severe intrauterine growth-restricted foetuses[END_REF], from our point of view it did not mean that one of this study was wrong, it only meant that pathologies, degrees of severity and gestational ages were different.

In any event, the superiority of the similarity entropy compared to the sample entropy reveals that the fluctuation around the FHR trend was the discriminating information. This result, that is completely novel in this field, is very encouraging for a discrimination purpose.

However, this work constitutes a first step in order to better understand the underlying processes leading to the foetal distress. in progress will consist to test our multi-scale descriptors to a larger corpus of recordings.

Figure 1 :

 1 Figure 1: Illustration of the fundamental difference between sample and similarity entropies. Top of the figure, identification of the first 2-pattern into the time series for the sample entropy process. Bottom of the figure, identification of the first centred 2-pattern into the time series for the similarity entropy process.

Figure 2 :

 2 Figure 2: Two foetuses heart rate derived from our dataset. Top of the figure, foetal heart rate of a normal foetus. Bottom of the figure, foetal heart rate of a distressed foetus.

Figure 3 :

 3 Figure 3: Multi-scale analysis of the sample and similarity entropies (2-pattern) for normal and suffering foetuses. Top of the figure, sample entropy versus scale for normal foetuses (dot line) and suffering foetuses (continuous line). Bottom of the figure, similarity entropy versus scale for normal foetuses (dot line) and suffering foetuses (continuous line).

Table 1 :

 1 The second step which is foetus State RE 2 (1, 6) RE 1[START_REF] Liston | Surveillance du bienetre foetal: Directive consensus d'antepartum et intrapartum[END_REF][START_REF] Voicu | Improved estimation of the foetal heart rate using directional Doppler signal and YIN[END_REF] Relative error of the similarity and sample entropies for different scales (α = 1, α ′ = 6).

	Healthy	41 %	51 %
	Suffering	56 %	74 %

Email address: jean-marc.girault@univ-tours.fr (Jean-Marc Girault)Preprint submitted to International Journal of Systems, Control and CommunicationsOctober 22, 2014


J M Girault
email: jmgirault@univ-tours.fr

D Kouamé

A Ouahabi

F Patat

Estimation of the blood Doppler frequency shift by a timevarying parametric approach

Keywords: AR, Doppler frequency shift, Time-varying, Parametric method

Doppler ultrasound is widely used in medical applications to extract the blood Doppler flow velocity in the arteries via spectral analysis.

The spectral analysis of non-stationary signals and particularly Doppler signals requires adequate tools that should present both good time and frequency resolutions. It is well-known that the most commonly used time-windowed Fourier transform, which provides a time-frequency representation, is limited by the intrinsic trade-off between time and frequency resolutions. Parametric methods have then been introduced as an alternative to overcome this resolution problem. However, the performances of those methods deteriorate when high non-stationarities are present in the Doppler signal. For the purpose of accurately estimating the Doppler frequency shift, even when the temporal flow velocity is rapid (high non-stationarity), we propose to combine the use of the time-varying auto-regressive method and the (dominant) pole frequency. This proposed method performs well in the context where non-stationarities are very high. A comparative evaluation has been made between classical (FFT based) and auto-regressive (both block and recursive) algorithms. Among recursive algorithms we test an adaptive recursive method as well as a time-varying recursive method.

Finally, the superiority of the time-varying parametric approach in terms of frequencies tracking and of delay on the frequency estimate is illustrated on both simulated and in vivo Doppler signals.

Introduction

Doppler ultrasound provides a noninvasive assessment of the hemodynamic flow condition within blood vessels and cardiac cavities. Diagnostic information is extracted from the Doppler blood flow signal, which results from backscaterring of the ultrasound beam by moving red blood cells. Because of the random spatial distribution of red blood cells and the dynamics of the cardiovascular system, the Doppler signal is a time-varying random signal. The timefrequency distribution (TFD) of the Doppler blood flow signal is most often computed using time-windowed Fourier transform, and the resulting TFD is called the spectrogram. The spectrogram is computed on the assumption that the signal to be analyzed is stationary during a short time interval. It has the advantages of fast computation, but it has the main shortcoming of the trade-off between time and frequency resolutions. To increase the frequency resolution, a longer time interval is required. Thus, the stationary assumption may not be valid. In addition, the spectral components occurring in a large interval will be smeared in the time domain, resulting in a decreased time resolution. To partly solve this problem, autoregressive (AR) modeling has been used as an alternative technique [START_REF] Kay | Spectrum analysis -A modern perspective[END_REF], [START_REF] Vaitkus | A comparative study and assessment of Doppler ultrasound spectral estimation techniques, Part I : Estimation methods[END_REF]. In fact, the frequency resolution can be enhanced, since model-based methods implicitly extrapolate the data outside the window under consideration. The problem is then shifted to that of the model identification; in particular, the order and the parameters of an AR process that best describes the limited duration of the Doppler signal must be estimated.

Parametric modeling

Following the principle of the timewindowed Fourier transform (spectrogram), the power spectral density (PSD) at any given time can be also obtained by applying classical autoregressive (AR) modeling.

Nonstationary Autoregressive modeling

The AR method consists of modeling the Doppler signal as the output of a linear filter driven by a white noise. This filter, referred to as AR, is a linear combination of the previous samples (Regressive) of the output itself (Auto). For examples, one can refer to [START_REF] Kay | Spectrum analysis -A modern perspective[END_REF], [START_REF] Vaitkus | A comparative study and assessment of Doppler ultrasound spectral estimation techniques, Part I : Estimation methods[END_REF] and [START_REF] Ljung | Recursive Identification: Theory for the users[END_REF]. Equation of a classical AR complex process, in a nonstationary context, is given by:

x (n)   a i (n )x (n  i)  u(n) i  1 p  (1)
where a i (n) are AR complex parameters, p is the AR order (or the number of AR parameters), u(n) is a white complex noise and n is the sample time.

Depending on the type of nonstationaries present in the signal, two cases can be envisaged for modeling the Doppler signal. First, when the nonstationaries of x(n) are low, the AR parameters can be reached by using an algorithm applied directly to the parameters a i (n) of expression [START_REF] Kay | Spectrum analysis -A modern perspective[END_REF]. This method is referred to as the adaptive algorithm.

Secondly, when the nonstationarities are strong, we can describe the AR parameters a(n) by using deterministic functions; the parameter estimation algorithm is not applied directly to the parameters but to the coefficients of the deterministic functions. This method is called the timevarying algorithm.

Time-varying autoregressive modeling

Now, suppose that the time-varying parameters are linear combinations of a set of deterministic basis time-varying functions F g (n). Time-varying AR parameters are expressed by:

a i ( n)  a i, g F g ( n) g  0 m  (2)
where a i,g are AR constant complex coefficients and m is the dimension of the time functions basis F g (n). Thus, a time-varying AR model for a nonstationary sample signal x(n) is [START_REF] Grenier | Time-dependent ARMA modeling of nonstationary signal[END_REF], [START_REF] Liporace | Linear estimation of nonstationary signal[END_REF], [START_REF] Girault | Time-varying autoregressive Spectral estimation for ultrasound attenuation in tissue characterization[END_REF]:

x( n)   a i,g F g (n  i )x(n  i )  u(n ) g  0 m  i 1 p  (3 )
The number of unknowns is multiplied by (m+1), but this seems a small price to pay compared to the benefit of keeping the problem linear. Several base functions [START_REF] Grenier | Time-dependent ARMA modeling of nonstationary signal[END_REF] have been used in different fields, for example in speech signal processing and in tissue characterization [START_REF] Girault | Time-varying autoregressive Spectral estimation for ultrasound attenuation in tissue characterization[END_REF]. Here we use one of the most common basis: the power of time functions [START_REF] Grenier | Time-dependent ARMA modeling of nonstationary signal[END_REF]:

F g (n )  1 g! n N     g (4)
where F 0 (n)=1 and N is the sample number in the analyzed signal.

Parameters estimation

Many algorithms can be used to compute AR parameters required for the spectrum estimation. We can use either batch (block) or recursive (sequential) techniques. Here, we focus on the most popular ones: the adaptive Recursive Least-Squares (RLS) and the weighted time-varying RLS algorithms [START_REF] Ljung | Recursive Identification: Theory for the users[END_REF], [START_REF] Girault | Time-varying autoregressive Spectral estimation for ultrasound attenuation in tissue characterization[END_REF]. The expression of both the weighted time-varying RLS algorithm and adaptive RLS algorithm are given, by rewriting equation (1), by:

x (n)   n  1 H    u( n) (5)
where the superscript H denotes the hermitian transpose operator and the hat denotes the estimate values. The recursively estimated, the AR parameters are given by:

  n    n  1  P n  n *  n (10)  n  x n   n H   n  1 (11) P n  1  P n  1  P n  1  n *  n H P n  1    n H P n  1  n *       (12)
where   is the estimated parameters vector, P n the gain and  n the prediction error. The superscript * denotes the conjugation,  n is the observation vector and  the forgetting factor . Note that the so-called forgetting factor  is used to give more weight to the recent data than the past data during the estimation process. It is chosen such as 0<<1.

In the adaptive case, the observation vector and the AR parameters become :

 n   n   x( n  1 ), ...,  x (n  p )   T    a  1 , ..., a  p     T      (6)
where T denotes the transpose operator.

In the time-varying case, the observation vector and the AR parameters become :

 n  1 H   n  1 H V V  F 0, n  1 ,..., F m ,n  p   T    a  1
Due to the recursive nature of this algorithm, first a transient region appears and secondly an initialization of the gain P n and AR parameters is required. A standard initialization value of the gain is P 0 = I (I is an identity matrix) and 10.

In practice, the difference (called the prediction error) between the measured signal and its model is weighted by an exponential window that moves with the data: this results both in a better estimate of the model parameters and in the capability to track varying signals. This algorithm updates the parameters vector upon acquisition of a new sample without inverting a matrix. Note that the performances of such algorithms depend strongly upon the choice of the forgetting factor , which controls the length of the prediction error and therefore the amount of memory in the system [START_REF] Ljung | Recursive Identification: Theory for the users[END_REF].

Since the main purpose of our study is to extract a piece of information which resumes the temporal evolution of the Doppler frequency, we use a low AR order. This approach is slightly different from those based on a singular value decomposition (SVD) as proposed in [START_REF] Forsberg | On the usefulness of singular value decomposition -ARMA models in Doppler ultrasound[END_REF] and [START_REF] Fort | Adaptive SVD-Based AR model order determination for timefrequency analysis of Doppler ultrasound signals[END_REF]. For example, in a complex case, a first order AR model can efficiently estimate the frequency which corresponds to the pole of the Doppler signal. This is possible in the particular case of high signal-to-noise ratio as encountered in continuous Doppler.

In this way, it is possible to calculate either an instantaneous spectrum or a single pole frequency, hence to study the spectral characteristics of Doppler signals even in non-stationary conditions.

Spectral estimation

From known AR parameters, a standard approach to evaluate an instantaneous frequency consists of computing first the whole spectrum, then estimating a particular frequency (the centroid frequency or the maximum energy frequency). Accordingly, the power spectral density S xx (f,n) of a time-varying AR process (see eq. ( 1)) is given at each time n by:

S xx (f , n )   u 2 ( n) 1  a i (n )e  j2 if i 1 p  2 (13) S xx (f , n )   u 2 ( n) ( z(n )  z i (n )) i1 p  z e 2 j  f 2 ( 14
)
where f is the normalized frequency -0.5  f  0.5,  u 2 is the noise power at time n and z i are poles that correspond to AR parameters. The centroid frequency is given by :

f c (n )  fS xx ( f , n )df    S xx ( f , n)df    (15)
As it can be seen in equation ( 15), an estimation of the centroid frequency implies the computation of the whole spectrum. This is not appropriated for a real time An interesting alternative is to evaluate directly a single frequency (having the same variation as the centroid frequency) in which is concentrated the time-frequency contents. In this case, only one frequency has to be estimated instead of the whole spectrum. This provides an important reduction of the computing time, thus allowing real time estimation. This frequency, which corresponds to the pole argument, is given by:

f k (n )  f s 2  arg z k (n )   (16)
with arg(z i (n))  ]-, [ and where f s is the sampling frequency. In our study we only consider a low AR order, i.e. p=1.

Comparison

In this part, we compare the centroid frequency computed by using the FFT to the dominant pole frequency obtained by AR methods. Three kinds of pole frequency are evaluated, each one correspond to the batch [START_REF] Kay | Spectrum analysis -A modern perspective[END_REF], the adaptive RLS [START_REF] Ljung | Recursive Identification: Theory for the users[END_REF] and the weighted time-varying RLS approaches [START_REF] Grenier | Time-dependent ARMA modeling of nonstationary signal[END_REF], [START_REF] Girault | Time-varying autoregressive Spectral estimation for ultrasound attenuation in tissue characterization[END_REF].

In figure [START_REF] Kay | Spectrum analysis -A modern perspective[END_REF], we present the Doppler frequency estimation, of an artificial Doppler signal, proposed by Wendling [START_REF] Wendling | Simulation of Doppler ultrasound signals, pulsatile, non uniform flow[END_REF], evaluated by all the presented methods. These curves show that all AR algorithms give a good Doppler frequency estimation, but an advantage is in favor of the adaptive RLS and the weighted time-varying RLS approaches in terms of estimation delay and accuracy.

In order to show the typical performances of the adaptive and the time-varying methods, we compute an unrealistic simulated Doppler signal (see figure [START_REF] Vaitkus | A comparative study and assessment of Doppler ultrasound spectral estimation techniques, Part I : Estimation methods[END_REF]). Though the simulated Doppler signal in figure [START_REF] Vaitkus | A comparative study and assessment of Doppler ultrasound spectral estimation techniques, Part I : Estimation methods[END_REF] does not correspond to a true one (unrealistic), it permits to highlight some typical behaviors that cannot be easily observed in realistic simulated Doppler signals. In figure [START_REF] Vaitkus | A comparative study and assessment of Doppler ultrasound spectral estimation techniques, Part I : Estimation methods[END_REF] a time delay between the estimated Doppler frequency (by adaptive and time-varying algorithms) and the theoretical values can be observed. This delay is more pronounced for the adaptive RLS algorithm. Note that the forgetting factor  for the adaptive and the weighted time-varying algorithms is the same and equal to 0.995. This value of  seems a good trade-off between the estimation fluctuations and the tracking of the frequency. With in vivo Doppler signal, figure [START_REF] Ljung | Recursive Identification: Theory for the users[END_REF] shows that the Doppler frequency evaluated by the centroid estimator computed from the spectrogram has more fluctuations than the one evaluated by combining the use of the time-varying algorithm and the pole frequency estimator. This is partly due to the smoothness nature of the AR spectrum.

Conclusion

In this paper we have presented parametric methods which permit to evaluate a pole frequency. The computation time of this method is by far shorter than the one concerning the centroid frequency since it requires the evaluation of the whole spectrum. Moreover, we have compared a new parametric timevarying method to classical parametric methods. We have shown that this method provides an estimation delay lower than classical methods. This method can be used when very high nonstationarities are encountered in Doppler signals.

Figure 1 :

 1 Figure 1 : Doppler frequency estimation of an artificial signal by AR methods during a 3 seconds time span. Real part of the simulated Doppler signal a). Spectrogram of the Doppler signal b). Evaluation of the Doppler frequency by combining the use of the pole frequency estimator and parametric algorithms (batch, adaptive RLS and weighted time-varying RLS), =0.98, and centroid frequency evaluated from the spectrogram c).

Figure 2 :

 2 Figure 2 : Doppler frequency estimation of an unrealistic artificial signal by AR methods during a 3 seconds time span. Real part of the simulated Doppler signal a). Spectrogram of the Doppler signal b). Evaluation of the Doppler frequency by the joint use of the pole frequency estimator and AR algorithms with a forgetting factor equal to 0.995 for the two algorithms c); theoretical curve (dashed line), adaptive approach (gray solid line) and timevarying approach (dark solid line).

Figure 3 :

 3 Figure 3 : Doppler frequency estimation of an in vivo femoral artery Doppler signal by the time-varying AR method; and by the joint use of the centroid frequency estimator and the spectrogram during a 3 seconds time span. Real part of the simulated Doppler signal a). Spectrogram of a real Doppler signal and its centroid frequency b). Evaluation of the Doppler frequency by the joint use of the pole frequency estimator and the time-varying AR algorithm with a forgetting factor equal to 0.98 c); spectrogram (gray solid line) and time-varying approach (dark solid line).


Jean Marc Girault

Denis Kouamé

Abdeldjalil Ouahabi

Frédéric Patat

come


domain: info math

text:
Olivier Brun

Josu Doncel

Christopher Thraves Caro

Shortest Path Discovery Problem, Revisited (Query Ratio, Upper and Lower Bounds)

Consider the following problem: given two nodes s and t in a fully connected graph where each edge of the graph has a hidden length, discover the shortest path between s and t. The issue is that edge lengths are hidden. Hence, any algorithm that aims to solve the problem needs to uncover the length of some edges to discover the shortest path. The goal then is to discover the shortest path by means of uncovering the least possible amount of edge lengths. This problem is known as the Shortest Path Discovery (SPD) problem. The SPD problem is introduced by [13] in AAAI 2004. In this document, we study the SPD problem. We show that the previously proposed measure to evaluate the quality of an algorithm does not differentiate correctly algorithms according to their performance. Hence, it does not provide insightful information. Therefore, we introduce the query ratio, the ratio between the number of uncovered edge lengths and the least number of edge lengths required to solve the problem, as a new measure to evaluate algorithms that solve the SPD problem. When an input of size n is considered, we prove a lower bound of 1 + 4/n -8/n 2 on the query ratio of any algorithm that solves the SPD problem. As well, we present an algorithm that solves the problem and we prove that its query ratio is equal to 2 -1/(n -1).

Introduction

In a given graph, searching for the shortest path from an origin node to a destination node is a widely studied problem, see for instance the following surveys [START_REF] Wagner | Speed-up techniques for shortest-path computations[END_REF][START_REF] Cherkassky | Shortest paths algorithms: Theory and experimental evaluation[END_REF][START_REF] Dreyfus | An appraisal of some shortest-path algorithms[END_REF][START_REF] Alistair Moffat | Empirical survey of shortest path algorithms[END_REF]. Finding a shortest path is a problem that comes into sight in the area of Artificial Intelligence as subproblem of different problems, for example in symbolic planning, parsing, vision, or speech recognition.

The work [13] presented in AAAI 2004 introduces the Shortest Path Discovery (SPD) problem. In the SPD problem the length of the edges are unknown, but they can be queried. The SPD Problem aims to find the shortest path between two nodes querying the minimum number of edges. The SPD problem arises in a context in which obtaining the length of the edges dominates the total cost of computing a shortest path. As explained in [13], such a context appears in character or speech recognition, systems based on segmentation lattices, hierarchical planning, or exploration of unsafe environments.

Our particular motivation emerges from a routing problem in communication networks. Consider a set of nodes located at various spots in the Internet, and imagine that a source node wants to deliver a message to a destination node with a latency as low as possible. It may happen that the direct Internet path between the source and destination nodes has an unacceptably high latency. In that case, provided that other nodes can act as relays for the message, it may be worth searching for an alternate path passing through one or more intermediate nodes. One can be even more ambitious and search for the minimum latency path in the complete graph formed by all nodes. However, monitoring the quality of the Internet paths between all pairs of nodes by sending probe packets can be excessively costly, and it makes sense to minimize the monitoring effort required to discover the shortest path. This scenario perfectly falls whithin the scope of the SPD problem.

In this paper, we study the SPD problem. Due to our particular motivation, we restrict ourselves to the case of fully connected graphs. On the other hand, we extend the definition of the SPD problem by relaxing the constraint that a shortest path has to be discovered, and allowing a feasible path to be at most α times longer than the sortest one for some α ≥ 1. Of course, we fall back on the original problem when α = 1. Even if the restriction added to the problem appears to simplify it, all together with the relaxation they form an appealing version of the SPD problem.

Our contributions are as follows. We first prove that, for any complete graph of size n, any algorithm will need to query at least n -1 edges to find a feasible solution. On the other hand, we also show that for any algorithm there exists a bad instance such that the number of edges queried by the algorithm will be of the same order of magnitude than the total number of edges. The latter results suggest that the number of queries is not an appropriate measure to discriminate between algorithms for the SPD problem. We thus propose a new measure, the query ratio, to evaluate the performance of algorithms that solve SPD problem. The query ratio of an algorithm is defined as the worst-case ratio (over all instances) of the number of queries made by an algorithm on an instance to the minimum number of queries required to find a feasible path for that instance. For instances of size n, we prove that any algorithm has a query ratio of at least 1+ 4 n -8 n 2 and propose an approximation algorithm whose query ratio is upper bounded by 2 -1 n-1 . The paper is organized as follows. We first introduce some definitions and present related works. We then prove our lower bounds on the number of queries, before establishing lower and upper bounds on the query ratio. Finally, some conclusions are drawn and future research directions are proposed at the end of the paper.

Definitions

Let G = (V, E) be a fully connected undirected graph with n nodes where each edge has an unknown positive length. Let us denote by ℓ(e) > 0 the unknown length of the edge e ∈ E. We define a path in G as a finite ordered set of nodes in which all nodes are distinct. A path that connects nodes u and v is a path whose first node is u and last node is v. An edge belongs to a path if and only if the edge is formed by two consecutive nodes in the path. We denote by P (u,v) a path that connects nodes u and v, and by P (u,v) the set of all such paths. The length of a path is measured as the sum of the lengths of the edges in the path, i.e., the length of a path P (u,v) is ℓ(P (u,v) ) := e∈P (u,v) ℓ(e). We extend the previous notation to any set of edges F ⊆ E by letting ℓ(F ) := e∈F ℓ(e).

A shortest path between nodes u and v is a path P * (u,v) in P (u,v) so that ℓ(P * (u,v) ) ≤ ℓ(P (u,v) ) for all P (u,v) ∈ P (u,v) . We denote by δ (u,v) the length of a shortest path in G between nodes u and v.

On the other hand, we follow the standard definitions used in graph theory. A cut is a partition of the set V of nodes into two disjoint subsets. The cut-set of a cut is the set of edges whose end points are in different subsets of the partition.

In order to discover the shortest path between two nodes, an algorithm has to uncover the unknown length of the edges. We use the abstraction of an oracle for that purpose. Let O be an oracle that can be accessed by an algorithm to uncover the length of an edge or a set of edges, i. e., the oracle is accessed by an algorithm by requesting the length of an edge or a set of edges. Hence, the oracle reveals to the algorithm the length of all the requested edges. For short, we say that an algorithm uncovers an edge when we refer to all this process.

We remark that in the original definition of the SPD problem, it seeks the shortest path between two nodes in a graph uncovering the minimum possible amount of edges. Nonetheless, sometimes the main ambition can be lowered down and, instead to seek the shortest path, it might be enough to find a path with a guarantee with respect to the shortest path. This is the case that we study.

Consider a path P (s,t) between two nodes s and t ∈ V . We say that P (s,t) is an α-approximation if the following condition holds:

ℓ(P (s,t) ) δ (s,t) ≤ α.
When δ (s,t) is totally unknown (no lower bound is known except for the fact that δ (s,t) is positive), there is no guarantee on the length of path P (s,t) with respect to that of a shortest path, and we say that P (s,t) is an ∞-approximation. We say that a set of edges C ⊆ E is an α-certificate of G if and only if -the length of the edges in C is known, whereas edges in E \ C have unknown lengths, -C contains a path from s to t, the so called proposed path, and -there are enough uncovered edges in C to guarantee that the proposed path is an α-approximation.

We remark that every edge in the proposed path belongs to the α-certificate.

Hence, its length is fully known. In all instances there exists at least one αcertificate for any α. Indeed, the set E that contains all the edges of the graph is an α-certificate for any α. In [13], the authors prove that a set of edges is a 1-certificate (i. e., a certificate enough to guarantee that the proposed path is a shortest path) if the proposed path is a shortest path in the graph considering the known lengths of the edges in the certificate and lengths equal to zero for all other edges. Note that such a result can be extended as follows. A set of edges C is an α-certificate if and only if it contains a proposed path from s to t and the proposed path is an α-approximation in the graph where the length of the edges in C is known and the length of the edges in E \ C is zero.

Instance and Feasible Solution An instance I of the SPD problem is defined by a complete undirected graph G = (V, E) with n nodes and unknown positive edge lengths, two special nodes s and t ∈ V , a targeted approximation factor α ≥ 1, and an oracle O that can be accessed by an algorithm to uncover a set of edges. We define the size of an instance I as the number of nodes of the fully connected graph G, and it is denoted by |I|. As well, we define a feasible solution for the SPD problem as an α-certificate whose lengths are fully uncovered.

Two Objective Functions Let us denote by U (A(I)) the set of edges whose length has been uncovered by an algorithm A when solving the SPD problem on the instance I. In other words, the set U (A(I)) is the α-certificate given by algorithm A as a solution for the instance I. We define the number of queries of an algorithm that solves the SPD problem as follows.

Definition 1. The number of queries for instances of size n of an algorithm that solves the SPD problem is

β n if and only if |U (A(I))| ≤ β n ∀ I such that |I| = n.
On the other hand, we point out the fact that there might be many αcertificates in an instance and an algorithm has to search for one. We are interested in the size of a smallest α-certificate of an instance. Let us denote by |C α min (I)| the size of a smallest α-certificate of instance I. Henceforth, we define the query ratio of an algorithm as follows.

Definition 2. The query ratio of an algorithm A that proposes an α-approximation as a solution to solve the SPD problem is defined by the following ratio:

max I |U (A(I))| |C α min (I)| .
Our Contributions Our main contributions are as follows:

-We present a new meaningful measure, the query ratio, to evaluate the performance of algorithms that solve SPD problem. -We argue why the number of queries (as measure for the SPD problem) does not provide meaningful information about the algorithms that solve the SPD problem. -We prove that any algorithm has a query ratio of at least 1 + 4 n -8 n 2 , which means that no algorithm solves the SPD problem optimally.

-We present an algorithm that solves the SPD problem for any α ≥ 1. Furthermore, we prove that such an algorithm has a query ratio of 2-1 n-1 when α is equal to 1.

Related Work

The interest of researchers in discovering the shortest path in graphs with unknown information have increased in the last years. The survey [START_REF] Sommer | Shortest-path queries in static networks[END_REF] presents a compilation of results in the context of Shortest-Path Queries in Static Networks. The main difference of these problems with the SPD problem is that Shortest-Path Queries in Static Networks includes a preprocessing algorithm that may compute some information of the network to then be able to answer shortestpath or distance queries. The goal is to construct an efficient data structure via the preprocessing algorithm so that queries are answered rapidly. While, in the SPD problem, operations to obtain information about the network dominates the total cost of computation. In the context of bioinformatics, the survey [START_REF] Bouvel | Combinatorial search on graphs motivated by bioinformatics applications: A brief survey[END_REF] presents a collection of results and methods in the area of combinatorial search, focusing on graph reconstruction using queries of different type. The goal is to reconstruct a hidden graph from a class of graphs making as few queries as possible. Again, the goal of such problem differs from the goal of the SPD problem, since the SPD problem aims to find a shortest path.

The authors of [START_REF] Papadimitriou | Shortest paths without a map[END_REF] study shortest path problems when the graph is unknown in advance, but specified dynamically. These problems seek dynamic decision rules so that the total traversed distance has the best possible ratio to the shortest path. The authors describe optimal decision rules for two cases: layered graphs of width two, and two-optimal scenes with unit square obstacle. The objective function in this case clearly differs form the objective function of the SPD problem.

Another related work is [START_REF] Noga Alon | Economical graph discovery[END_REF] where the authors present the use of agents to discover the edges of the graph or a shortest path from a source to a sink node. They give bounds on the number of agents required to discover directed and undirected graphs. The objective function of this problem is the number of agents used to discover the solution, which differs from the objective function of the SPD problem.

In this document, we present an algorithm that searches from the source and the sink node at the same time. This type of algorithms are known in the literature as bidirectional search algorithms and their study has a long history [START_REF] Pohl | Bi-directional and Heuristics Search in Path Problems[END_REF]. These algorithms are shown to be faster than standard search algorithms such as Dijkstra's algorithm or A* [START_REF] Hart | A formal basis for the heuristic determination of minimum cost paths[END_REF] in most of the instances. However, make the two search fronts meet in the middle is a difficult task. Several algorithms have been presented in the literature to solve this issue. For example, in [START_REF] De | Bidirectional heuristic search again[END_REF] the authors suggest the BHFFA, which is a front-to-front algorithm that it is computationally expensive. The authors of [START_REF] Ghosh | Bidirectional heuristic search with limited resources[END_REF][START_REF] Davis | Towards a better understanding of bidirectioanl search[END_REF] present improved versions of the BHFFA that are computationally less expensive.

In this section, we present lower bounds for the number of queries required by any algorithm providing a finite α approximation.

Lemma 1. For any finite α ≥ 1, all α-certificate contain a cut-set in G such that the corresponding cut places s in one set of the partition and t in the other.

Proof. First, we remark that an α-certificate contains a proposed path by definition. Therefore, the length ℓ(P (s,t) ) of the proposed path P (s,t) is fully determined. Second, we remark that, in order to provide any finite approximation guarantee, the α-certificate needs to provide a strictly positive lower bound for the length of a shortest path between s and t. Otherwise, the only known lower bound for the length of a shortest path between s and t is 0. Now, consider an instance I of SPD problem and an α-certificate C. Let us assume that the α-certificate does not contain a cut-set that separates s and t. Hence, there exists a path P * (s,t) between s and t so that P * (s,t) ∩C = ∅. Since only edges in C have a known length, the length of P * (s,t) is totally unknown for the α-certificate C, implying that the only lower bound on δ s,t known by C is 0. Thus, the α-certificate C cannot guarantee any finite approximation for its proposed solution. Therefore, there is a contradiction because C is not an α-certificate. ⊓ ⊔ Lemma 2. A set of edges that contains a path between s and t and a cut-set in G, such that the corresponding cut places s in one part and t in the other, is an α-certificate for some finite α ≥ 1.

Proof. Consider a set of edges C as in the statement of the Lemma. Let us denote by P C (s,t) the path in C between s and t. It holds that P (s,t) ∩ C = ∅ for any path P (s,t) ∈ P (s,t) . Since 0 < min{ℓ(P (s,t) ∩ C) : P (s,t) ∈ P (s,t) } ≤ δ (s,t) , it holds that

ℓ(P C (s,t) ) ≤ ℓ(P C (s,t) ) min{ℓ(P (s,t) ∩ C) : P (s,t) ∈ P (s,t) } δ (s,t) < ∞,
implying that C is an α-certificate for α = ℓ(P C (s,t) )/min{ℓ(P (s,t) ∩ C) : P (s,t) ∈ P (s,t) }. ⊓ ⊔

Lemma 1 enables us to present lower bounds for the number of queries β n required so that an algorithm can guarantee a finite α-approximation.

Corollary 1. For any algorithm that solves the SPD problem for a finite approximation

α ≥ 1, it holds that β n ≥ n -1.
This is a direct consequence of Lemma 1 and the fact that the smallest cut-set in the complete graph has size n -1.

Nevertheless, the previous lower bound for β n is optimistic since there exist cases in which any algorithm needs to uncover strictly more than n -1 edges in order to provide a finite approximation. Lemma 3. For any real α ≥ 1 and integer 1 ≤ p ≤ n/2, there exists an input so that any algorithm requires at least p • (np) uncovered edges in order to provide an α-approximation.

Proof. We prove this Lemma via the construction of an input that certifies the conditions stated in the lemma. Let us split the set of nodes in one set of size p and one set of size np. Each edge with its two end points in the same set has length ǫ > 0. The direct edge (s, t) has length 1. Each edge with its end points in different sets (except for the direct edge) has length α ≥ 1. In such a graph, the only α-approximation is indeed the direct path s, t. But, in order to guarantee such condition, any algorithm needs to uncover at least the cut-set of size p • (np) that contains all the edges of length α.

⊓ ⊔ Corollary 2. For any algorithm A that solves the SPD problem for a finite approximation factor α ≥ 1, there exists an input so that A requires at least n 2 /4 uncovered edges in order to provide an α-approximation.

According to Corollary 2, we consider meaningless the number of queries β n of an algorithm. Indeed, for any algorithm and whatever the value of α ≥ 1, it is always possible to find a bad instance such that the number of edges uncovered by the algorithm will be of the same order of magnitude than the total number of edges. Therefore we change our aim. In the rest of the document, we focus on the study of the query ratio of algorithms that proposes α-approximations to solve the SPD problem. We believe that the query ratio is a fair measure to evaluate the performance of algorithms for the SPD problem since it expresses how far is the number of queries asked by an algorithm with respect to the best possible any algorithm can perform in that instance.

Lower and Upper Bounds on the Query Ratio

In this section, we concentrate on the study of the query ratio. We present a lower bound and an upper bound on the query ratio. The first bound is obtained via the design of an adversary constructed for any algorithm. For the second bound, we present an algorithm and analyze its query ratio.

An Adversary for Any Algorithm

Lemma 4. For any α ≥ 1 and for any algorithm A that proposes an α-approximation, there exists a particular instance I of size n such that

|U (A(I))| |C α min (I)| ≥ 1 + 4 n - 8 n 2 .
Algorithm 1 Adversary that construct a bad instance for any algorithm, where e 1 , e 2 . . . , e l are the edges queried by the algorithm, i. e., e i is the edge queried at the i-th step.

1: INITIALIZE sets Gs = {s} and Gt = {t}; functions g(u) = 0, ∀u ∈ V /{s, t}, g(s) = s, and g(t) = t. 2: for i = 1, . . . , l do 3:

if ei = (s, t) then 4:

REPLAY ℓ(ei) = 1.

5:

end if 6:

if ei = (s, u) such that g(u) = 0 then 7:

REPLAY ℓ(ei) = ǫ and update g(u) := s and Gs := Gs ∪ {u}.

8:

end if 9:

if ei = (s, u) such that g(u) = t then 10:

REPLAY ℓ(ei) = α.

11:

end if 12:

if ei = (u, t) such that g(u) = 0 then 13: REPLAY ℓ(ei) = ǫ and update g(u) := t and Gt := Gt ∪ {u}.

14:

end if 15:

if ei = (u, t) such that g(u) = s then 16:

REPLAY ℓ(ei) = α. 17:

end if 18: if ei = (u, v) such that g(u) = g(v) = 0 then 19: REPLAY ℓ(ei) = ǫ. 20:
end if 21:

if ei = (u, v) such that g(u) = 0 and g(v) ∈ {s, t} then 22:

REPLAY ℓ(ei) = ǫ.

23:

UPDATE g(u) := g(v).

24:

UPDATE g(u ′ ) := g(v)∀u ′ such that there exists a path from u to u ′ composed by uncovered edges each with length equal to ǫ.

25:

UPDATE G g(v) := G g(v) ∪ {u} ∪ {u ′ : u ′ →ǫ u}, where u ′ →ǫ u means that u and u ′ are connected by a path of uncovered edges each with length equal to ǫ.

26:

end if 27:

if ei = (u, v) such that g(u) ∈ {s, t} and g(v) ∈ {s, t}/g(u) then 28:

REPLAY ℓ(ei) = α.

29:

end if 30:

if ei = (u, v) such that g(u) ∈ {s, t} and g(v) = g(u) then 31:

REPLAY ℓ(ei) = ǫ.

32:

end if 33: end for Proof. In order to prove the Theorem, we construct a bad instance I for each algorithm. The construction is made adversarially. We give a malicious adversary that acts as the oracle and, each time that an algorithm uncovers an edge, the adversary gives the length of that edge to the algorithm so that the performance of the algorithm is as bad as possible. The adversary is precisely described in Algorithm 1.

The adversary constructs an instance similar to the instance of Lemma 3, but ad hoc to each algorithm. In the instance constructed by the adversary, the shortest path between s and t is always the direct edge (s, t). Furthermore, such a path is the only α-approximation. On the other hand, the instance has a partition of the set of vertices with s in one set of the partition and t in the other set. The partition and the size of each sets of the partition depend on the algorithm. Edges that connect two nodes of the same set of the partition have length ǫ. While, edges that connect two nodes each in a different set of the partition have length α.

Each algorithm can be seen as a sequence of edges to be uncovered. An algorithm poses a query to the oracle that is an edge to be uncovered. The oracle answers each query providing the length of that edge. In this particular construction, the adversary plays the role of the oracle. Edges to be uncovered by an algorithm can be grouped in four groups:

i) {(s, t)}, ii) {(s, u) : u ∈ V /{t}}, iii) {(u, t) : u ∈ V /{s}} and, iv) {(u, v) : u ∧ v ∈ V /{s, t}}.
The way in which the adversary determines the partition is described in the following lines. Nodes s and t are initially placed one in each set of the partition, let us denote these sets by G s and G t , respectively (see the initialization of function g(s) and g(t) in line 1 of Algorithm 1). If the algorithm queries the edge (s, t) to be uncovered, the adversary answers to the algorithm ℓ(s, t) = 1 (see lines 3 and 4 in Algorithm 1). If the algorithm queries an edge of the second group to be uncovered and the node u has not been placed in any set of the partition, the adversary answers ℓ(s, u) = ǫ and places u in the set G s (see lines 6 and 7 in Algorithm 1). Otherwise, when u has been placed in a set of the partition (it can be only the set G t ), the adversary answers ℓ(s, u) = α (see lines 9 and 10 in Algorithm 1). The adversary acts equivalently when the algorithm queries an edge of the third group. I. e, if u has not been placed in any set of the partition, the adversary answers ℓ(u, t) = ǫ and places u in the set G t (see lines 12 and 13 in Algorithm 1). Otherwise, when u has been placed in a set of the partition (it can be only the set G s ), the adversary answers ℓ(u, t) = α (see lines 15 and 16 in Algorithm 1). Finally, if the algorithm queries an edge of the fourth group, there exist four different cases: u and v have not been placed in any set of the partition, then the adversary answers ℓ(u, v) = ǫ and none is placed in any set of the partition (see lines 18 and 19 in Algorithm 1). When one of them has been placed in a set of the partition, says u, and the other one has not, the adversary answers ℓ(u, v) = ǫ and node v is placed in the same set than u. In this case, node v might have neighbors not yet assigned to a set of the partition as well. In that case, all the nodes in the same connected component than v are placed in the same set as nodes u and v (see lines 21 to 25 in Algorithm 1). Finally, if the two nodes have been placed in a set of the partition, the adversary answers ℓ(u, v) = ǫ if the two nodes belong to the same set of the partition, or ℓ(u, v) = α if they belong to different sets (see lines 27 to 31 in Algorithm 1).

We observe that the shortest path from s to t in any instance constructed by the adversary, regardless the algorithm, is the edge (s, t). Moreover, it is the only α-approximation. On the other hand, for any algorithm, we obtain two sets G s and G t , according to the notation defined in Algorithm 1, that form a partition of V , i.e., G s ∩ G t = ∅ and G s ∪ G t = V . The sets G s and G t form a partition since every node is added either to the set G s or to the set G t . Moreover, since any algorithm needs to present an α-certificate and such certificate must contain a partition of V , therefore, every node is added to one set.

The smallest α-certificate consists in all the edges that connect the nodes of both sets of the partition G s and G t . Hence, it holds that |C α min (I)| = |G s | • |G t |. Moreover, we see that the number of uncovered edges by the algorithm is the sum of |C α min (I)| and the number of uncovered edges in each set of the partition. The graph formed by the uncovered edges in each set of the partition is connected, since by construction there exists a path from s (resp, t) to any node in G s (resp, G t ). Therefore, the number of uncovered edges in each set of the partition is at least |G s | -1 and |G t | -1, respectively. Thus, it holds that:

|U (A(I))| |C α min (I)| ≥ |C α min (I)| + |G s | -1 + |G t | -1 |C α min (I)| = 1 + |G s | + |G t | -2 |G s | • |G t | .
Since, it also holds that

|G s | + |G t | = n, the fraction |Gs|+|Gt|-2 |Gs|•|Gt| yields its minimum value when |G s | = |G t | = n 2 .
Hence, we obtain

|U (A(I))| |C α min (I)| ≥ 1 + 4 n - 8 n 2 ⊓ ⊔
A direct consequence of Lemma 4 is the following Theorem.

Theorem 1. For any α ≥ 1 and for any algorithm A that proposes an αapproximation, it holds the following inequality for the query ratio,

max I |U (A(I))| |C α min (I)| ≥ 1 + 4 n - 8 n 2 .
According to this result, we observe that the query ratio of any algorithm is strictly higher that 1, which means that no algorithm solves the SPD problem optimally.

An Algorithm that Searches From the Source and the Sink

In this subsection, we present an algorithm that proposes an α-approximation as a solution of the SPD problem. We remark that in the proposed algorithm α is a parameter, and it can be set arbitrarily. Therefore, the proposed algorithm is a parametrized algorithm that guarantees the approximation factor that we arbitrarily decide to obtain. We compute the query ratio of such an algorithm proving that it never queries more than two times the size of the smallest certificate of an instance, when it proposes an optimal solution. A precise description of the algorithm is presented in Algorithm 2.

The algorithm defines lower and upper bounds on the length of each edge that are initially set to zero and infinity, respectively (see line 1 in Algorithm 2). The algorithm works in rounds. At each round, the algorithm advances one step further in a double search that starts from nodes s and t. At each round, Algorithm 2 picks the closest nodes to s and t according to the current uncovered edges. The closest node to s (resp. t) is denoted by s * (resp. t * ) (see lines 3 and 4 in Algorithm 2). Then, the algorithm queries all the edges of the form (s * , u) and (u, t * ) that have not been queried yet, and that approaches in one edge s * to t and t * to s, respectively (see lines 7 to 9 in Algorithm 2). The algorithm then computes the shortest path between s and t using the real length for the uncovered edges and the lower bound set at the beginning for the edges not yet uncovered (P AT H inf ). The algorithm also computes the shortest path between s and t using the real length for the uncovered edges and the upper bound set at the beginning for the edges not yet uncovered (P AT H sup ). Finally, the algorithm computes whether P AT H sup is an α-approximation in line 22. If that is the case, Algorithm 2 stops and returns P AT H sup , otherwise, it iterates one more round.

The correctness of the algorithm follows directly from the following two facts. First, the algorithm proposes a fully uncovered path. Second, the proposed path is an α-approximation since in the last round it holds that ℓ(P AT Hsup) ℓ(P AT H inf ) ≤ α and ℓ(P AT H inf ) is a lower bound on δ s,t .

In order to proceed with the analysis of the query ratio of Algorithm 2, we first compute the number of queries performed by the algorithm up to a generic round i. Lemma 5. For any i, the number of queried edges by Algorithm 2 up to the i-th round is equal to i(2n -2i -1).

Proof. At each round, the algorithm queries 2|V /{m s ∪ m t }| + 1 edges according to lines 7 to 9 of Algorithm 2. At each round, the sizes of m s and m t increases in one element. Note that s * and t * are different at each round. Otherwise, if at some round s * = t * , in the previous round the algorithm would have stopped since the union of the shortest path from s to s * and the shortest path from t * to t would have been the shortest path from s to t. Hence, approx would have been equal to 1. Therefore, at the j-th round, the size of V /{m s ∪ m t } is equal to (n -2j).

Thus, the number of edges queried by the algorithm up to round i is the sum of the queries at all the previous rounds, i.e., i j=1 (2(n-2j)+1) = i(2n-2i-1).

⊓ ⊔

On the other hand, if Algorithm 2 stops after i rounds, we are able to give a lower bound on the size of the smallest certificate of the instance. We give such a lower bound in the following lemma. Lemma 6. If Algorithm 2 stops after i rounds in an instance I, the size of the minimum 1-certificate of the instance is at least i(n-i), i.e., |C 1 min (I)| ≥ i(n-i).

Proof. In this proof we use the following notation. We denote by m s,j (respectively, m t,j ) the set m s (respectively m t ) at the end of the j-th round of the algorithm. We also denote by s * j (respectively t * j ) the node that was added to m s (respectively to m t ) at the j-th round of the algorithm. According to these definitions, we have that in round j, m s,j = m s,j-1 ∪ {s * }, m t,j = m t,j-1 ∪ {t * } where m s,0 = m t,0 = {∅}. We use m s = m s,i and m t = m t,i to denote the sets m s and m t after Algorithm 2 has finished. Moreover, for any two nodes u, v and a set of nodes U ⊆ V , we denote by P * (u,v) | U the shortest path between u and v in the graph induced by the set of nodes U .

First we show that the following two inequalities hold for all 1 ≤ j ≤ i.

ℓ(P * (t,t * j-1 ) | mt,j-1 ) ≤ ℓ(P * (t,t * j ) | mt,j ). (1)
Since the arguments are equivalent for both equations, we only argue that Equation (1) holds.

We point out the fact that the path P * (s,s * j ) | ms,j either visits s * j-1 or it does not visit such node. In the first case, Equation (1) holds because the path P * (s,s * j ) | ms,j can be decomposed in the path P * (s,s * j-1 ) | ms,j-1 (the shortest path from s to s * j-1 in m s,j-1 ) union some other edges. Hence, the length ℓ(P * (s,s * j ) | ms,j ) can also be decomposed in the sum of ℓ(P * (s,s * j-1 ) | ms,j-1 ) plus a positive value. In the second case, when the path P * (s,s * j ) | ms,j does not visit the node s * j-1 , due to the order in which Algorithm 2 chooses nodes s * j-1 and s * j , it holds: In conclusion, Equation (1) holds for all 1 ≤ j ≤ i.

Second, we show that the following equation holds.

ℓ(P (s,t) ) ℓ(P * (s,s * i ) | ms ) + ℓ(P * (t,t * i ) | mt ) > 1. (3)
The shortest path proposed by the algorithm might be fully uncovered either at the very last round of the algorithm or it was uncovered in an earlier round. When the proposed path was uncovered in the last round of the algorithm, Equation (3) holds because in this case the proposed path must visit s * i and t * i . Therefore the length of the proposed path P (s,t) is of the form ℓ(P * (s,s *

i ) | ms ) + ℓ(P * (t,t * i ) | mt ) + A,
where A is a positive value given by the length of the last uncovered edges added to the shortest path proposed by the algorithm. Hence, it holds:

ℓ(P (s,t) ) ℓ(P * (s,s * i ) | ms ) + ℓ(P * (t,t * i ) | mt ) = ℓ(P * (s,s * i ) | ms ) + ℓ(P * (t,t * i ) | mt ) + A ℓ(P * (s,s * i ) | ms ) + ℓ(P * (t,t * i ) | mt ) > 1.
In the case when the proposed path was uncovered in a round earlier than the last round of the algorithm, Equation (3) holds because in the round i -1, the algorithm computes | mt,j , where P (s * j , t * j )| V /{ms,j ∪mt,j } denotes a path between s * j and t * j in V /{m s,j ∪ m t,j }. There exists at least n -2j + 1 disjoint paths of the form previously described, one per each node in V /{m s,j ∪ m t,j } plus the path that connects directly s * j and t * j . Hence, at least n -2j + 1 edges needs to be present in any 1-certificate for each pair of nodes s * j , t * j . Therefore, if we sum up all these edges, we obtain that any 1-certificate needs to contain at least the following amount of edges. i j=1 n -2j + 1 = ini(i + 1) + i = i(ni).

⊓ ⊔

Now, we state the main result of this Subsection in the following theorem. Proof. From Lemmas 5 and 6, it holds:

|U (A * (I))| |C 1 min (I)| ≤ i(2n -2i -1) i(n -i) = 2 - 1 n -i ≤ 2 - 1 n -1 .
⊓ ⊔

Conclusions and Future Work

In this document we introduced the query ratio, a new measure to analyze algorithms that solve the SPD problem. In our opinion, the query ratio of an algorithm provides an important insight into the real quality of an algorithm solving the SPD problem. That is because it compares the number of queries performed by the algorithm with the least amount of queries required to solve the problem. Therefore, we consider that the query ratio is the correct measure to take into account in the design of algorithms to solve the SPD problem.

In this document we presented lower and upper bounds on the query ratio. Under our consideration, the most appealing problem that this document leaves open is the gap between these lower and upper bounds. The question is whether there exists an algorithm, or on the contrary an adversary that produces a bad instance for any algorithm, so that the gap is closed. We also consider interesting the comprehension of the trade-off between the approximation factor α for the proposed path and the query ratio of an algorithm. The question is whether when we relax the approximation factor α we obtain better results for the query ratio. Another open problem is to extend the results presented in this document to general graphs (not only when the graph in consideration is fully connected).

j- 1 )

 1 | ms,j-1 ) ≤ ℓ(P * (s,s * j ) | ms,j )

j- 1 )

 1 | ms,j-1 ) ≤ ℓ(P * (s,s * j ) | ms,j-1-{s * j-1 }∪{s * j } ). Otherwise, the algorithm would have picked s * j before s * j-1 . Since the path P * (s,s * j ) | ms,j does not visit the node s * j-1 , it also holds that P * (s,s * j ) | ms,j = P * (s,s * j ) | ms,j-1-{s * j-1 }∪{s * j } . Therefore, it holds: ℓ(P * (s,s * j-1 ) | ms,j-1 ) ≤ ℓ(P * (s,s * j ) | ms,j-1-{s * j-1 }∪{s * j } ) = ℓ(P * (s,s * j ) | ms,j ).

Theorem 2 .

 2 Let A * denote Algorithm 2. Therefore, for the query ratio of A * , it holds:

  Now, using Equations (1) to[START_REF] Cherkassky | Shortest paths algorithms: Theory and experimental evaluation[END_REF], we are able to show that, for all 1 ≤ j ≤ i, it holds the following:ℓ(P (s,t) ) ℓ(P * (s,s * j ) | ms,j ) + ℓ(P * (t,t * j ) | mt,j ) > 1.Therefore, for any 1 ≤ j ≤ i and any path that intersects P * (s,s * j ) | ms,j and P * (t,t * j ) | mt,j , any 1-certificate needs at least one edge not in P * (s,s * j ) | ms,j ∪P * (t,t * j ) | mt,j to show that the proposed path is the shortest path. Now, for any pair of nodes s * j , t * j , consider the paths of the form P

	ℓ(P (s,t) ) ) |m s )+ℓ(P * (t,t * i than 1 since the algorithm does not stop. Therefore it holds: ℓ(P * (s,s * i ) |m t ) and the result has to be larger
	ℓ(P (s,t) ) i ) | ms ) + ℓ(P * (s,s * ℓ(P * (t,t * i ) | mt )	> 1.

* (s,s * j ) | ms,j ∩ P (s * j , t * j )| V /{ms,j ∪mt,j } ∩ P * (t,t * j )