Marie-Gabrielle Medici

Anne Mongruel

Laurent Royon

Daniel Beysens
email: daniel.beysens@espci.fr

Edge effects on water droplet condensation

Keywords: number(s): 68.03.Fg, 68.08.Bc, 64.60.Q-

In this study is investigated the effect of geometrical or thermal discontinuities on the growth of water droplets condensing on a cooled substrate. Edges, corners, cooled/non cooled boundaries can have a strong effect on the vapor concentration profile and mass diffusion around the drops. In comparison to growth in a pattern where droplets have to compete to catch vapor, which results in a linear water concentration profile directed perpendicularly to the substrate, droplets near discontinuities can get more vapor (outer edges, corners), resulting in faster growth or less vapor (inner edges), giving lower growth. When the cooling heat flux limits growth instead of mass diffusion (substrate with low thermal conductivity, strong heat exchange with air), edge effects can be canceled. In certain cases, growth enhancement can reach nearly 500% on edges or corners.

I. INTRODUCTION

Everybody has observed, in a room supersaturated with water vapor, the runoff of water drops condensing on windows. A more careful observation shows that the drops start to flow mostly from the edges of the window.

Drops, which are pinned by their contact line on the substrate, detach from an inclined surface when their diameter exceeds a critical size that depends on the inclination angle [1]. The fact that droplets detach sooner from the edge is thus due to their larger size when compared with the other "bulk" droplets. This phenomenon is quite interesting for droplet collection since the top drops can wipe out the entire surface when sliding down.

The reasons of this difference in droplet evolution can be found in the discontinuities of the substrate which modify the water vapor gradient around drops, causing enhancement or reduction of their growth rate. These discontinuities can be either geometric (edge of the substrate, bump, cavity, etc.) or thermal (differences in substrate cooling properties). To our knowledge, no such effects have been reported so far, although drop detachment due to enhanced growth by directed coalescence under wettability gradient has already been observed [2]. It is thus the object of the present study to evaluate the effect of substrate discontinuities on dropwise condensation, the discontinuities being either of geometrical or thermal nature.

II. GROWTH OF A DROPLET PATTERN

A. General

Dew, also called "Breath Figures" (BF) in the laboratory, is the condensation of water vapor on a substrate. The preliminary research on BFs dates back to the years from 1893 to 1922 [START_REF] Aitken | Proc. R. Soc. Edinburgh[END_REF][START_REF] Rayleigh | [END_REF][5]. Fundamental laws of nucleation and growth of BFs were identified later [6][7] and well-characterized regimes were evidenced. The substrate on which condensation takes place is assumed to be maintained at constant temperature. In this study water drops exhibit contact angles θ around 90° with all the investigated substrates of this study, with one exception. Unless specified, we will thus assume in the following that droplets are hemispherical. Four different stages of growth can be identified. (i) Droplets nucleate. (ii) Droplets grow with rare coalescences corresponding to low surface coverage.

The radius, R, of the droplet spherical cap varies with time, t, according to a power law 𝑅~𝑡 ! . The exponent value depends on the relative values of droplet inter-distance <d>, defined as the mean distance between two neighboring drops centers, compared to the water concentration boundary layer, ζ. The latter measures the extension of the water vapor concentration profile around the droplets. After nucleation, in stage (ii), drops are far apart from each other. It corresponds to <d> > ζ where drops grow independently in a hemispherical profile centered on each drop, resulting in α =1/2. Later on, drop surface coverage increases and drop inter-distance decreases until <d> < ζ. The concentration profiles overlap, the mean profile is directed perpendicularly to the substrate and α =1/3 (a full discussion is given below). (iii) Then droplets touch each other and coalesce, leading to a constant surface coverage and a self-similar growth behavior. The concentration profiles still overlap with the mean profile directed perpendicularly to the substrate and α =1/3 for each individual drop. The mean radius of the droplet pattern grows as < 𝑅 > ~𝑡! with γ = 3α. The surface coverage, 𝜀 ! , being constant at this stage, implies that < 𝑑 > scales with < 𝑅 > . For instance, hemispherical droplets on a square lattice show a surface coverage 𝜀 ! = 𝜋 !! ! ! !! ! ! ≈ 0.55. Then at some time, < 𝑑 > > ζ and nucleation of new droplets can occur between neighboring drops. This is stage (iv).

The new droplets which have nucleated then follow the same growth law behavior as described earlier. Further on (stage v), gravity effects become important. The influence of gravity can be measured by comparing the drop radius to the water capillary length 𝑙 ! = ! !∆! (≈ 2.7 mm with σ ≈ 73 mN.m -1 the water-air surface tension, g ≈ 9.81 m.s -2 the earth acceleration constant and ∆𝜌 = ρ wρ a ≈ 1000 kg.m -3 the air-water density difference). Drops on an inclined substrate slide down when their weight becomes larger than their capillary pinning forces.

Let us now consider the details of the growth of a droplet when its temperature, T s , is maintained constant in a humid air at given temperature T a and vapor pressure p∞. A sessile drop (contact angle θ) grows by incorporation of the diffusing water vapor molecules (monomers) around it. The concentration of monomers, c(r, t), counted in mass per volume, obeys the following equation (r is the distance to the drop center):

!" !" + ∇. 𝚥 = 0 , (1)
where

𝚥 = -𝐷∇𝑐 , (2)
is the diffusive flux of monomers (mass per unit surface and unit time) with D the diffusion coefficient of the monomers in air.

The problem governed by Eqs. (1-2) is a Stefan problem with a moving boundary at r = R(t). Analytical solutions are rare. For the present problem one assumes a growth slow enough such that the time dependence of c can be neglected in Eq. ( 1) (quasi-static approximation). Thus Eqs. ( 1) and ( 2) reduce to the Laplace equation:

∆𝑐 = 0 . (3)
Its solution has to fulfill the following boundary conditions: (i) c(r = R) = c s , corresponding to the water saturation pressure at the drop temperature, p s , and (ii) c(r → ∞) = c ∞ , corresponding to the water pressure at air temperature, p ∞ . Practically, c ∞ (p ∞ ), resp., represents the monomer concentration (water pressure) resp., at the border of the concentration boundary layer, ζ. It is then assumed that the transport of water molecules towards the droplet surface occurs by molecular diffusion only, i.e. the convective transport is negligible. This will be discussed in section IV-E.

The above assumption (i) implies that droplets are isothermal. This can be ensured for the smallest drops where heat transfer occurs on a small (µm) lengthscale. For larger drops, Marangoni thermocapillary convection provides fast heat transfer to make droplets isothermal [8]. Such convective flows have been observed. They provide efficient heat transfer from the drop surface to the condensing substrate and validate an isothermal drop.

Once the concentration of monomers is known, the drop volume evolution can be obtained following the growth equation:

!" !" = ! ! ! 𝚥 𝑟 = 𝑅 . 𝑛 𝑑𝑆 = ! ! ! 𝐷 -∇𝑐 ! . 𝑛𝑑𝑆 ! ! . ( 4
)
Here 𝚥 𝑟 = 𝑅 is the flux of monomers at the drop surface, 𝑛 is the unit vector locally normal to the drop surface,

V=π f(θ)R 3 is the drop volume with 𝑓 𝜃 = !!!!"#$!!"#$ ! !!"#$ !
and S is the surface of drop/air interface.

Depending whether one deals with a single drop or a droplet pattern, the drop evolution is different. In the following we address these two kinds of growths.

B. Single drop growth

For a single sessile drop on a surface kept at constant temperature, a simple way to solve the problem is to assume an inverse process to evaporation [9][10]. It is implicitly assumed that the probability of incorporating the monomers is uniform on the drop surface, which means that the latent heat of condensation is uniformly removed.

In a 3D space and for a hemispherical drop (Fig. 1a), Eq. ( 3) has a hyperbolic solution:

𝑐 = 𝑐 ! -𝑐 ! -𝑐 ! ! ! . ( 5
)
The following growth law can then be derived from Eq. 4:

𝜌 ! 𝑅 ! !" !" = 𝑅 ! 𝐷 ! ! ! ! ! ! . ( 6
)
The integration of this equation gives the classical evolution

𝑅 = (𝐴𝑡) ! ! , ( 7
) with 𝐴 = 2 ! ! ! !! ! ! !
(in m 2 .s -1 ) .

This growth law corresponds to an isolated drop or to a drop in a pattern whose water vapor profile does not overlap with the other drops. The latter case occurs when the inter-droplet distance <d> >> ζ.

C. Individual drop growth in a pattern

Let us consider now an array of drops separated by the mean distance < 𝑑 > on order or lower than ζ (Fig. 1b).

This situation corresponds to the end of stage (ii) or stage (iii) between the coalescence events. The individual water vapor concentration profiles merge in a profile parallel to the substrate. The drop pattern can thus be treated as a homogeneous film with average thickness ℎ =

! ! ! ! = ! ! !!! ! [6-10].
Here 𝑉 ! = 𝑉 ! = 𝜋𝑓(𝜃) 𝑅 ! ! is the total condensed volume and 𝑆 ! is the surface area of the condensation substrate. Each individual drop (i) with volume V i = πf(θ )𝑅 ! ! is assumed to grow like a thin film, where the vapor concentration profile depends only on the normal to the substrate (z axis). Eq. 4 gives a linear variation for the water vapor profile. The boundary conditions are c s = c(z=h) and c ∞ = c(z=h+ζ), where ζ is the concentration boundary layer. (A discussion about its calculation and how its value impacts the calculation of the drop growth rate is given below in section IV-E). One thus finds:

𝑐 = 𝑐 ! + 𝑐 ! -𝑐 ! !!! ! . (8)
It follows:

h=Bt, (9)
with 𝐵 =

! ! ! !! ! ! ! ! (in m.s -1 ).
This implies that V i is proportional to h , and hence, to t. Finally, R i is proportional to t β , with β=1/3.

D. Drop pattern evolution with coalescence

In the self-similar growth stage (iii) drops touch each other and coalesce, which leads to an acceleration of the drop pattern evolution. When accounting for such coalescence events, the mean radius evolution of the droplet pattern is rescaled from the individual drop growth Eq. ( 9) as

𝑅 ! = 𝐵 ! 𝑡 ! , ( 10
)
with [6]

𝛾 = 𝛽 ! ! ! ! !! ! . ( 11
)
Here 𝐷 ! (𝐷 ! ) are the drop (substrate) dimensionalities. For 3D droplets growing on a 2D substrate, 𝛾 = 3𝛽 = 1.

For 3D droplets growing on a line, 𝛾 = ! ! 𝛽 = 1/2 [11].

In this growth stage where the drop surface coverage is constant, one notes the relation of proportionality between the mean radius of the drop pattern, <R>, and V T . Let us consider the definition of the drop surface coverage

𝜀 ! = ! ! ! ! = ! ! ! ! ! ! . ( 12
)
Here 𝑆 ! = 𝜋 𝑅 ! is the surface area covered by drops. By expressing the mean drop radius in terms of third and second moments, < 𝑅 >=

! ! ! ! ! ! , one gets < 𝑅 >= ! ! ! !(!) ! ! ! ! = ! ! ! !(!) ℎ . ( 13
)
From Eq. ( 9), one obtains:

< 𝑅 > = 𝑘𝑡, (14)
with

𝑘 = ! ! ! !(!) ! ! ! ! ! ! !! ! . ( 15
)
An evaluation of ζ is given below in section IV-E. It can be used to evaluate k. It is worthy to note that the quantity 𝑐 ! -𝑐 ! / 𝜁 represents the mean water vapor concentration gradient on a drop according to Eq. ( 4). Eq. (15) can thus be alternatively written as (S is the drop/air interface)

𝑘 = ! ! ! !(!)! ! ! ! -∇𝑐 ! . 𝑛𝑑𝑆 ! . (16)
In [12] the relation ε 2 ≈ 1-θ (deg.)/200 was found between the drop surface coverage and contact angle θ . This relation stems from the drop coalescence process. When two drops coalesce, the new composite drop exhibits a contact angle, θ, lower than the receding angle, θ R . It results a force ∼σ (cosθ -cosθ R ) that moves the contact line against the pinning forces. This force decreases as the contact angle diminishes. Then the contact line remains pinned at some places. It results an increase in drop surface coverage when compared to the case where the contact line moves freely. It thus follows from this relation that the mean droplet radius of the pattern grows linearly with time with a prefactor that depends only on the water vapor supersaturation Δ𝑐 = 𝑐 ! - 𝑐 ! , the concentration boundary layer thickness 𝜁 and the vapor in air diffusion constant D. One notes that this growth law remains valid as long as the film approximation remains valid, that is, the individual concentration profiles of drops overlap. It is thus also valid for droplets growing on a 1D, linear substrate and corners.

E. Effects of discontinuities

All the above growth laws are concerned with a uniform substrate corresponding to a semi-infinite medium and drop interfaces maintained at constant temperature thanks to a thermal connection to a thermostat. The latter corresponds to a heat conductive substrate where the latent heat flux coming from condensation can be continuously sent to the thermostat. Growth is then not limited by the heat flux in the substrate. This is generally true when the substrate is made of a conductive metal in contact with a thermostat, bare or coated with a thin sheet of low conductive materials (polymers). It is not the case when the heat flux limits condensation, e.g. for substrates made of a thick isolating materials or a thin foil not or weakly connected to the thermostat. The growth of natural dew, where the substrate cooling is a balance between surface radiative cooling and air heating, is a more complex case where mass diffusion and thermal diffusion compete. We will thus not consider here this situation.

In this aspect, two types of boundaries can be considered: (i) geometric discontinuity without cooling heat flux limitation as e.g. the boundaries of the condensation substrates and (ii) thermal discontinuities as e.g. the border between a conductive and nonconductive support. (Discontinuities in contact angles are not considered here). Both geometrical and thermal discontinuities have in common a modification of the water concentration profile and thus of the droplet evolution near the border. One can already anticipate that thermal discontinuities and geometrical discontinuities at outer edges will speed up the growth because more water vapor can be collected at the border, whereas geometrical discontinuities at inner edges, where less water vapor is collected, will lower the droplet growth.

A quantification of the effect of borders on drop evolution needs to consider several factors. One notices that drops near discontinuities always undergo coalescence with the neighboring drops that grow on the same plane. As the advancing contact angles are less than 98° (Table 1), there are no coalescences between orthogonal planes.

Let us first consider the drops near a linear edge. Such drops can coalesce with the other drops sitting in a halfplane. The edge drops can thus be considered as particular drops of the same plane but with a vapor concentration profile that is now two-dimensional. Observation (Figs. [2][START_REF] Aitken | Proc. R. Soc. Edinburgh[END_REF] shows that the corresponding drop pattern exhibits the features of scaling during growth: uniform radius, drop inter-distance on the order of the radius. Such scaling can be verified by the constancy of the drop surface coverage

𝜀 ! = ! ! ! ! ! !
during drop pattern evolution. The summation is made on the edge condensing surface, S E . The latter is not constant during evolution. Its determination can be performed by making use of а method based on Voronoi polygons or Dirichlet tessellation [START_REF] Okabe | Spatial Tessellations Concepts and Applications of Voronoi Diagram[END_REF]. Such а polygon is the smallest convex polygon surrounding а drop whose sides are the bisectors of the lines between the drops and its neighbors. The edge surface can thus be considered as the total surface of the Voronoi polygons of the edge drops (Fig. 4c).

Note that a good approximation of the ε 2 calculation can be obtained from the evaluation of the line surface coverage of the edge drops,

𝜖 ! = ! ! ! !
. The summation is made along the edge of length L removing the two corner drops. The edge surface can then be considered as a band of length L and constant width w, corresponding to the mean extent of the Voronoi polygons perpendicular to the edge. From the Voronoi construction, w=α<R>, with α a proportionality constant on order two. One thus obtains S T ∼L<R> and

𝜖 ! = ! ! ! ! ∝!!!!
. Making use of the evaluation

< 𝑅 >= ! ! ! ! ! , one readily obtains 𝜖 ! = ! !!
𝜖 ! . Results are reported in Fig. 4a for substrate P1 and Fig. 4b for substrate P2. Constant surface coverage is found for the edge zone with both ε 2 (= 0.56 ± 0.02 for P1) and ε 1 (= 0.78 ± 0.01 for P1 and 0.71 ± 0.01 for P2). From the ratio ε 2 / ε 1 one determines α = 2.1 ± 0.1, the expected value.

One then notes that the mean radius can also be written as

< 𝑅 >= ! ! ! ! ! ! . ( 17
)
The vapor concentration profiles of the edge drops overlap, then the assumption of equivalent film holds and

𝑅 ! ~𝑉!,! ~𝑡 !
, with V T,E the condensed volume near the edge. One thus eventually gets the growth law <R> = k E t, similar to Eq. ( 14), however with a different prefactor k E corresponding to a different mean vapor profile on the drops. In the equivalent film approximation, one has two perpendicular linear profiles, one directed perpendicular to the condensing plane, the other perpendicular to it.

Note that growth near a linear edge is different from 1-D growth (as e.g. drops growing on a very thin thread)

where line coverage ε 1 is constant or 𝑅 = constant. In this case Eq. ( 13) can be rewritten as < 𝑅 >=

! ! ! ! = ! ! ! ! ! ! .
The first term is proportional to the condensed volume V T ∼t and the second is 1/<R>, giving <R>∼t 1/2 .

Let us now consider the case where the edge is a corner. This case is not so much different from the linear edge case, although there is only one drop growing at a corner. The corner drop can be considered as a particular drop of a linear edge with a vapor concentration profile that is now three-dimensional. This drop undergoes coalescence with other drops from two different edges and drops from the plane (see Fig. 2), leading to constant surface coverage (= 0.62 ± 0.02, see Fig. 4a). Then the film approximation holds and growth still follows Eq. ( 14).

The estimation of the gradient near the edge depends on the particular edge geometry and needs to solve the Laplace equation, Eq. (3). A theoretical estimation is out of the scope of the present study. The solution for a 2D arrangement will be performed numerically in the next section V. In order to highlight the vapor pressure dependence of the gradient, one defines a new mean boundary layer thickness, 𝜁 ! , such as (Eq. ( 4)),

! ! ∇𝑐 ! . 𝑛𝑑𝑆 ! = ! ! ! ! ! ! !
(S is the drop-air interface). Equations (14-15) can thus still hold for a droplet pattern near a discontinuity, with a new factor 𝑘 ! :

𝑘 ! = ! ! ! !(!) ! ! ! ! ! ! ! ! ! ! . ( 18
)
This factor is different according to the type of discontinuities.

III. MATERIALS AND METHODS

Condensation experiments are performed on a cooled horizontal substrate in order to get rid of the droplets detachment and sliding along the substrate. The study is limited to drops size lower or on the same order than the water capillary length . It corresponds to having negligible gravity effects on the shape of the drop.

A. Condensation chambers and observation set up

Two different test chambers and optics are used, depending on the length scale investigated. c  high resolution CCD color camera PixeLink (PL B776F) connected to a computer. This camera is equipped with a Pentax Megapixel lens with a 6 mm focus length to get a ×8 magnification at 5 cm from the substrate (30 px/mm).

The latter is put on an electrolytic copper block cooled by a Peltier element. The thermal contact is ensured either by a small layer of water or by thermal grease (a silicone-free heat sink compound). Dew condenses from the room ambient air whose temperature T a and air relative humidity RH is constant during the experiment time within ± 0.5 °C and 3%, respectively. The temperature of the substrate is measured by a thermocouple taped on it.

Experiment type 2. For larger droplets (typical range 0.1-5 mm), the above arrangement is enclosed in a large Plexiglas chamber, where air temperature and RH is maintained constant. The same optical system as for experiment type 1 is used, however the distance between the substrate and the lens is larger ( Although the characteristics of humid air can be monitored, it is not possible to control in each experiment the exact conditions of air flows around the substrate. To get rid of this uncertainty, the evolution of droplet radius at the substrate boundaries will be rescaled by the corresponding droplet radius evolution in the central part of the substrate. Both evolutions are expected to be linear according to section II-E.

The images are analyzed with an image analysis software (ImageJ) to obtain the mean surface of the droplets in a given image area. The radius is that of a spherical cap seen from above. The uncertainties in the drop radius measurements correspond to (i) optical resolution, from 0.4% for large (mm) drops to 4% for the smaller (0.1 mm) drops, (ii) number of drops for calculating the average, which gives smaller uncertainties for small drops than with large drops, (iii) irregularities of air convection. The uncertainties (i) and (ii) compensate to give an overall uncertainty of about 4%, whereas the uncertainty (iii) is difficult to estimate. We decided to report in the figures the error bars corresponding only to the uncertainty of measurements (4%). In the fitting procedure, we report the statistical uncertainty corresponding to two standard deviations (95% confidence). In total, 37 sets of experiments have been performed. The reproducibility is on order of 10% when droplet evolution at the boundaries is rescaled by the corresponding evolution in the center of the substrate (see section IV and Table 2).

B. Condensation substrates

Different substrates are used to evidence various types of discontinuities. A 0.1 mm thick PP foil (G2 substrate) is stuck with a thin water layer on the above duralumin substrate. Only corner and linear edges were concerned with this coating, not the groove. (iii) A polymethyl methacrylate plate (G3 substrate, commercial name Plexiglas), with the same geometrical characteristics than the above G1 substrate. It is stuck on the substrate holder with a thin water layer.

The roughness of the above substrates is the same on the flat and on the edge regions and has been measured by an optical profilometer. The results are reported in Table 1. The mean contact angles on water on the above substrates have been measured by two methods, looking at the shape of the drop on (i) an inclined substrate at the sliding onset and (ii) when pushing or pulling water on a horizontal substrate with a syringe. The results are the same within the uncertainties. The mean values for both methods are reported in Table 1. These values are typical of substrates used in the open air or an industrial environment and ensure dropwise condensation. Except for PMMA, the advancing contact angles are close to 90°. The hysteresis of the contact angle is correlated with the surface roughness, as expected.

IV. OBSERVATION AND ANALYSES

We comment in the following the different evolutions corresponding to the different types of discontinuities (corner, edge, groove, scratch, thermal). Condensation proceeds on a very long time period corresponding to the stage (iii) of the self-similar growth (Figs. 2 and3). Then the short time periods of the nucleation phase (i) and the individual growth stage (ii) can be neglected. In the center of a 2D substrate the evolution of the drop mean radius can thus be fitted to a linear growth law, consistent with Eq. ( 14). From Eq. ( 15 conditions. With such a rescaling, the reproducibility of experiments remains within 10%. This ratio is listed in Table 2 and discussed for the different experiments in section VI.

In the following we report the different growth laws for the substrates as described in section II.

A. Corner and edges on P1 parallelepiped

In Fig. 2c is reported a photo of water condensation on P1 substrate. The drops on corner and linear edges exhibit clearly larger sizes than the drops close to but apart from the discontinuities.

Seven sets of experiments have been performed. A typical evolution of the mean drop radius on corners, edges and the central region is reported in Fig. 4a. The values are averaged on the 4 edges and corners. As expected, it is observed that droplet growth is faster at the substrate corners than at the edges, the latter giving faster growth than in the central region. A fit to Eq. ( 14) with k as adjustable parameters give k C = (12 ± 0.4) 10 -3 mm/min (average on four corners), k E = (8.3 ± 0.2) 10 -3 mm/min (edges), k M = (3.52 ± 0.04) 10 -3 mm/min (central region). The ratios to the central region are reported in Table 2.

B. Edges and thermal borders on P2 diamond

In Fig. 2d is reported a photo of water condensation on P2 substrate. The drops on thermal and geometrical corner and linear edges exhibit clearly larger sizes than the drops close to but apart from the discontinuities.

One set of experiments has been performed in this configuration. In Fig. 4b are reported the evolution of the mean drop radius on edges, border of the thermally inhibited condensation (thermal) and the central region. The values are averaged on all 4 edges and thermal boundaries. As above with parallelepiped P1, it is observed that droplet growth is faster at the substrate edges than in the central region. Growth at the thermal borders is faster than in the central region but slower than at the edges. A fit to Eq. ( 14) with k as adjustable parameters give k E = (5.0 ± 0.2) 10 -3 mm/min (edges), k T = (4.1 ± 0.1) 10 -3 mm/min (thermal border), k M = (1.8 ± 0.15) 10 -3 mm/min (central region). The ratios to the central region are reported in Table 2.

C. Corner, edge, groove and scratch on G1 and G2

In Fig. 3b is reported a photo of water condensation on the G1 substrate (duralumin). The drops on outer linear edges exhibit clearly larger sizes than the drops close to, but apart from the discontinuities. The drops near the groove, in the upper region, also show larger drops. In contrast, drops near the groove edge in the inner region show smaller drops. The drops in the inner central region of the groove and on the scratch have similar size than in the central region of the substrate. The scratch gives somewhat aligned droplets.

Numerous experiments (24) have been performed on G1. Evolutions of the droplet radius are reported in Fig. 5a for a typical experiment. The radius is averaged on the two upper plate corners, the upper plate edge and the central region. Also reported are the drop radius evolution on the upper edge of the groove, in two locations 1 and 2 (edge groove+ (1) and edge groove+ (2)), the lower part of the groove edges (edge groove-) and the central part of the groove (central groove). The scratch gives somewhat aligned droplets (see Fig. 3b) but their evolution is similar to the central part of the plate. As reported in (6), a scratch induces a 1D growth only in the early stages of growth when the drop diameter is less than the scratch thickness. For larger drop sizes, growth is the same as on a 2D surface.

As above for P1 and P2 droplets grow faster at the substrate corners than at the edges (plate and groove edge), the latter giving faster growth than in the central region. The central part of the groove exhibits a slighter slower growth than the central part of the plate. The lower groove edge gives the slower growth. A fit to Eq. ( 14) with k as adjustable parameters give k C = (28 ± 2) 10 -3 mm/min (average on two corners), k E = (16.1 ± 0.4) 10 -3 mm/min (edges), k G+ = (9.8 ± 0.4) 10 -3 mm/min (groove edges), k M = (6.2 ± 0.4) 10 -3 mm/min (central region), k GM = (5.3 ± 0.2) 10 -3 mm/min (groove central region), k G-= (3.2 ± 0.2) 10 -3 mm/min (groove lower edge). The ratios to the plate central region are reported in Table 2. Note that a step-like evolution is visible on the corner drops. These discrete steps are much larger than the experimental error, and reproducible. Each step corresponds to a coalescence event with a neighboring drop. It is a characteristic feature of the corners, where the evolution of a single drop is observed, whereas for the other locations the coalescence events are averaged on a line (edges) or on a surface (middle) ; they remain only barely visible on edges.

The G2 substrate (same as G1 but coated with polypropylene foil), shows the same kind of behavior as on the G1 substrate, although water drops exhibit a larger contact angle (Table 1). Three sets of experiments have been performed. A fit to Eq. ( 14) with k as adjustable parameters give k C = (80 ± 2.5) 10 -3 mm/min (average on two corners), k E = (46 ± 1) 10 -3 mm/min (edges), k M = (15.3 ± 0.2) 10 -3 mm/min (central region). The growth rates ratios corresponding to the corners and the edges region are reported in Table 2.

D. G3 low conductive plate

Two sets of experiments have been carried out with the G3 plate. They do not give any of the above observed edge effects as can be seen in Fig. 3c. The drop diameters show the same increase on corners, edges and central part.

However, growth is accelerated inside the groove. This striking observation can be understood when considering the quite different values [START_REF]CRC Handbook of Chemistry and Physics[END_REF] of thermal conductivity, λ, for metallic substrates (duralumin: 160 Wm -1 K -1 ; brass: 120 One can express the different flux per unit surface as

Wm -1 K -1 )
! ! ! ! = 𝜆 ! ! ! !! ! ! ! and 𝑃 𝑐 𝑆 𝑇 = 𝐿 𝑆 𝑇 𝑑𝑚 𝑑𝑡 = 𝐿𝜚 𝑤 𝑑ℎ 𝑑𝑡 . ( 19
)
Here ρ w (= 1×10 3 kg.m -3 ) is the density of liquid water, L (= 2400 kJ.kg -1 ) the latent heat of condensation and λ a (= 0.026 Wm -1 K -1 ) the air thermal conductivity [START_REF]CRC Handbook of Chemistry and Physics[END_REF]. The thermal boundary layer in air, δΤ , corresponds to the thickness where the transport of heat by conduction becomes more efficient than by convection or a Peclet number Pe T =UδΤ/D T <1 (U is air velocity, D T = 2.2×10 -5 m 2 .s -1 [START_REF]CRC Handbook of Chemistry and Physics[END_REF] is air thermal diffusivity). Although the thermal boundary layer is of different nature than the diffusive boundary layer, which corresponds to the diffusion of water molecules in air, characterized by the diffusion coefficient D, it happens that the value D = 2.4×10 -5 m.s -1 [START_REF]CRC Handbook of Chemistry and Physics[END_REF] is close to D T . It results that δΤ ≈ ζ (≈ 1.8 mm for natural convection, as discussed in details in next section IV-E).

Making use of Eq. ( 9), one obtains

! ! ! ! = 𝐿 !∆! ! .
The flux P can be expressed as the conduction through the substrate of thickness e in contact with the Peltier element at temperature T 0 ,

! ! ! = 𝜆 ! ! !! ! ! . ( 20
)
In the present experiment where T a = 25°C, RH = 62%, T s = 16°C, T 0 = 13°C (Δp = 0.20 kPa) corresponding to Δc = 1.6×10 -3 kg.m -3 , the ratio air conduction over condensation mm/min. Drops are seen to grow faster in the groove than on the surface because the conductive cooling heat flux is here more important. With a growth rate in the groove k GM = (7.5 ± 0.6) 10 -3 mm/min, the growth rate enhancement 2). This value compares well with the factor 2 that is expected from the cooling heat flux from Eq. ( 20), assessing that the droplet growth is indeed limited by the low thermal conductivity of PMMA.

! ! ! ! = ! ! (! ! !! ! ) !"∆! ≈ 2
is k GM / k M = 1.7 ± 0.2 (Table

E. Boundary layer thickness and growth rate

The concentration boundary layer thickness ζ corresponds to the extent of the region near the substrate, where the transport of water molecules by diffusion becomes more efficient than by convection. In other words, it corresponds to a Peclet number Pe C =Uζ/D <1 (U is air velocity).

One can have a rough estimation of ζ by a scaling analysis of the natural convection above a horizontal cooled plate [START_REF] Gersten | Strömungsmechanik, Grundlagen der Impuls-, Wärme-und Stoff-Ubertragung aus Asymptotischer Sicht[END_REF]. Due to buoyancy effects, air flow will be confined in a hydrodynamic boundary layer of thickness δ. The latter is a function of the Grashof number Gr =

!"∆!! ! ! !
as δ ∼L Gr -1/5 . Here L (≈ 20mm) is the plate characteristic length, ΔT = T a -T s , β = 2/(T s +T a ) = 3.4×10 -3 K -1 is the air volumetric thermal expansion coefficient (air considered as ideal gas) and ν = 1.6 10 -5 m 2 /s is the air kinematic viscosity [START_REF]CRC Handbook of Chemistry and Physics[END_REF]. These values give Gr ≈ 13000 and δ ≈ 3 mm with ΔT ≈ 10 K. As δ ∼ ΔT 0.2 , its value is only weakly sensitive to temperature. The maximal velocity in the hydrodynamic layer is given by U m ~ (δ β g ΔT) 1/2 ≈ 3 cm/s [START_REF] Gersten | Strömungsmechanik, Grundlagen der Impuls-, Wärme-und Stoff-Ubertragung aus Asymptotischer Sicht[END_REF]. With D = 2.4×10 -5 m.s -1 [START_REF]CRC Handbook of Chemistry and Physics[END_REF] the diffusion constant of water in air, Pe C ≈ 3 for U=Um. Assuming that the air velocity decreases near the plate following a parabolic flow, the boundary layer thickness ζ can be deduced from Pe C (z) =

𝑈(𝑧)𝑧 ! = ! ! ! ! ! !/! ! = 1: 𝜁~! ! !/! ! !"Δ! !/! !/! . ( 21
)
The ζ value is only weakly temperature dependent. For ΔT ≈ 10K, one finds ζ ≈ 1.1 mm. It results that for droplets of radius lower than 1.1 mm, growth remains limited by diffusion. When the drop diameter becomes larger, a thorough description of the process would need a fine description of the convective flow in the exact experimental configuration.

The above expression of ζ , Eq. ( 21), can be inserted in Eq. ( 15) to calculate the growth rate k, whose value can be then compared to the experimental value of k m in the central part of the substrate. In the dependence of the surface coverage with the contact angle, 𝜀 ! =1-(θ (deg.) /200) [12], one has to consider the advancing contact angle as drops are growing. The values are listed in Table 2. One notes that the k M experimental values are in general significantly larger than the calculated values and show significant variations, even for similar substrates under same conditions (G1, G2 and P 1 , P 2 ). In addition to the fact that the calculated values originate from scaling (approximate estimation, Eq. ( 21)), variations do exist because of uncontrolled air flows around the substrate. Indeed the experiments were not designed to control air flows (it is a quite difficult task). Hydrodynamics is then not simply natural convection and can vary in an uncontrolled way from experiment to experiment.

F. Condensation on an inclined substrate

In all above-mentioned experiments the substrate was horizontal in order to focus on the edge effects only. In this section we present an example of a condensation experiment on an inclined substrate, in order to show qualitatively the combined action of edge effects and gravity. Figure 6 shows the condensation pattern on a silicon wafer inclined at 30° from horizontal. The droplets situated near the upper horizontal edge have grown faster than their neighboring droplets. As a consequence, they reach sooner the critical size necessary for detachment, and, acting as wipers, collect the other drops as they slide down. The condensing surface is thus continuously renewed, and the condensation process is sustained.

This "self-cleaning" effect should have practical implications on the water collection efficiency of inclined surfaces. It remains, however, to be precisely quantified. As a matter of fact, it has been reported that dew collectors of origami form with many edges can collect up to 400% more water than simple planar surfaces for small dew events [START_REF] Beysens | [END_REF]. The question arises about spines or sharp needles that are encountered in some plants to favor natural dew condensation and collection. In order to improve water harvest efficiency one could also combine the edge effects of the condensation substrate with the wettability and geometry properties as studied in [18]. A coating with small contact angle hysteresis placed on the upper borders of a condenser should promote the early detachment of small drops, thus enhancing the wiper effect.

V. SIMULATIONS

In the simulation the condensing plate is supposed either perfectly conductive (isothermal) or adiabatic such as only mass diffusion in humid air above the plate matters. We consider a "snapshot" where the droplet configuration is fixed, the size of the droplet are set and droplets are not growing. They are placed in various configurations with different concentration boundary layer geometries. It is also assumed that inside the concentration boundary layer, the transport of the molecules by natural convection is negligible compared to their transport by diffusion (Pe C <1).

The validity of this assumption has been assessed above in section IV-E by performing a scaling analysis of the natural convection above a horizontal cooled plate.

This situation thus corresponds to solve only the diffusion equation in a stationary state. As a result of the calculation, the drops are receiving a mass flux that characterizes their rate of growth during the snapshot small time interval in this fixed configuration.

A. Model geometry and boundary conditions

The comparison of the growth rates of drops at different geometrical and thermal boundaries is inferred from the value of the mean water vapor concentration gradient at the drop perimeter, Eq. ( 4). To calculate this value, we solve the steady state diffusion equation Eq. ( 3) in two dimensions (2D) for water vapor concentration c : Δc = 0, using a finite element method implemented in Matlab (pdetool). A 2D simplification is consistent with the fact that the droplets close to edges are aligned (see Figs. 23). It is not, however, the case for the droplets at the corners and is a simplification for the central part.

The geometry of the domain is depicted in Figs. 7ab. The boundaries of the domain are (i) the solid surfaces of the substrate where drops are growing and (ii) the surface boundaries where water vapor concentration is kept constant. These surfaces correspond to the position of the concentration boundary layer as estimated previously in section IV.E. The values that are used in the simulation ( 1 and 2 mm) are typical of the boundary layer thickness.

We address two substrate geometries, an edge (Fig. 7a) and a groove (Fig. 7b), to mimic the geometry of the AL plate (Fig. 3). On the substrate, hemispherical drops of same diameter 2R = 200µm are distributed with a distance between the edges of two neighboring drops equal to 50µm). It means that each drop is at the center of a box of width d = 250 µm, corresponding to a mean interdrop distance <d> = d. This configuration correspond to a drop surface coverage ε 2 = 0.50, as observed during the coalescence -driven, self-similar coalescence stage (iii). The drops are situated within a distance of 50 µm from the boundary.

For the edge case, the thickness of the substrate is set to 2 mm. On the substrate walls between the droplets, we impose a zero transversal flux, i.e. a zero concentration gradient. Symmetry dictates that on the boundaries X = 3 mm and Y = 0 mm, the transversal flux is zero. On the boundaries Y = 3mm and X = 0, a uniform concentration c∞ = 2 (in arbitrary units) is imposed. These surfaces are situated at a distance of 1 mm from the substrate, corresponding to the case ζ >> <d>. On the drops surfaces, a saturated concentration c s =1 is assumed. This yields a ratio 𝑐 ! /c s typical of the ratio (p∞ /p s ) used in the experiments. In Figs. 7ab, the local diffusive flux vector is depicted as arrows, the colors represent the intensity of the local concentration gradient. The maximal concentration gradient intensity is found at the surface of the droplets situated close to the edge E, and a decreasing concentration gradient is observed with increasing drop distance from the edge.

The groove (Fig. 7b) is 1mm in depth and 4 mm in width. For symmetry reasons, we simulated only half of the groove. As for the edge, the concentration is set to c∞ = 2 at Y = 1mm from the substrate. The concentration is set to c s = 1 on the surface of the drops. In agreement with the preceding cases, the concentration gradient amplitude is maximized on the drop G+ situated at the edge of the groove. In contrast, it is the smaller for the drops inside the groove, with decreasing values from the inner groove edge G-towards the inner groove middle GM.

where drops cannot grow. As for the edge and the groove, the concentration is set to c∞ = 2 on the surface at Y = 2mm, situated at 1mm from the top of the substrate. The concentration is set to c s =1 on the surface of the drops. The transversal concentration gradient is set to zero on the symmetry axis X = 0, on the solid surfaces of the substrate, and on the boundary (Y = 0, X<1mm).

It can be seen on Fig. 7c that similarly to the preceding cases, the concentration gradient is maximized on the drops situated at the edge of the (thermal) boundary T. It decreases towards the middle M of the drop pattern.

B. Comparison with experiments

Following Eqs. (2,[START_REF] Rayleigh | [END_REF] for the monomer flux and drop volume evolution dV/dt, we thus compute the following integral :

𝐼 = ! ! ∇𝑐 ! . 𝑛𝑑𝑆 ! , ( 22
)
of the concentration gradient on the different individual drop surfaces to determine a quantity which is proportional to the mean drop volume growth rate dV/dt (Eq. ( 4)) and thus to d<R>/dt = k from Eq. ( 16).

In order to compare with the experiments, the integral of the concentration gradient is computed on drops marked on Fig. 7, M (central part of the substrate), E (edge), G+ (outer edge of the groove) G-(inner edge of the groove),

GM (central part of the groove), T (thermal discontinuity).

The ratio of each integrals I to the integral I M corresponding to the substrate central is independent of the value of the vapor diffusion coefficient D and of supersaturation, see Eqs. (15 -18). It is listed in Table 2 where it can be compared to the corresponding experimental values k J /k M . The values compare relatively well taking into account the fact that the simulation is 2D. There is one exception concerning k G-/k M (the groove inner edge) where the calculated value is 7 times lower than the measured value. This discrepancy is due to the assumption in the simulation of the boundary layer above the groove. In the reality, the layer should curve towards the groove, thus enhancing the growth rate.

VI. CONCLUDING REMARKS

From this study it appears that droplet growth on a cooled substrate can be significantly modified by discontinuities. They can be of geometric or thermal nature and growth can be enhanced or reduced. In the case where mass diffusion around the drops controls growth, drops can collect more or less moisture near a boundary than in the middle of the substrate depending on the shape and nature of the discontinuity. In certain cases, the growth enhancement can reach nearly 500% on edges or corners.

On the other hand, these boundary effects can disappear when another process than mass diffusion limits growth. This is for example the case for substrates where the cooling heat flux is limited by the low thermal conductivity of the substrate (PMMA substrate in this study) or strong heat exchange in a windy atmosphere when cooling is ensured by radiation deficit (natural dew).

TABLES

Table 1. Surface roughness (root mean square RMS) of the materials with contact angles of water.

Experiments type1 :Experiments type 2 :

 type12 (a) A brass rectangular parallelepiped (P1 substrate, Fig.2a) of 17.5 mm height, top surface of 15.1 mm x 10 mm is covered by an adhesive grey foil of polyvinyl chloride (PVC) with 0.14 mm thickness. This sample provides a geometrical discontinuity of corner and linear edge type. (b) Two aluminum alloy (duralumin) massive triangles (P2 substrate, Fig.2b), separated by a gap, forming a diamond, are covered by an adhesive brown foil of polypropylene (PP) with 0.02 mm thickness. In addition to geometrical discontinuities, two thermal discontinuities are present along the gap between the triangles where the foil cannot be cooled. Geometrical discontinuities are realized in different type of materials with different wetting and thermal properties. (i) A square duralumin plate (G1 substrate, Fig.3a), 2 mm thickness and 173.2 mm side (same size as the substrate holder) provides different kind of geometrical discontinuities: U-groove at 40 mm from the left edge (width: 10 mm, depth: 1 mm) and a linear scratch of about 0.1 mm depth in the center of the plate. (ii)

,

  ), this prefactor k is proportional to the supersaturation Δ𝑝 = 𝑝 ! -𝑝 ! and the water vapor diffusion constant in air, D. It is inversely proportional to the concentration boundary layer thickness, ζ. As discussed in section II-E, the effect of discontinuity does not change the mean droplet growth law on the discontinuity, only the prefactor k is modified into 𝑘 ! . The experiments, which have been performed under different conditions of temperature (T a , T s ), give different boundary layer thicknesses and different condensation parameters RH or Δ𝑝. For comparison and discussion, the growth rates 𝑘 ! at different locations (E) are thus rescaled by the value, k M , measured at the central, middle part (M) of the substrate, corresponding to the same parameters (air flow, T a , T s , RH, and Δ𝑝). The ratio with ζ E, ζ M the mean boundary layer thickness at E, M, locations can thus be compared without accounting for the different experimental

  and PMMA (0.19 Wm -1 K -1 ) [15]. The cooling heat flux P per unit surface corresponds to maintain a constant temperature at the substrate surface by compensating for air heating (heat flux P a ) and condensation latent heat (P c ) : 𝑃 + 𝑃 ! + 𝑃 ! = 0 .

. 5 .

 5 Thus nearly most of the heat flux P/S T (≈ 300 W.m -2 ) is used for cooling the substrate. From Eqs. (19-20) one can estimate the limiting growth rate dh/dt ≈ P/( 𝐿𝜚 ! 3.5S T ) ≈ 2×10 -3 mm/min This is a rough estimation as it is obtained by subtracting two large heat fluxes. However, the growth rate is on the same order as the rate found in the central part of G3: k M = (4.5 ± 0.2)10 -3

FIG. 1 .FIG. 2 .FIG. 3 .

 123 FIG. 1. (Color online) Schematics of different regimes for the droplet growth on a substrate : (a) single drop evolution ; (b) growth in a pattern with overlapping water vapor concentration profile, and film of average thickness h.

FIG. 4 .

 4 FIG. 4. (Color online) (a-b) Left ordinate: evolution of the mean drop radius <R> on corners, edges and central area. The lines are fits to Eq. (14). Right ordinate: evolution of the drop coverage on corners, edges and central area (surface coverage: full lines; interrupted line: edge linear coverage). The lines are fits to a constant. (a): P1 substrate (T a = 22.6°C , T s = 4.8°C , RH = 44% ). (b): P2 substrate (T a = 22.6°C , T s = 4.8°C , RH = 44 %). (c) Voronoi polygon construction (P1, t = 60 min) for corner, edge and central region, showing the band approximation with length L and thickness w (see text).

FIG. 5 .

 5 FIG. 5. (Color online) Evolution of the mean drop radius <R> on plate corners, edges, upper and lower groove edges and plate and groove central areas (see text). The lines are fits to Eq. (14). (a) G1 substrate (T a = 25°C , T s = 15°C , RH = 78% ). (b) G2 substrate (T a = 25°C, T s = 16°C, RH = 62%). (The step-like evolution on corners correspond to coalescence with a neighboring drop).

FIG. 6 .

 6 FIG. 6. (Color online) Condensation on a smooth substrate at 30° from horizontal (square silicon wafer of 21 mm side; 156 min; T a = 26°C, RH = 60%, T s = 1.2°C ). At the top horizontal edge, the drops grow faster, they thus reach sooner the critical size for detachment and slide down, collecting the other drops. On the fresh bare area a new generation of drops nucleates and grows.

  14 cm) giving a magnification of 42 px/mm. The substrate holder is a 2 mm thick stainless square steel plate of 173.2 x 173.2 mm size, screwed with

thermal grease on a electrolytic copper plate of same size in contact with a Peltier element thermostat. The hot side of the latter is cooled by a fan directed on a water basin, which ensures large and stable air humidity ( RH >76%) and temperature. Air and surface temperatures together with humidity data are recorded by a data logger (Testo 454) coupled to a computer.

Table 2 .

 2 Values of radius growth rate k M on substrate central region (exp.: experimental value; calc.: calculated from Eq. (15)), k E (substrate edge). Comparison is also given between the experimental ratios k E /k M (overall uncertainties are within 10%) and the simulated ratios I/I M . Δp is the difference p ∞ -p S (see text). The values under brackets for G3 [(1) and (2)] correspond to the ratio of heat fluxes for low conductivity PMMA substrate. The missing data correspond to non-existent geometries in the simulation or in the substrates.

	Materials	substrate roughness	Contact angles (deg.)
					RMS (nm)	advancing receeding
	Duralumin	G1		460	84.5 ± 5.5 21.0 ± 4.5
		PP	G2		150	98.0 ± 2.5 65.0 ± 5.5
	PMMA	G3		100	70.0 ± 4.5 40.0 ± 3.0
	PVC	P1		1600	86.0 ± 4.5 31.0 ± 4.5
		PP	P2		180	94.5 ± 2.5 67.5 ± 5.0
			G1	G2	G3	P 1	P 2	I/I M
	k M	exp.	6.2	15.3	4.5	3.5	1.8
	(10 -3 mm.min. -1 )	calc.	22	9.0	6.7	11.4	9.8
	k C /k M		4.6	5.2	1 (1)	3.4	-	-
	k E /k M		2.6	3.0	1 (1)	2.4	2.7	1.90
	k G+ /k M		1.6	-	1 (1)	-	-	1.66
	k GM /k M		0.86	-	1.7 (2)	-	-	0.43
	k G-/k M		0.51	-	1.7 (2)	-	-	0.072
	k T /k M		-	-	-	-	2.2	2.64
	T a (°C)		25	23	25	22.6	22.6
	T s (°C)		15	12.5	16	4.8	4.8
	RH (%)		78	76	62	44	44
	Δp (kPa)		0.80	0.40	0.20	0.35	0.35

ACKNOWLEDGMENTS

We gratefully thank Martin Hendel for his valuable corrections and for his critical reading, helpful remarks and relevant comments.


Konstantin E Avrachenkov
email: k.avrachenkov@inria.fr

Vivek S Borkar
email: borkar.vs@gmail.com

Whittle Index Policy for Crawling Ephemeral Content

Keywords: Whittle Index, Search Engine, Crawler, Ephemeral Content Index de Whittle, Moteur de Recherche, Crawler, Robot

We consider a task of scheduling a crawler to retrieve content from several sites with ephemeral content. A user typically loses interest in ephemeral content, like news or posts at social network groups, after several days or hours. Thus, development of timely crawling policy for such ephemeral information sources is very important. We first formulate this problem as an optimal control problem with average reward. The reward can be measured in the number of clicks or relevant search requests. The problem in its initial formulation suffers from the curse of dimensionality and quickly becomes intractable even with moderate number of information sources. Fortunately, this problem admits a Whittle index, which leads to problem decomposition and to a very simple and efficient crawling policy. We derive the Whittle index and provide its theoretical justification.

Introduction

Nowadays an overwhelming majority of people find new information on the web at news sites, blogs, forums and social networking groups. Moreover, most information consumed is ephemeral in nature, that is, people tend to lose their interest in the content in several days or hours. The interest in a content can be measured in terms of clicks or number of relevant search requests. It has been demonstrated that the interest decreases exponentially over time [START_REF] Goyal | Learning Influence Probabilities in Social Networks[END_REF][START_REF] Lefortier | Timely Crawling of Highquality Ephemeral New Content[END_REF][START_REF] Moon | Refining Recency Search Results with User Click Feedback[END_REF].

In a series of works (see e.g., [START_REF] Cho | Synchronizing a Database to Improve Freshness[END_REF][START_REF] Cho | Effective Change Detection Using Sampling[END_REF][START_REF] Cho | Effective Page Refresh Policies for Web Crawlers[END_REF][START_REF] Olston | Web Crawling[END_REF] and references therein) the authors address the problem of refreshing documents in a database. However, these works do not consider the ephemeral nature of the information. Motivated by this challenge, the authors of [START_REF] Lefortier | Timely Crawling of Highquality Ephemeral New Content[END_REF] suggest a procedure for optimal crawling of ephemeral content. Specifically, the authors of [START_REF] Lefortier | Timely Crawling of Highquality Ephemeral New Content[END_REF] formulate an optimization problem for finding optimal frequencies of crawling for various information sources.

The approach presented in [START_REF] Lefortier | Timely Crawling of Highquality Ephemeral New Content[END_REF] is static, in the sense that the distribution of crawling effort among the content sources is always the same independent of the time epoch and, in particular, does not depend on any 'state variable(s)' evolving with time. With a dynamic policy, for instance, if there is not much new material on the principal information sources, the crawler could spend some time to crawl the sources with less popular content but which nevertheless bring noticeable rate of clicks or increase information diversity. Therefore, in the present work we suggest a dynamic formulation of the problem as an optimal control problem with average reward. The direct application of dynamic programming quickly becomes intractable even with moderate number of information sources, due to the so-called curse of dimensionality. Fortunately, the problem admits a Whittle index, which leads to problem decomposition and to a very simple and efficient crawling policy. We derive the Whittle index and provide its theoretical justification.

In [START_REF] Avrachenkov | Optimal Threshold Control by the Robots of Web Search Engines with Obsolescence of Documents[END_REF][START_REF] Liu | Optimization Issues in Web Search Engines[END_REF][START_REF] Talim | Controlling the Robots of Web Search Engines[END_REF] the authors study the interaction between the crawler and the indexing engine by means of optimization and control theoretic approaches. One of interesting future research directions is to take into account the indexing engine dynamics in the present context.

The general concept of the Whittle index was introduced by P. Whittle in [START_REF] Whittle | Restless Bandits: Activity Allocation in a Changing World[END_REF]. This has been a very successful heuristic for restless bandits, which, while suboptimal in general, is provably optimal in an asymptotic sense [START_REF] Verloop | Asymptotically Optimal Priority Policies for Indexable and Non-indexable Restless Bandits[END_REF][START_REF] Weber | On an Index Policy for Restless Bandits[END_REF] and has good empirical performance. It and its variants have been used extensively in logistical and engineering applications, some recent instances of the latter in communications and control being for sensor scheduling [START_REF] Nino-Mora | Sensor Scheduling for Hunting Elusive Hiding Targets via Whittle's Restless Bandit Index Policy[END_REF], multi-UAV coordination [START_REF] Ny | Multi-UAV Dynamic Routing with Partial Observations Using Restless Bandit Allocation Indices[END_REF], congestion control [START_REF] Avrachenkov | Congestion Control of TCP Flows in Internet Routers by Means of Index Policy[END_REF][START_REF] Avrachenkov | Infinite Horizon Optimal Impulsive Control with Applications to Internet Congestion Control[END_REF][START_REF] Jacko | Congestion Avoidance with Future-Path Information[END_REF], channel allocation in wireless networks [START_REF] Larranaga | Stochastic and Fluid Index Policies for Resource Allocation Problems[END_REF], cognitive radio [START_REF] Liu | Indexability of Restless Bandit Problems and Optimality of Whittle Index for Dynamic Multichannel Access[END_REF] and real-time wireless multicast [START_REF] Raghunathan | Index Policies for Real-time Multicast Scheduling for Wireless Bradcast Systems[END_REF]. Book length treatments of indexable restless bandits appear in [START_REF] Jacko | Dynamic Priority Allocation in Restless Bandit Models[END_REF][START_REF] Ruiz-Hernandez | Indexable Restless Bandits[END_REF].

Model

There are N sources of ephemeral content. A content at source i ∈ {1, ..., N } is published with an initial utility modelled by a nonnegative random variable ξ i and decreasing exponentially over time with a deterministic rate µ i . The new content arrives at source i ∈ {1, ..., N } according to a time-homogeneous Poisson process with rate Λ i . Thus, if source i's content is crawled τ time units after its creation, its utility is given by ξ i exp(-µ i τ ). The base utility ξ i is assumed independent identically distributed across contents at a given source, with a finite mean ξi . It is also assumed independent across sources. We assume that the crawler crawls periodically at multiples of time T > 0 and has to choose at each such instant which sources to crawl, subject to a constraint we shall soon specify. When the crawler crawls a content source, we assume that the crawling is done in an exhaustive manner. In such a case, the crawler obtains the following expected reward from crawling the content of source i:

u i = Λ i E[ξ i exp(-µ i τ )] = Λ i ξi µ i (1 -exp(-µ i T )). (1)
Set α i = exp(-µ i T ). Let us define the state of source i at time t as the total expected utility of its content, denoted by X i (t). Then, if we do not crawl source i at epoch t (formally, the control is v i (t) = 0 -we say the source is 'passive'), we obtain zero reward r i (X i (t), v i (t)) = 0 and the state evolves as follows:

X i (t + 1) = α i X i (t) + u i . (2)
On the other hand, if we crawl source i (formally, v i (t) = 1 -we say the source is 'active'), we obtain the expected reward r i (X i (t), v i (t)) = X i (t) and the next state of the source is given by

X i (t + 1) = u i . ( 3
)
Our aim is to maximize the long run average reward

lim sup t↑∞ N i=1 1 t t m=0 r(X i (t), v i (t)) (4)
subject to the constraint

lim sup t↑∞ N i=1 1 t t m=0 C i v i (t) = M (5)
for a prescribed M > 0. If C i = 1, i = 1, ..., N , this case can be interpreted as a constraint on the number of crawled sites per crawling period T and corresponds to the original Whittle framework for restless bandits [START_REF] Whittle | Restless Bandits: Activity Allocation in a Changing World[END_REF]. The case C i = 1 is slightly more general and can represent the situation when various sites have different limits on the crawling rates (typically specified in the file 'robots.txt'). This is a constrained average reward control problem [START_REF] Altman | Constrained Markov Decision Processes[END_REF][START_REF] Piunovskiy | Optimal Control of Random Sequences in Problems with Constraints[END_REF]. We address this problem in the framework of restless bandits and derive a simple index policy for the problem, which may be viewed as a variant of the celebrated Whittle index. In the next section, we recall the theory of Whittle index.

Whittle index

The original formulation of restless bandits is for discrete state space Markov chains, but we consider here Markov chains with closed domains (i.e., closure of an open set) S i ⊂ R d , d ≥ 1, as state space. The original motivation for the index policy remains valid nevertheless as long as we justify the associated dynamic programming equation, which we do. A deterministic dynamics such as ours is a special case, albeit degenerate. The fully stochastic case can be handled similarly and is detailed in the report [START_REF] Avrachenkov | Whittle Index Policy for Crawling Ephemeral Content[END_REF]. While we introduce the broader framework in a general set up, we use the same notation as above to highlight the correspondences. This should not cause any confusion. Thus consider resp. S i -valued processes X i (t), t ≥ 0, 1 ≤ i ≤ N , each with two possible dynamics, dubbed active and passive, wherein they are governed by transition kernels p i (dy|x), q i (dy|x) resp. These are assumed to be continous as maps x ∈ S i → P(S i ). (:= Inria the space of probability measures on S i with Prohorov topology). The control at time t is an

A := {0, 1} N -valued vector v(t) = [v 1 (t), • • • , v N (t)] ∈ A, with the understanding that v i (t) = 1 ⇐⇒ X i (t) is active.
In the original restless bandit problem, exactly N < N processes are active at any given time. The v i (t) are assumed to be adapted to the history, i.e., the σ-field σ(X i (s), s ≤ t; v i (s), s < t; 1 ≤ i ≤ N ). Let r i : S → R + , 1 ≤ i ≤ N, be reward functions so that a reward of r i (X i (t)) is accrued if process i is active at time t. The objective then is to maximize the long run average reward

lim sup t↑∞ N i=1 1 t t m=0 E[r i (X i (t))v i (t)].
This problem has state space × N i=1 S i . Whittle's heuristic among other things reduces the problem to separate control problems on S i . The idea is to relax the constraint of 'exactly N are active' to 'on the average, N are active', i.e., to

lim sup t↑∞ 1 t t s=0 E[ N i=1 v i (s)] = N .
This makes it a constrained average reward control problem [START_REF] Altman | Constrained Markov Decision Processes[END_REF][START_REF] Piunovskiy | Optimal Control of Random Sequences in Problems with Constraints[END_REF] which permits a relaxation to an unconstrained average reward problem by replacing the above reward by

lim sup t↑∞ N i=1 1 t t s=0 E[r i (X i (s))v i (s) + λ(N /N -v i (s))],
where λ ∈ R is the Lagrange multiplier. Motivated by this, Whittle introduced a 'subsidy' λ for passivity, i.e., a virtual reward for a process in passive mode. Replace the above control problem by N control problems with the ith problem for process X i (•) seeking to maximize over admissible v i (t), t ≥ 0, the reward

lim sup t↑∞ 1 t t s=0 E[r i (X i (t))v i (s) + λ(N /N -v i (s))]. (6)
The dynamic programming equation for this average reward problem is

V i (x) + β = max λ + q i (dy|x)V i (y), r i (x) + p i (dy|x)V i (y) . (7)
If this can be rigorously justified (which is not always easy), one defines B(λ) as the set of passive states, i.e., B(λ) :=

x : λ + q i (dy|x)V i (y) ≥ r i (x) + p i (dy|x)V i (y) .
If B(λ) increases monotonically from φ to S i as λ increases from -∞ to ∞, the problem is said to be Whittle indexable. The Whittle index for the ith process in state x i is then defined as

γ i (x i ) := {λ : λ + q i (dy|x i )V (y) = r i (x i ) + p i (dy|x i )V (y)}.
The so-called 'Whittle index policy' [START_REF] Whittle | Restless Bandits: Activity Allocation in a Changing World[END_REF] then is to set v i (t) = 1 for the i with the top N indices and v j (t) = 0 for the rest.

Dynamic programming equation

In view of the above, the first step is to justify the counterpart of ( 7) in our context. For this, we first note that

r i (x) = x, 1 ≤ i ≤ N . Further, let u * i := ui 1-αi > u i .
We argue that without loss of generality, we may take

S i = [u i , u * i ]. To see this, let X i (0) = x 0 . If x 0 ≤ u * i , it is easy to see that X i (t) ≤ α t i x 0 + (1 -α t i )u * i ↑ u * i ,
where the equality in the first inequality occurs only if source i is never crawled. On the other hand, if

x 0 > u * i , then X i (t) = α t i x 0 + (1 -α t i )u * i ↓ u * i as t ↑ ∞, if never crawled,
and reduces to the previous case if there is even a single crawl. Combining the two observations and recalling that we consider the long-run average criterion, we conclude that

x 0 / ∈ [u i , u * i ]
are transient and can be ignored. Thus we set

S i = [u i , u * i ].
Henceforth we focus on the average reward problem for source i. We do not delve into the justification for Lagrange multiplier formulation for constrained average cost problem on a general state space, as this is well understood. (In fact, it follows from standard Lagrange multiplier theory applied to the 'occupation measure' formulation of average cost problem which casts it as an abstract linear program. See section 4.2 of [START_REF] Borkar | Convex Analytic Methods in Markov Decision Processes[END_REF] which carries out this program for discrete state space and section 3.2 of ibid. which describes how to extend the same to general compact Polish state spaces as long as the controlled transition probability kernel is continuous in the initial state and control.) For notational simplicity we drop the index i for the time being. We approach the problem by the standard 'vanishing discount' argument. Thus let 0 < δ < 1 be a discount factor and for k(x, v)

:= xv + Cλ(1 -v), consider the infinite horizon discounted reward ∞ m=0 δ t k(X(t)).
Denote the associated value function by

V δ (x) := sup {v(t)},X(0)=x ∞ m=0 δ t k(X(t), v(t)) .
Then V δ satisfies the discounted reward dynamic programming equation

V δ (x) = max (Cλ + δV δ (αx + u), x + δV δ (u)) . (8)
Inria Lemma 1 The solution of equation ( 8) has the following properties:

(1) Equation ( 8) has a unique bounded continuous solution V δ ;

(2) V δ is Lipschitz uniformly in δ ∈ (0, 1);

(3) V δ is monotone increasing and convex.

Proof: Claim (1) is standard (See Theorem 4.2.3 and bullet 1 in 'Notes on §4.2', Section 4.2, [START_REF] Hernández-Lerma | Discrete Time Markov Control Processes: Basic Optimality Criteria[END_REF]). For (2), consider x = x > x ∈ S. Consider processes X(t), t ≥ 0, and X (t), t ≥ 0, with initial conditions x, x resp., both controlled by control sequence v(t), t ≥ 0, that is optimal for the former. Then

V δ (x ) -V δ (x) ≤ ∞ t=0 δ m (k(X (t), v(t)) -k(X(t), v(t))) = (1 -αδ) τ 1 -α (x -x),
where τ := the time of first crawl (= ∞ if never crawled). Interchanging the roles of x , x we get a symmetric inequality, whence it follows that

|V δ (x ) -V δ (x)| ≤ (1 -αδ) τ 1 -α |x -x|.
For the first part of (3), take x > x as above and let X (t), X(t), t ≥ 0, be processes generated by a common admissible control sequence {v(t)} with initial conditions x , x resp. Then it is easy to check that X (t) ≥ X(t) for all t. Therefore

∞ t=0 δ t k(X (t), v(t)) ≥ ∞ t=0 δ t k(X (t), v(t)). (9)
Taking supremum over all admissible controls on both sides, monotonicity of V δ follows. For convexity, define the finite horizon discounted value function

V n (x) = sup {v(t)},X(0)=x n t=0 δ t k(X(t), v(t)).
Then it satisfies the dynamic programming equation

V n (x) = max (Cλ + δV n-1 (αx + u), x + δV n-1 (u))
for n ≥ 1 with V 0 (x) = x. The convexity of V n for each n then follows by a simple induction.

Since V δ (x) = lim n↑∞ V n (x), V δ is also convex. 2 Define Vδ (x) = V δ (x) -V δ (u), x ∈ S.
Then by the above lemma, Vδ is bounded Lipschitz, monotone and convex with Vδ (u) = 0. Also, (1 -δ)V δ (u) is bounded. Using Arzela-Ascoli and Bolzano-Weirstrass theorems, we may pick a subsequence such that ( Vδ , (1 -δ)V δ (u)) converge in C(S) × R to (say) (V, β). From (8), we have

Vδ (x) + (1 -δ)V δ (u) = max Cλ + δ Vδ (αx + u), x .
Passing to the limit along an appropriate subsequence as δ ↑ 1, we have

V (x) + β = max (Cλ + V (αx + u), x) (10)
= max

v∈{0,1} vx + (1 -v)(λ + V (αx + u)) . (11)
Then [START_REF] Goyal | Learning Influence Probabilities in Social Networks[END_REF] is the desired dynamic programming equation for average reward. We study important structural properties of the value function V in the next section.

Properties of the value function

We begin with the following result.

Lemma 2

The following statements hold:

(1) V is monotone increasing and convex with V (u) = 0;

(2) The maximizer on the right hand side of ( 11) is the optimal control choice at state x and β is the optimal reward.

Proof: Since monotonicity and convexity are preserved in pointwise limits, the first claim is immediate. For the second, let v * (x) denote the maximizer on the r.h.s. of [START_REF] Hernández-Lerma | Discrete Time Markov Control Processes: Basic Optimality Criteria[END_REF], any tie being settled arbitrarily. Then under {v(t) = v * (X(t)), t ≥ 0},

V (X(t)) + β = k(X(t), v(t)) + V (X(t + 1)). (12)
Summing ( 12) over t = 1, 2, • • • , T , and dividing by T on both sides, then letting T ↑ ∞, we see that β = the average reward under this control policy. On the other hand, for any other control sequence, the equality in (12) will be replaced by ≥, leading to the conclusion that β ≥ the corresponding average reward by an argument similar to the above. This imples the second claim. 2

Now define

B := {x ∈ S : Cλ + V (αx + u) > x}, B c := {x ∈ S : Cλ + V (αx + u) ≤ x}.
These are respectively the sets of passive and active states under subsidy λ.

Recall the stopping time τ := the time of first crawl. Suppose τ < ∞. (The case τ = ∞ corresponds to 'never crawl ' which we consider separately below.) Under optimal policy, iterating equation [START_REF] Goyal | Learning Influence Probabilities in Social Networks[END_REF] τ times leads to

V (x) = (Cλ -β)τ + α τ x + 1 -α τ 1 -α u -β .

Inria

Under any other policy, we would likewise obtain

V (x) ≥ (Cλ -β)τ + α τ x + 1 -α τ 1 -α u -β .
Thus we have the explicit representation for V given by

V (x) = max (Cλ -β)τ + α τ x + 1 -α τ 1 -α u -β ,
where the maximum is over all admissible control sequences. In particular, this implies:

Lemma 3 Equation ( 10) has a unique solution.

Finally, we have the key lemma:

Lemma 4
The above problem is Whittle indexable.

Proof: Since V is monotone increasing and convex, the map

x → x -V (αx + u)
is concave and hence the set B increases monotonically from φ to S as λ increases from -∞ to ∞. The claim now follows from the definition of Whittle indexability. 2

We shall now eliminate some irrelevant situations.

1. If u * ∈ B, i.e., the optimal action at u * is 0, then u * is a fixed point of the optimally controlled dynamics and the corresponding cost is Cλ. Then β = Cλ and it is optimal to be passive at all states, i.e., B = [u, u * ], B c = φ, and

λ ≥ λ m := max x∈[u,u * ] (x -V (αx + u))/C. ( 13
)
2. If u ∈ B c , then from [START_REF] Goyal | Learning Influence Probabilities in Social Networks[END_REF], 0 + β = u + 0, i.e., β = u and it is optimal to crawl when at u. Then u is a fixed point of the controlled dynamics and it is optimal to be active at all states, i.e., B c = [u, u * ], B = φ, and

λ ≤ λ M := min x∈[u,u * ] (x -V (αx + u))/C. ( 14
)
Note that since constant policies v(t) ≡ 0 and v(t) ≡ 1 lead to costs Cλ and u resp., β ≥ (Cλ)∨u always and β > (Cλ) ∨ u for λ ∈ (λ m , λ M ). For each λ in (λ m , λ M ), both B, B c are non-empty and there exists an a ∈ (u, u * ) for which the choice of being active or passive is equally desirable. Furthermore, this a is an increasing function of λ by Lemma 4. Inverting this function, we have γ(x) := the value of λ at which the active and passive become equally desirable choices, as an increasing function of x ∈ (u, u * ). Proof: Since V is convex, one of the following two must hold:

RR n°8702 1. For some a 2 > a 1 , B = [u, a 1 ) ∩ (a 2 , u * ] and B c = [a 1 , a 2 ], or, 2. for some a, B = [u, a), B c = [a, u * ].
However, since at u * the optimal action is to crawl, we conclude that u * ∈ B c and only the second possibility can occur.

2

Corollary 1 The map x → x -V (αx + u) is monotone non-decreasing on [u, u * ].

Derivation of Whittle index

Consider the situation when λ = γ(x) for a prescribed x ∈ (u, u * ). It is clear that after the first crawl when the process is reset to u, the optimal X(t) becomes periodic: not crawling and increasing till it hits B c and then crawling -thereby being reset to u -to repeat the process. Since finite initial patches do not affect the long run average reward, we may then take X(0

) = u. Define η(x) = min{t : X(t) ∈ B c }. Then X(η(x)) = (1 -α η(x) )u * (15) =⇒ η(x) = log + α 1 - x u * , (16)
where log + α x = log α xI{x > 0}. Since the long run average cost is equal to the average over one period, we can write

β = Cλ(η(x) -1) + X(η(x)) η(x) , (17)
where η(x) is given by ( 16) and X(η(x)) is given by [START_REF] Lefortier | Timely Crawling of Highquality Ephemeral New Content[END_REF].

We now revert to using the index i to identify the source being referred to. In particular, β i , λ i will refer to the optimal reward, resp. Lagrange multiplier, for the ith decoupled problem. Our main result is: Theorem 1 The Whittle index for our problem is given by

γ i (x) := 1 C i η i (x)((1 -α i )x -u i ) + 1 -α ηi(x) i 1 -α i u i ,
where

η i (x) := log + αi u i -(1 -α i )x u i .
Therefore the index policy is to crawl at time t (= mT for some m ≥ 0) the top M sources according to decreasing values of γ i (X i (t)), or alternatively, choose a number of top sources for the constraint to be reached.

Remark: Note that if an arm (say, ith) is crawled even once, the corresponding state process {X i (t)} takes only discrete values thereafter. These depend on α i and u i alone. In fact this is also true for an arm that is never crawled, except that the discrete values taken will also depend Inria on the initial condition. Therefore we need restrict attention to only these values of x for the argument of γ i (•). This results in a further simplification of the index formula, to

γ i (x) = 1 C i (η i ((1 -α i )x -u i ) + x) ,
where η i (x) is as before, but the argument x of both γ i and η i is now restricted to the aforementioned discrete set.

Proof: We drop the subscript i for notational convenience. For x ∈ B c , [START_REF] Goyal | Learning Influence Probabilities in Social Networks[END_REF]

leads to V (x) = x -β. Also, for x := αx + u, x ≤ u * = u 1 -α =⇒ x = αx + u ≥ αx + (1 -α)x =⇒ x ≥ x =⇒ x ∈ B c (by Lemma 5) =⇒ V (x ) = x -β.
Combining this with [START_REF] Goyal | Learning Influence Probabilities in Social Networks[END_REF] and the definition of Whittle index implies that for our problem it is

γ i (x) = (1 -α i )x -u i + βi (x) C i , (18)
where by virtue of (17), βi (x) := the optimal cost if one were to set λ i = γ i (x). The latter is given by: βi (x) := 1

η i (x) C i γ i (x)(η i (x) -1) + 1 -α ηi(x) i u * i .
where

η i (x) := log + αi u i -(1 -α i )x u i .
Substituting this back into [START_REF] Moon | Refining Recency Search Results with User Click Feedback[END_REF], one gets a linear equation for γ i (x) that can be solved to evaluate γ i (x) as

γ i (x) := 1 C i η i (x)((1 -α i )x -u i ) + 1 -α ηi(x) i 1 -α i u i .
This completes the proof. 2

Stochastic case

We now consider the fully stochastic situation when traffic at each source is observed as a random variable. In fact one could also consider mixed situations when some sources are observed and others are not. As we shall see, the development closely mimics the foregoing and the Whittle index is actually the same.

The stochastic system dynamics can be described as follows: Let {τ i n } denote the successive arrival times of content at source i, with utilities {ξ i n }, resp. The net utility added to source i during k-th epoch will be

U i (k) := τ i n : (k-1)T ≤τ i n <kT ξ i n e -µi(kT -τ i n ) .
The system state at time (k + 1)T is then

X i (k + 1) = α i X i (k) + U i (k + 1) if no crawl, = U i (k + 1) if crawled. ( 19
)
We define the average reward as

lim sup t↑∞ N i=1 1 t t m=0 E[r(X i (t), v i (t))],
which we seek to maximize subject to the constraint lim sup

t↑∞ 1 t N i=1 C i E[v i (t)] = M.
The discounted value function

V δ (x) := sup {v(t)},X(0)=x E ∞ t=0 δ t k(X(t), v(t))
then satisfies the dynamic programming equation

V δ (x) = max Cλ + δ V δ (αx + u)ϕ i (du), x + δ V δ (u)ϕ i (du) , (20)
where ϕ i is the law of U i (t) ∀t.

Lemma 5

The conclusions of Lemma 1 continue to hold.

Proof: The first claim follows as before from the cited results of [START_REF] Hernández-Lerma | Discrete Time Markov Control Processes: Basic Optimality Criteria[END_REF]. For the second, let X(t), X (t) be as in the proof of Lemma 1 (2). Then

V δ (x ) -V δ (x) ≤ E ∞ t=0 δ m (k(X (t), v(t)) -k(X(t), v(t))) ≤ E [(αδ) τ ] (x -x).
The Lipschitz property follows as before. Next let X(t), X (t) be as in the proof of Lemma 1 (3). Taking expectations in (9) followed by a supremum over all admissible controls proves monotonicity. Convexity follows as in the deterministic case. 2

The 'vanishing discount' argument of Section 4 can now be used to establish the average cost dynamic programming equation

V (x) + β = max(Cλ + V (αx + u)ϕ(du), x). (21)
Monotonicity and convexity of V follows as in Lemma 2. Equation ( 12) gets modified to

E[V (X(t))] + β = E[k(X(t), v(t))] + E[V (X(t + 1))],
Inria from which the optimality of

v * (x) ∈ Argmax v vx + (1 -v)(λ + V (αx + u)ϕ(du)) , x ∈ S,
follows by arguments analogous to those of Lemma 2. Furthermore, V can be shown to be the unique solution of ( 21) by establishing the explicit representation

V (x) = max E (Cλ -β)τ + α τ x + τ t=0 α τ -t U (t) -β ,
where the maximum is over all admissible control sequences. Thus, Whittle indexability follows as before. Define

Ξ(x) := E   η(x) t=0 α η(x)-t U (t) X(0) = x   .
The definitions of B, B c change to

B := {x ∈ S : Cλ + V (αx + u)ϕ(du) > x}, B c := {x ∈ S : Cλ + V (αx + u)ϕ(du) ≤ x}.
Let η m , m ≥ 1, denote the successive visits to B c , i.e., the crawling times. Then

X(η m+1 ) = ηm+1-1 t=ηm α ηm+1-t U t , m ≥ 1.
As before, we may assume that η 1 (x) = 0. Then the expression (16) for η 2 (x) will continue to hold. We denote it by η(x) as before for notational convenience. Therefore

β(x) = Cλ(η(x) -1) + E[X(η(x))] η(x) = Cλ(η(x) -1) + (1 -α η(x) )u * η(x)
as before. Hence the conclusions of Theorem 1 continue to hold.

Numerical examples

Let us illustrate the obtained theoretical results by numerical examples. There are four information sources with parameters given in Table 1. Without loss of generality, we take the crawling period T = 1. One can see how the user interest decreases over time for each source in Figure 1.

The initial interest in the content of sources 1 and 2 is high, whereas the initial interest in the content of sources 3 and 4 is relatively small. The interest in the content of sources 1 and 3 decreases faster than the interest in the content of sources 2 and 4.

In Figure 2 we show the state evolution of the bandits (information sources) under the constraint that on average the crawler can visit only one site per crawling period T , i.e., M = 1. The application of Whittle index results in periodic crawling of sources 1 and 2, crawling each with period two. Sources 3 and 4 should be never crawled. Note that if one greedily crawls only source 1, he obtains the average reward 179.79. In contrast, the index policy involving two sources results in the average reward 254.66.

In Figure 3 we show the state evolution of the bandits under the constraint that on average the crawler can visit two information sources per crawling period, i.e., M = 2. It is interesting that now the policy becomes much less regular. Source 1 is always crawled. Sources 2 and 3 are crawled in a non-trivial periodic way and sources 4 is crawled periodically with a rather long period. Now in Figure 4 we present the state evolution of the stochastic model with dynamics [START_REF] Nino-Mora | Sensor Scheduling for Hunting Elusive Hiding Targets via Whittle's Restless Bandit Index Policy[END_REF]. As one can see, in the stochastic setting source 1 is crawled from time to time.

Conclusions and future works

We have formulated the problem of crawling web sites with ephemeral content as an average reward optimal control problem and have shown that it is indexable. We have found that the Whittle index has a very simple form, which is important for efficient practical implementations. The numerical example demonstrates that the Whittle index policies, unlike the policies suggested in [START_REF] Lefortier | Timely Crawling of Highquality Ephemeral New Content[END_REF], do not generally have a trivial periodic structure. The proposed approach can also be used in the cases when some states are observed. In such cases, the Whittle index will act as a self-tuning mechanism. We are currently working on the adaptive version when some parameters (e.g., the rate of new information arrival) need to be estimated online. One more interesting future research direction is to add to the model the dynamics of the indexing engine.

Lemma 5

 5 The sets B, B c are of the form [u, a), [a, u * ] for some a ∈ [u, u * ].

Figure 1 :

 1 Figure 1: Content value as a function of time.

Figure 2 :

 2 Figure 2: The case of M = 1.

Inria

Figure 3 :

 3 Figure 3: The case of M = 2.

Figure 4 :

 4 Figure 4: The case of M = 2 (stochastic model).

Table 1 :

 1 Data for numerical example

	i	1	2	3	4
	ξi 1.0	0.7	0.2 0.08
	µ i 0.7 0.35 0.7 0.21
	Λ i 250 250 250 250

RR n°8702

Inria

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgments

The authors gratefully acknowledge the discussions with Liudmila O. Prokhorenkova and Egor Samosvat from Yandex during the preparation of the manuscript.

‡ This work was partially supported by Indo-French CEFIPRA Collaboration Grant No.5100-IT1 "Monte Carlo and Learning Schemes for Network Analytics". Index de Whittle pour Crawling du Contenu Éphémère