Vanessa Vitse
email: vanessa.vitse@ujf-grenoble.fr

Alexandre Wallet
email: alexandre.wallet@lip6.fr

Improved Sieving on Algebraic Curves

Keywords: discrete logarithm, index calculus, algebraic curves, curvebased cryptography

. Recently, Sarkar and Singh have proposed a sieving technique, inspired by an earlier work of Joux and Vitse, to speed up the relation search in the hyperelliptic case. We give a new description of this technique, and show that this new formulation applies naturally to the non-hyperelliptic case with or without large prime variations. In particular, we obtain a speed-up by a factor approximately 3 for the relation search in Diem and Kochinke's methods.

Introduction

Given a commutative group (G, +), and two elements g, h of G, the discrete logarithm problem (DLP) consists in finding, if it exists, an integer x such that x • g = h. It is considered as a major computational challenge and much work has been done on the principal families of groups in the last decades. Jacobians of algebraic curves defined over finite fields are of particular interest, largely because of their link with elliptic curves (which, as genus 1 curves, are their own Jacobians). Indeed, transfer attacks as introduced in [START_REF] Gaudry | Constructive and destructive facets of Weil descent on elliptic curves[END_REF] can reduce certain discrete logarithm instances on elliptic curves to instances on higher genus curves, see for instance the record computations of [START_REF] Joux | Cover and decomposition index calculus on elliptic curves made practical: application to a previously unreachable curve over F q 6[END_REF]. Consequently, even though for applications in cryptography only genus 1 (i.e. elliptic curves) or genus 2 curves are currently considered, assessing the exact difficulty of the DLP in higher genus is still very important from both the practical and the number-theoretical points of view.

A popular approach to the discrete logarithm problem is given by the index calculus family of algorithms, that rely heavily on the structures surrounding the group. The general picture is always the same. We start by choosing a socalled "factor base" B, i.e. a subset of the elements of the group. Then in a first phase we search for relations involving elements of the factor base, yielding linear equations between their discrete logarithms; we call this first phase "harvesting" throughout this paper. In a second phase we basically solve the linear system of equations given by the relation matrix and deduce the wanted discrete logarithm. This linear algebra phase does not depend on the structure of the group, but its complexity clearly depends on the cardinality N of the factor base, since it is roughly the size of the relation matrix.

It is possible to simplify the linear algebra at the expense of the harvesting phase by decreasing the size of the factor base. This must be done with added care since less elements in the factor base means lower probability of obtaining a relation. In the so-called "large prime" variants 4 (see [START_REF] Diem | An index calculus algorithm for plane curves of small degree[END_REF][START_REF] Gaudry | A double large prime variation for small genus hyperelliptic index calculus[END_REF][START_REF] Laine | Time-memory trade-offs for index calculus in genus 3[END_REF][START_REF] Thériault | Index calculus attack for hyperelliptic curves of small genus[END_REF]), we choose or construct a subset B s of the factor base B called the set of "small primes", of size O(N α ) with 0 < α < 1. The set B\B s is the set of large primes. Then we accept only relations involving elements in B s and at most two large primes. This decreases the probability of a relation, but it is shown in [START_REF] Diem | An index calculus algorithm for plane curves of small degree[END_REF][START_REF] Gaudry | A double large prime variation for small genus hyperelliptic index calculus[END_REF] that finding O(N ) relations involving at most two large primes is enough to form O(N α ) relations involving only small primes. The linear algebra phase over B s then runs in O(N 2α ) and it remains to choose α to balance both main phases of index calculus. More details are given at the end of Sect 2.1.

In this work we focus on improving the known harvesting methods, dedicating to Jacobian varieties of algebraic curves defined over finite fields. We emphasize that all the other aspects of the index calculus method (such as the choice of the factor base, the processing of large prime relations and the linear algebra phase) are not modified. Recently, Sarkar and Singh proposed in [START_REF] Sarkar | A new method for decomposition in the Jacobian of small genus hyperelliptic curves[END_REF] to use a sieving technique for harvesting relations in the hyperelliptic case, instead of the standard approach of Gaudry [START_REF] Gaudry | An algorithm for solving the discrete log problem on hyperelliptic curves[END_REF] based on smooth reduced divisors. A very similar sieve had actually been used before by Joux and Vitse in [START_REF] Joux | Cover and decomposition index calculus on elliptic curves made practical: application to a previously unreachable curve over F q 6[END_REF], but in the different context of curves defined over extension fields and Weil restrictions. It turns out that Sarkar and Singh's sieve has a simpler interpretation, which allows to generalize it to the index calculus introduced by Diem [START_REF] Diem | An index calculus algorithm for plane curves of small degree[END_REF] for non-hyperelliptic curves, or more exactly small degree planar curves. In our experiments, the new non-hyperelliptic sieve improves Diem's original method, as well as its development by Diem and Kochinke [START_REF] Diem | Computing discrete logarithms with special linear systems[END_REF], by a factor approximately 3.

The presentation follows these steps. We begin by the case of hyperelliptic curves, recalling the classical approach of Gaudry based on smoothness check. We present and analyze the sieving variant of Sarkar and Singh before introducing its simpler reformulation. The next section deals with algebraic curves of genus g admitting a plane model of degree d ≤ g +1. Again we start by the classical ideas of using principal divisors associated to equations of lines to generate relations [START_REF] Diem | An index calculus algorithm for plane curves of small degree[END_REF]. We then give the adaptation of our sieve to small degree curves, and compare it to Diem's method. We also briefly present the singularity-based technique of Diem and Kochinke and show that our sieve adapts again to this setting. Experiments and timings are reported in the last section.

2 Sieving for Hyperelliptic Curves 2.1 Gaudry's Relation Search Index calculus on hyperelliptic curves relies on the search of smooth Mumford representations of divisors. Let H be a genus g imaginary hyperelliptic curve defined over F q , with equation y 2 = h(x) (so that deg h = 2g + 1) and point at infinity P ∞ . For simplicity we assume that we are in the odd characteristic case, but everything can be easily adapted to the characteristic two case. We recall that any element [D] in the Jacobian variety Jac H (F q ) can be uniquely represented by a couple [u(x), v(x)] of polynomials such that:

u is monic and deg u ≤ g;

-deg v < deg u; -u|(h -v 2 ).
More precisely, this is the Mumford representation of the unique reduced divisor

D = (P 1 ) + • • • + (P deg u ) -deg u (P ∞ ) in the class [D].
The roots of u are exactly the x-coordinates of the points P i ∈ H(F q ), and v satisfies v(x Pi ) = y Pi . The Mumford representation is actually defined for every semi-reduced divisor, i.e. of the form (P 1 ) + • • • + (P w ) -w(P ∞ ) with P i = ıP j if i = j, where ı stands for the hyperelliptic involution (x, y) → (x, -y). The integer w = deg u is called the weight of the divisor, which is reduced if and only if w ≤ g.

With this setting we see that if the polynomial u splits over F q , then for each i the point P i is F q -rational so that the class of (P i ) -(P ∞ ) defines an element of Jac H (F q ). Furthermore, we have

D = i ((P i ) -(P ∞ )) (i.e.
D is 1-smooth) and the same equality holds when taking linear equivalence classes. Gaudry's algorithm [START_REF] Gaudry | An algorithm for solving the discrete log problem on hyperelliptic curves[END_REF] stems from this observation, and its harvesting phase can be summarized as follows.

-The factor base B is the set {(P ) -(P ∞ ) : P ∈ H(F q )}, or rather a set of representatives of its quotient by the hyperelliptic involution, accounting for the trivial relations (ıP )

-(P ∞ ) ∼ -((P ) -(P ∞ )). It contains Θ(q)
elements. -At each step, we compute (using a semi-random walk) the Mumford representation [u, v] of a reduced divisor D ∼ aD 0 + bD 1 , where D 0 and D 1 are the entries of the DLP challenge. -If u splits over F q as i (x -x i ) then a relation is found since we have

aD 0 + bD 1 ∼ i ((P i ) -(P ∞ )) where P i = (x i , v(x i )).
We see that each step of the harvesting phase requires a few operations in Jac H followed by the factorization of u, which is generically a degree g polynomial. The probability that u actually splits over F q is about 1/g!, so we need about g! trials before finding a relation. A precise analysis of the complexity is given by the author in [START_REF] Gaudry | An algorithm for solving the discrete log problem on hyperelliptic curves[END_REF]. However, asymptotically when g is fixed and q grows to +∞, the cost of finding one relation is in Õ(1), so the complexity of the harvesting phase is in Õ(q). By contrast, the linear algebra phase costs Õ(q 2 ) and dominates the complexity. Balancing the two phases has first been proposed by Harley and improved by Thériault [START_REF] Thériault | Index calculus attack for hyperelliptic curves of small genus[END_REF], who introduced the large prime variants in this context. Asymptotically, the best result5 is obtained by Gaudry, Thériault, Thomé and Diem [START_REF] Gaudry | A double large prime variation for small genus hyperelliptic index calculus[END_REF] using the double large prime variation with a factor base B s of size ≈ q 1-1/g , yielding a complexity of Õ(q 2-2/g ) for both the harvesting and the linear algebra phase. Giving a detailed description of the double large variant is outside the scope of this paper, but we mention that there are two distinct approaches regarding the construction of the small prime factor base. A first possibility is to define directly B s as a subset of B whose elements satisfy an easy to check condition, so that membership testing and enumeration are very fast; alternately, the set B S can be constructed progressively from the first relations in order to simplify the future elimination of large primes (as done in by Laine and Lauter [START_REF] Laine | Time-memory trade-offs for index calculus in genus 3[END_REF] in the non-hyperelliptic case).

Sarkar and Singh's Sieve

A recent result of Sarkar and Singh [START_REF] Sarkar | A new method for decomposition in the Jacobian of small genus hyperelliptic curves[END_REF] proposes a sieving approach to the relation search for hyperelliptic curves. In this method, with the same factor base B as in Sect. 2.1, we start from a weight g reduced divisor written as

D = [u, v] = g i=1 (P i ) -g(P ∞
), usually related to the challenge. We then consider all the weight g + 1 semi-reduced divisors D = [u , v ] that are linearly equivalent to -D; a relation is obtained each time u is split (the factor base B is the same as in the previous version). The set of all the decompositions of -D as

-D ∼ g+1 i=1 (Q i ) -(g + 1)(P ∞ ),
i.e. the set of all weight g+1 semi-reduced divisors linearly equivalent to -D, is in one-to-one correspondence with the set of divisors of functions in the Riemann-Roch space L(-D + (g + 1)(P ∞ )) = L(-g i=1 (P i ) + (2g + 1)(P ∞ )). This space is equal to Span(u(x), y -v(x)) (since functions in this space have poles at P ∞ only, of order at most 2g + 1, and vanish at the support of D), and thus the decompositions of -D can be parametrized by an element λ ∈ F q .

We begin with the non-large-prime, non-sieving version of the algorithm. The relation search consists of two main loops, the outer one being simply a semi-random walk iterating through reduced divisors D = [u, v] ∼ aD 0 + bD 1 . The inner loop iterates over the value of the parameter λ ∈ F q . For each λ, we consider the function f λ = y -v(x) + λu(x) and the corresponding semi-reduced divisor

D λ = -D + div(f λ ). The Mumford representation [u λ , v λ ] of D λ is given by the formulae u λ = c (λu-v) 2 -h u = c(λ 2 u -2λv + v 2 -h u ) v λ = v -λu mod u λ ,
where c ∈ F q is the constant that makes u λ monic. We obtain a relation each time D λ is 1-smooth, i.e. when u λ is split over F q ; this happens heuristically with probability 1/(g + 1)!.

The main advantage of this relation search is that it admits a sieving version, in the spirit of [START_REF] Joux | Cover and decomposition index calculus on elliptic curves made practical: application to a previously unreachable curve over F q 6[END_REF]. The idea is to replace the inner loop in λ by an inner loop in x ∈ F q .

For each value of x, we compute the expression

S(x, λ) = λ 2 u(x) -2λv(x) + v(x) 2 -h(x) u(x) ,
which becomes a quadratic polynomial in λ, and find the corresponding roots (for simplicity we can skip the values of x for which u(x) = 0). There are two distinct roots λ 0 and λ 1 if and only if h(x) is a square in F q , and those roots are given by:

λ 0 = v(x) + h(x) 1/2 u(x) , λ 1 = v(x) -h(x) 1/2 u(x) .
As explained by the authors, this step is very fast if a table containing a square root of h(x) (if it exists) for each x ∈ F q has been precomputed. We then store the corresponding couples (λ 0 , x) and (λ 1 , x). At the end of the inner loop, we look for the values of λ that have appeared g + 1 times: this means that the corresponding polynomial u λ has g + 1 distinct roots, so that D λ yields a relation, i.e. a decomposition of -D. In practice, we can either store each value of x in an array L of lists indexed by λ; each time a value of λ is obtained as a root of the quadratic expression, we append

x to L[λ]. When #L[λ] = g + 1,
we directly have the x-coordinates of the points in the support of div(f λ ) -D, and a last step is then to compute back the y-coordinates using f λ . Alternatively, we can simply maintain a counter array Ctr indexed by λ and increment Ctr[λ] each time λ is obtained as a root. When this counter reaches g + 1, we factorize the corresponding split polynomial u λ . This variant has the merit of saving memory at the expense of some duplicate computations, but is more interesting when g increases since the proportion of λ's yielding a relation becomes small. The main speed-up is provided by the fact that at each iteration of the inner loop, we replace the splitting test and the eventual factorization of either the degree g polynomial u (in Gaudry's version) or the degree g + 1 polynomial S(λ, x) evaluated in λ, by the resolution of the degree 2 equation S(λ, x) = 0, evaluated in x. This comes at the expense of a slightly lower decomposition probability, namely 1/(g + 1)! instead of 1/g!, and higher memory requirement.

As already noticed in [START_REF] Joux | Cover and decomposition index calculus on elliptic curves made practical: application to a previously unreachable curve over F q 6[END_REF], a second advantage of this sieve is its compatibility with the double large prime variation. Indeed, once the "small prime" factor base B s is constructed, it is sufficient to sieve among the values of x ∈ F q corresponding to abscissae of its elements (the full sieving as described above can still be used in the construction steps of B s if necessary). Since the cardinality of B s is in Θ(q α ) with α = 1 -1/g, this shortened sieving only costs Õ(q α ) instead of Õ(q). We then look for the values of λ that have been obtained at least g -1 times. The corresponding polynomials u λ have at least g -1 roots corresponding to small primes, and it just remains to test if it is indeed split, which happens with heuristic probability 1/2 (in the case where λ has been obtained exactly g -1 times). Note that we cannot simply scan the array L or Ctr, as it would cost Õ(q) (even with a very small hidden constant) and defeat our purpose. So additional care must be taken in the implementation in order to recover the interesting values of λ in only Õ(q α ), for instance using associative arrays, see [START_REF] Sarkar | A new method for decomposition in the Jacobian of small genus hyperelliptic curves[END_REF] for details. Although it is not specified in the original paper, one can show that the asymptotic complexity of this variant is still in Õ(q 2-2/g ) for fixed g, as in the work of Gaudry, Thomé, Thériault and Diem [START_REF] Gaudry | A double large prime variation for small genus hyperelliptic index calculus[END_REF], but it is more efficient in practice, and the authors report a significant speed-up.

Sarkar and Singh's Sieve Revisited

As mentioned above, precomputing a table containing an eventual square root of h(x) for each x ∈ F q can significantly speed up the sieving phase (for a Õ(q) overhead). But this table is actually nothing more than a list of the rational points of H. Indeed, if y is a square root of h(x) then (x, y) and (x, -y) are exactly the two points in H(F q ) with abscissa x, and this precomputation is actually performed when the factor base B = {(P ) -(P ∞ ) : P ∈ H(F q )} is enumerated.

This means that we can modify Sarkar and Singh's sieve as follows. Recall that we are looking for functions f λ = y -v(x) -λu(x) such that -D + div(f λ ) is 1-smooth. Instead of sieving over the value of x ∈ F q , or in a small subset corresponding to small primes, we directly sieve over P = (x P , y P ) ∈ B or B s , and the corresponding value of λ is simply recovered as y P -v(x P ) u(x P ) . We give a pseudo-code of this sieve in Alg. 1.

This pseudo-code corresponds to the non-large-prime version. Details like the management of the list or associative array L and the update of M are omitted. As mentioned above, a simple counter array Ctr can be used instead of L, requiring the factorization of S(x, λ) for the update of M . If the double large prime variation is used, then the first inner loop iterates only over the elements of the small factor base B s , and in the second we test if #L[λ] ≥ g -1 and subsequently if the remaining factor of S(x, λ) splits.

An easy improvement, not included in the pseudo-code for the sake of clarity, is to use the action of the hyperelliptic involution to divide by two the size of the factor base. We can then compute simultaneously the values of λ corresponding to P = (x P , y P ) and ıP = (x P , -y P ). This saves one evaluation of u and of v at x P , and one inversion of u(x P ), although it is also possible to precompute all inverses. It is clear that this is basically a rewriting of Sarkar and Singh's original sieve, so that the performances of both should be similar. However, we will now see that it is easier to adapt to the non-hyperelliptic case.

F (x,λx+µ) (x-x1)(x-x2
) . The probability of finding a relation is 1/(d -2)!, so that after q steps about q/(d -2)! relations are harvested. By comparison, in our sieving each step requires a single division (or multiplication if the inverses are pretabulated). The inner loop ends after about #B ≈ q steps, and yields q/(d -1)! relations approximately: all the lines through P 1 = (x 1 , y 1 ) have been explored, and contain d -1 other points with probability 1/(d -1)!. Thus we need d -1 times as many steps to obtain the same number of relations, but each step is much simpler, and the experiments of the next section confirm the important speed-up.

This sieve can be adapted straightforwardly to the double large prime variation : we just have to restrict both loops to the small factor base B s (once it is constructed, if the version of [START_REF] Laine | Time-memory trade-offs for index calculus in genus 3[END_REF] is followed), then we recover the values of λ such that #L[λ] ≥ d -3. When #L[λ] = d -3, we still have to check if the remaining two points on the line are rational, which amounts to factorizing a degree 2 polynomial. If d = 4, in Diem's version there are at most two remaining points on any line anyway; our new sieve is thus basically equivalent and does not provide a significant speed-up when using double large primes. However as soon as d ≥ 5 it outperforms Diem's version, but the asymptotic complexity remains in Õ(q 2-2/(d-2) ).

Sieving with Singularities

An article of Diem and Kochinke [START_REF] Diem | Computing discrete logarithms with special linear systems[END_REF] tries to improve on the asymptotic complexity of the above method. The basic idea is to consider singular small degree plane models, and use a singular point as one of the points defining the lines cutting out the curve. Indeed, a singular point appears with a multiplicity greater than one in any line passing through it, so that there are fewer remaining points of intersection with C, and the degree of the polynomial to test for smoothness is less than when two regular points are used. Unfortunately in general there are not enough singular points on a given planar curve to obtain sufficiently many relations. Thus an important part of Diem and Kochinke's work is to find a way to compute new singular plane models of degree d ≤ g + 1 for a given genus g curve, but this is outside of the scope of the present article; furthermore, the computation of the maps between the different models is not asymptotically relevant. Using Brill-Noether theory and considerations on special linear systems, they show that this method works for "general enough" non-hyperelliptic curves, of genus g ≥ 5.

So we assume that we are given a degree d curve C, of equation F (x, y) = 0, with a rational singular point P 1 of multiplicity m ≥ 2 (in most cases m = 2). The factor base is given by the rational points of the desingularization C of C, i.e. B = {(P ) : P ∈ C(F q )}. In the original version, for each other point P 2 in B or in the small factor base B s , the intersection of C with the line passing through P 1 and P 2 is computed as before. This amounts to finding the of the polynomial

F (x, λx + µ) (x -x 1 ) m (x -x 2 )
, which has degree d -m -1. If it splits, which happens with probability about 1/(d -m -1)!, we compute the intersection points P 3 , . . . , P d-m-1 and obtain a relation that we can write as

D ∼ (P 2 ) + (P 3 ) + • • • + (P d-m-1 ),
where D involves the singularity and the points at infinity. In the double large prime variation we keep this relation only if it involves no more than two large primes. To get rid of the divisor D on the left-hand side we would like to subtract one such relation from all the other ones. But in order to do this (using large primes) we need one relation involving only small primes ; if it does not exist a solution is then to add some points to B s . Since there are less points on the righthand side than in Diem's first algorithm, the probability of finding a relation increases, and one can show that the overall complexity becomes Õ(q 2-2/(g-2) ).

Note that here again, some care must be taken to avoid duplicate relations, and in particular not all points P 2 but only a fraction of the factor base should be considered. Now it is clear that our sieve can be naturally adapted to this new setting. Indeed, we can keep the inner loops of Alg. 2 ; the point (x 1 , y 1 ) is now the singular point P 1 , and we look for the values of λ that have been obtained d -m times, or d -m -2 times in the double large prime variation. Once again, this replaces the factorization of a degree d -m -1 polynomial by a single division, and avoids checking for duplicate relations.

Experiments

We have experimented the harvesting techniques presented in this article for several curves of different genera, defined over different finite fields. All computations have been done using the computer algebra system Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF] on an AMD Opteron TM 6176 SE@2.3GHz processor. We only implemented the nonlarge-prime version of the algorithms, the main reason being that we wanted the tests to be as simple as possible6 . The curves have been generated with the command RandomCurveByGenus, which always returned a degree g curve (instead of g + 1) for g ≥ 6; for this reason the results in genus 6 are very close to those in genus 5 and we did not report them. For the non-sieving versions, we used associative arrays and sets to automate the check for duplicate relations, but this is more and more costly as the number of relations grows. We give in Table 1 the comparison between Diem's method and our sieve; the values are the timings in seconds (on an Intel c Core i5@2.00Ghz processor) to obtain p ≈ #F relations, averaged over several curves. In Table 2 we give timings comparing the new sieve with Diem and Kochinke's method. We did not implement the change of plane models; instead, we simply chose random curves possessing rational singular points, and used one of them as the base point for the relation search. In the sieving version all the relations involving lines passing through the singularity were computed, whereas in the non-sieving case we only iterated through half of the basis, as suggested in [START_REF] Diem | Computing discrete logarithms with special linear systems[END_REF]. For this reason the values correspond to the timings in seconds needed to obtain 1000 relations, again averaged over several curves.

Conclusion

We have shown in this work that a reformulation of Sarkar and Singh's sieve [START_REF] Sarkar | A new method for decomposition in the Jacobian of small genus hyperelliptic curves[END_REF], namely sieving over points instead of x-coordinates, gives a simpler presentation of the harvesting phase of the index calculus algorithm on hyperelliptic curves. More importantly, it can be naturally adapted to Diem and Kochinke's index calculus for non-hyperelliptic curves [START_REF] Diem | An index calculus algorithm for plane curves of small degree[END_REF][START_REF] Diem | Computing discrete logarithms with special linear systems[END_REF]. Our experiments show that the new sieve clearly outperforms the relation search of the other methods in all circumstances and should always be preferred.

Table 1 .

 1 Comparisons of the new sieve with Diem's classical method

	p		78137 177167 823547 1594331
		Diem	11.57 27.54 135.1 266.1
	Genus 3, degree 4	Diem + sieving 3.65 9.38 46.96 94.60
		Ratio	3.16 2.95	2.88	2.81
		Diem	51.85 122.4 595.8 1174
	Genus 4, degree 5	Diem + sieving 15.58 40.01 195.1 387.6
		Ratio	3.33 3.06	3.05	3.03
		Diem	229.4 535.8 2581	5062
	Genus 5, degree 6	Diem + sieving 75.66 199.0 969.3 1909
		Ratio	3.03 2.69	2.66	2.65
		Diem	1382 3173 14990 29280
	Genus 7, degree 7	Diem + sieving 458.5 1199 5859 11510
		Ratio	3.02 2.65	2.56	2.54

Table 2 .

 2 Comparisons of the new sieve with Diem and Kochinke's method

	p		78137 177167 823547 1594331
		Diem & Kochinke 1.58 1.60	1.69	1.76
	Genus 5, degree 6	DK + sieving	0.43 0.45	0.52	0.61
		Ratio	3.67 3.60	3.23	2.90
		Diem & Kochinke 8.59 8.68	8.97	9.20
	Genus 7, degree 7	DK + sieving	1.21 1.25	1.56	1.93
		Ratio	7.13 6.96	5.74	4.77

The terminology of index calculus stems from the context of integer factorization. In our setting, "large primes" are arbitrary elements, and involve no notion of size.

This is only true asymptotically. For actual instances of the DLP many other factors have to be taken into account, and large prime variations are not always appropriate.

More fundamentally, large prime variations are interesting for the asymptotic complexity analysis, but are not always well-suited in practice ; other methods such as the Gaussian structured elimination[START_REF] Lamacchia | Computation of discrete logarithms in prime fields[END_REF] can be more efficient.

Acknowlegdements. We would like to thank the anonymous referees for their useful comments during the elaboration of the article.

3 Sieving for Small Degree Curves

Diem's Relation Search

Gaudry's algorithm can be adapted to non-hyperelliptic curves. Most divisors can still be represented by Mumford coordinates, but computations in the Jacobian variety are not as tractable and checking for 1-smoothness is less obvious. However, all these operations are in Õ(1) when g is fixed, so that the asymptotic complexity is still in Õ(q 2-2/g ), albeit with a larger hidden constant than in the hyperelliptic case.

In [START_REF] Diem | An index calculus algorithm for plane curves of small degree[END_REF], Diem devised a different harvesting technique for plane curves whose degree is really close to the genus. More precisely, if a curve of genus g ≥ 3 is general enough (which rules out hyperelliptic curves), we can find in polynomial time a plane model of expected degree d ≤ g + 1 using a probabilistic algorithm. This means that Diem's algorithm applies to almost all non-hyperelliptic curves, with the (then unexpected) consequence that the DLP is easier on non-hyperelliptic curves than on hyperelliptic ones.

Harvesting is done by considering relations coming from principal divisors corresponding to equations of lines. For any couple of rational points P 1 and P 2 on the curve C, we consider the affine function f = ax + by + c ∈ F q (C) such that the equation of the line L passing through P 1 and P 2 is f = 0. The intersection of L and the affine part of C contains up to d rational points, of which we already know two; determining the remaining d -2 amounts to finding the roots of a degree d -2 polynomial. If there are exactly d -2 other rational intersection points P 3 , . . . , P d then we obtain a relation of the form

where D ∞ is the divisor corresponding to the intersection of C with the line at infinity. This happens with probability 1/(d -2)!, which is better than the 1/g! probability for hyperelliptic curves as soon as d ≤ g + 1.

We can summarize Diem's harvesting technique as follows. The curve C is defined by the equation F (x, y) = 0, and we denote by C 0 its affine, non-singular part. We no longer consider only (classes of) degree 0 divisors, so technically we are working in the full divisor class group and not only its degree 0 part, but in practice it makes no difference.

-The factor base is B = {(P ) :

-We choose two points P 1 = (x 1 , y 1 ) and P 2 = (x 2 , y 2 ) in B such that x 1 = x 2 (for simplicity) and compute λ = (y 2 -y 1 )/(x 2 -x 1 ) and µ = y 1 -λx 1 . -We test if the degree d -2 polynomial F (x,λx+µ) (x-x1)(x-x2) splits over F q . If it is the case, we compute its roots x 3 , . . . , x d and the associated y-coordinates y 3 = λx 3 + µ, . . . , and we store the relation

where P i = (x i , y i ), provided these points are non-singular.

-We go back to the second step until enough relations are found.

Note that a descent phase is needed to express the entries of the DLP challenge in terms of elements of the factor base, see [START_REF] Diem | An index calculus algorithm for plane curves of small degree[END_REF].

The whole routine is particularly well-suited to a two large prime variation (see also [START_REF] Laine | Time-memory trade-offs for index calculus in genus 3[END_REF] for another version differing mainly on the construction of the factor base and the large prime graph). Instead of selecting two points in B, we pick them in the small factor base B s and keep only relations involving at most two large primes. The main advantage (as compared to the hyperelliptic case) is that we ensure in this way that each potential relation contains already two small primes; this greatly increases the probability of finding relations with only two large primes. In particular if d = 4, every relation found by the above method automatically satisfies the two large prime condition.

A precise complexity analysis is given in [START_REF] Diem | An index calculus algorithm for plane curves of small degree[END_REF] and, if C admits a plane model of degree g + 1, gives an asymptotic running time of Õ(q 2-2/(d-2) ), for a small factor base B s of size Θ(q 1-1/(d-2) ). If d = g + 1 this is Õ(q 2-2/(g-1) ), which improves over the Õ(q 2-2/g ) complexity of the hyperelliptic case. Note however that the size of the small factor base is such that in order to find enough relations, almost all lines going through pairs of points of B s have to be considered. This is troublesome because each line, and thus each relation, can be obtained several times, namely n(n -1)/2 times if it contains n small factor base points. This is not really an issue if d = 4, but for higher d some extra care has to be taken in order to prevent duplicate relations.

The Sieving Technique

We can easily adapt our sieving formulation to Diem's setting. The factor base remains the same set of points. Basically, in a first loop we iterate over points P 1 = (x 1 , y 1 ) ∈ C 0 (F q ). The equation of a non-vertical line passing through P 1 is given by (y -y 1 ) -λ(x -x 1 ) = 0. The task is now to find the values of λ such that the line has d rational points of intersection with C without checking for smoothness. For this we then loop in P 2 = (x 2 , y 2 ) ∈ C 0 (F q ) and compute the corresponding λ = (y 2 -y 1 )/(x 2 -x 1 ). But instead of looking for the intersection of the line with C, we just append P 2 to the list L[λ], where L is an array of lists; alternatively, we can simply increment a counter Ctr[λ]. If this counter reaches d -1, or if L[λ] contains d -1 elements, we know that the line contains enough points and yields a relation. This is made precise in the pseudo-code of Alg. 2.

Algorithm 2 Sieving for small degree curves

Input: the list of rational non-singular affine points B = C0(Fq). Output: the relation matrix M .

n rel = 0.

Initialize an array of lists L. Note that in the inner loop we do not iterate over the elements of B that have already been considered in the outer loop. Indeed, after an iteration of the outer loop all the lines passing through the given point P 1 = B[i] have been surveyed, so there is no reason to scan this point again. In this way no line can be considered twice, and we avoid completely having to check for duplicate relations.


Vangelis Th Paschos
email: paschos@lamsade.dauphine.fr

Giorgio Ausiello
email: ausiello@dis.uniroma1.it

Aristotelis Giannakos
email: giannako@lamsade.dauphine.fr

Greedy algorithms for on-line set-covering

Greedy algorithms for on-line set-covering

Introduction

Let C be a ground set of n elements and S a family of m subsets of C such that ∪ S∈S S = C. The set covering problem consists of finding a family S ⊆ S, of minimum cardinality, such that ∪ S∈S S = C. In what follows, for an element c i ∈ C, we set F i = {S j ∈ S : c i ∈ S j } and f i = |F i |; also, we set f = max{f i : i = 1, . . . , n}.

The set covering problem has been extensively studied over the past decades. It has been shown to be NP-hard in Karp's seminal paper ( [START_REF] Karp | Reducibility among combinatorial problems[END_REF]) and O(log n)-approximable for both weighted and unweighted cases (see [START_REF]A greedy-heuristic for the set covering problem[END_REF], for the former and [START_REF] Johnson | Approximation algorithms for combinatorial problems[END_REF][START_REF] Lovász | On the ratio of optimal integral and fractional covers[END_REF][START_REF] Slavík | A tight analysis of the greedy algorithm for set cover[END_REF], for the latter; see also [START_REF] Th | A survey about how optimal solutions to some covering and packing problems can be approximated[END_REF] for a comprehensive survey on the subject). This approximation ratio is the best achievable, unless NP ⊆ DTIME(n O(log log n) ), i.e., unless problems in NP could be proved solvable by slightly super-polynomial algorithms ( [START_REF] Feige | A threshold of ln n for approximating set cover[END_REF]).

In on-line computation, one can assume that the instance is not known in advance but it is revealed step-by-step. Upon arrival of new data, one has to decide irrevocably which of these data are to be taken in the solution under construction. The fact that the instance is not known in advance, gives rise to several on-line models specified by the ways in which the final instance is revealed, or by the amount of information that is achieved by the on-line algorithm at each step. In any of these models, one has to devise algorithms, called on-line algorithms, constructing feasible solutions whose values are as close as possible to optimal off-line values, i.e., to values of optimal solutions assuming that the final instance is completely known in advance. The closeness of an on-line solution to an optimal off-line one is measured by the so-called competitive ratio m(x, y)/ opt(x), where x is an instance of the problem dealt, y the solution computed by the on-line algorithm dealt, m(x, y) its value and opt(x) the value of an optimal off-line solution. This measure for on-line computation has been introduced in [START_REF] Sleator | Amortized efficiency of list update and paging rules[END_REF].

Informally, the basic on-line set-covering model adopted here is the following: elements of a ground set of size n arrive one-by-one and with any such element c i , arrives also the name of some set S i 0 containing c i and covering the most of the ground setelements that have not been yet covered. Clearly, any uncovered element is yet unrevealed. For this model we analyze a simple greedy algorithm consisting of taking S i 0 into the cover, only if c i is not already covered. We prove that the competitive ratio of this algorithm is

√ n and that it is asymptotically optimal for the model dealt, since no on-line algorithm can do better than n/2. This model generalizes the one proposed in [START_REF] Alon | The online set cover problem[END_REF] and, furthermore, it uses a very simple, fast and intuitive algorithm that could be seen as the on-line counterpart of the natural greedy (off-line) set-covering algorithm.

Preliminaries

In [START_REF] Alon | The online set cover problem[END_REF], the following on-line set covering model has been studied. We suppose that we are given an instance (S, C) that it is known in advance, but it is possible that only a part of it, i.e., a sub-instance (S p , C p ) of (S, C) will finally arrive; this sub-instance is not known in advance. A picturesque way to apprehend the model is to think of the elements of C as lights initially switched off. Elements switch on (get activated) oneby-one. Any time an element c gets activated, the algorithm has to decide which among the sets of S containing c has to be included in the solution under construction (since we assume that (S, C) is known in advance, all these sets are also known). In other words, the algorithm has to keep an online cover for the activated elements. The algorithm proposed for this model achieves competitive ratio O(log n log m) (even if less than n elements of C will be finally switched on and less than m subsets of S include these elements).

The on-line model dealt here and studied in Section 3, is inspired, yet quite different, from the one in [START_REF] Alon | The online set cover problem[END_REF]. Given C, S (not known in advance as [START_REF] Alon | The online set cover problem[END_REF] assumes) and an arrival sequence Σ = (σ 1 , . . . , σ n ) of the elements of C (i.e., elements of C are switched on following the order σ 1 , . . . , σ n ), the objective is to find, for any i ∈ {1, . . . , n}, a family S i ⊆ S such that {σ 1 , . . . , σ i } ⊆ ∪ S∈S i S. For any σ i , i = 1, . . ., we denote by S j i , j = 1, . . . , f i , the sets of S containing σ i , by Sj i the subset of the elements of S j i still remaining uncovered and by δ j i the cardinality of Sj i . By f i , we denote the frequency of σ i , i.e., the number of sets in S containing σ i . When σ i switches on, the only information revealed is the name of some set S j 0 i ∈ argmax{δ j i , j = 1, . . . , f i }. So, no a priori knowledge of the topology of the instance (S, C) is assumed by the model. In particular, we do not have to know which are the yet uncovered elements of S j 0 i but only the fact that their number is maximum with respect to any other S j i . The algorithm that we study for this model, called LGREEDY in the sequel, informally works as follows: once an element σ i ∈ C switches on, if σ i is not already covered, then set S j 0 i ∈ argmax{δ j i , j = 1, . . . , f i } is added in the cover under construction. Clearly, by the way LGREEDY works, the content of Sj 0 i is still unrevealed. This algorithm follows the same principle as the natural greedy algorithm for (off-line) minimum set covering, called FGREEDY in the sequel, modulo the fact that this principle applies not to the whole instance (S, C) that is to be finally revealed, but to the part of (S, C) induced by the elements of C that, at a given moment, are switched off (even if the topology of this part is not known). We prove that the competitive ratio of this algorithm is √ n and also that there exist arbitrarily large instances for which this ratio is at least n/2.

In Section 4, we provide a lower bound, equal to n/2 for the competitiveness of a whole class of on-line algorithms running on our model. These algorithms are the ones that construct a cover by taking, at any activation step, at least one set containing some not yet covered recently activated ground element. Based upon this result, one can conclude that LGRREDY is asymptotically optimal for this class and for the model adopted.

There exist several reasons motivating, to our opinion, the study of the model dealt in this paper. The first one is that the algorithm used is as it has already been mentioned, a kind of on-line alternative of the famous greedy algorithm for set-covering. Hence, analysis of its competitiveness is interesting by itself. The second reason is that a basic and very interesting feature of the model dealt is its very small memory requirement, since the only information needed is the binary encoding of the name of S j 0 i . This is a major difference between our approach and the one of [START_REF] Alon | The online set cover problem[END_REF]. There, anytime an element gets activated, the algorithm needs to compute the value of a potential function using an updated weight parameter for each element and then chooses covering sets in a suitable way so that this potential be non-increasing; the greedy online algorithm in our model needs only a constant number of memory places, making it more appropriate for handling very large instances with very few hardware ressources. For instance, the algorithm dealt uses O(log m) space.

In Section 5.1, we show that the set-covering model just presented can be used to solve also minimum dominating set, within competitive ratio √ n where n is the order of the input graph. Minimum dominating set is defined as follows: given a graph G(V, E), we wish to determine the least subset V ⊆ V that dominates the rest of the vertices, i.e., a subset

V ⊆ V such that for all u ∈ V \ V there exists v ∈ V for which (u, v) ∈ E.
In Section 5.2, a slightly simplified, but somewhat more memory consuming on-line model for minimum set covering is adopted. Any time an element σ i of the arrival sequence Σ switches on, the whole sequence (S 1 i , . . . , S f i i ), where S j i , j = 1, . . . , f i are as above, is revealed. For this model, we propose an algorithm achieving competitive ratio f = max σ i ∈Σ {f i }. In many real-life problems, it is meaningful to relax the main specification of the online setting, that is, to keep a solution for any partially revealed instance, in order to achieve a better solution quality. In this sense, a possible relaxation is to consider that several algorithms collaborate in order to return the final solution. The costs of using these algorithms can be different the ones from the others, depending upon the sizes of the solutions computed, the time overheads they take in order to produce them, etc. Moreover, we can assume that an initial common budget is allotted to all these algorithms and that this budget is large enough to allow use of at least one of the algorithms at hand to solve the problem without exceeding it. A nice objective could be in this case, to use these algorithms in such a way that a maximum of the initial budget is saved. For the case of set-covering, the following budget-model, giving rise to what we call maximum budget saving problem is considered in Section 6. We assume that two algorithms collaborate to solve it: the LGREEDY and the FGREEDY. The application-cost of the former is just the cardinality of the solution it finally computes, while, for the latter, its application cost is the cardinality of its solutions augmented by an overhead due, for example, to the fact that it is allowed to wait before making its decisions. For an instance x of setcovering, the initial budget considered is B(x) = √ n opt(x) (this is in order that at least

LGREEDY is able to compute a solution of x without exceeding the budget for any x). Denote by c(x, y) the cost of using A in order to compute a cover y for x. The objective is to maximize the quantity B(x) -c(x, y) and, obviously, the maximum possible economy on x is B(x) -opt(x). We show in Section 6 that there exists a natural algorithm-cost model such that FGREEDY is asymptotically optimal for maximum budget saving.

Before closing this section, let us quote another very interesting approach that could be considered to be at midway between semi-on-line approaches and solutions-stability ones, developed in [START_REF] Gambosi | Preserving approximation in the minweighted set cover problem[END_REF]. There, the problem tackled is the maintenance of approximation ratio achieved by an algorithm while the set covering instance undergoes limited changes. More precisely, assume a set covering instance (S, C) and a solution S for it. How many insertions of some of the ground elements in subsets that did not previously contain these elements produce an instance for which the solution S of the initial instance guarantees the same approximation ratio in both of them? It is shown in [START_REF] Gambosi | Preserving approximation in the minweighted set cover problem[END_REF] that if solution S has been produced by application of the natural greedy algorithm achieving approximation ratio O(log n) ( [START_REF]A greedy-heuristic for the set covering problem[END_REF]), then after O(log n) such insertions initial solution S still guarantees the same approximation ratio.

A greedy on-line algorithm

As already mentioned, the model studied in this section assumes an arrival sequence Σ = (σ 1 , . . . , σ n ) of the elements of C, and the objective is to find, for any i ∈ {1, . . . , n}, a family S i ⊆ S such that {σ 1 , . . . , σ i } ⊆ ∪ S∈S i S. Once an element σ i , i = 1, . . . , switches on, the encoding for S j 0 i ∈ argmax{δ j i , j = 1, . . . , f i } is also revealed. For this model, we propose the following algorithm, LGREEDY, where, although it is not necessary, we suppose for reasons of simplicity of algorithm's specification that n is known to it: Proof. Fix an arrival sequence Σ = (σ 1 , . . . , σ n ) and denote by c 1 , . . . , c k , its critical elements, i.e., the elements having entailed introduction of a set in S . In other words, critical elements of Σ are all elements c i such that c i was not yet covered by the cover under construction upon its arrival. Assume also that the final cover S consists of k sets, namely, S 1 , . . . , S k , where S 1 has been introduced in S due to c 1 , S 2 due to c 2 , and so on.

• set S 0 = ∅; • for i = 1 to n do (σ i switches on): if σ i is not already covered by S i-1 , -then set S i = S i-1 ∪ {argmax{δ j i : j = 1, . . . , f i }}; -else set S i = S i-1 ; • output S = S n .
Let δ(S i ) be the increase of the number of covered elements just after having taken S i in the greedy cover (recall that if S i has been added in S for critical element c i = σ j , δ(S i ) = max{δ 1 j , . . . , δ

f j j }).
We have:

δ (S 1 ) = |S 1 | (1)
and, for 2 i k,

δ (S i ) = i =1 S - i-1 =1 S ( 2
)
Fix now an optimal off-line solution

r i=1 h (S * i ) = k (3) r k * (4)
For any S * i , let c 1 i , . . . , c h(S * i ) i be the elements of its critical content ordered according to their position in the arrival sequence Σ; in other words, following our assumptions,

Ŝ * i = {c 1 i , . . . , c h(S * i ) i } (recall that Ŝ * i ⊆ S * i ).
Suppose, without loss of generality, that, for = 1, . . . , h(S * i ), the set S j ∈ S has been introduced in S when the critical element c i has been activated. At the moment of the arrival of c 1 i , the set S * i is also a candidate set for S . The fact that S j 1 has been chosen instead of S * i means that δ(S j 1 ) δ(S * i ); hence, since as noticed just above, Ŝ * i ⊆ S * i , the following holds immediately:

δ(S j 1 ) δ(S * i ) | Ŝ * i | = h(S * i ).
When c 2 i gets activated, the set S * i has lost some of its elements that have been covered by some sets already chosen by the algorithm. In any case, it has lost c 1 i (covered by S j 1 ). So, following the arguments developed just above for S j 1 , δ(S j 2 ) h(S * i ) -1, and so on (quantities δ(•) are defined either by [START_REF] Alon | The online set cover problem[END_REF], or by ( 2)). So, dealing with c i , the following holds:

h (S * i ) -+ 1 δ (S j ) (5)
For example, consider the illustration of Figure 1. Let S * be a set of the fixed optimal cover S * and denote by Ŝ the set of its critical elements, c 1 , c 2 and c 3 (ranged in the order they have been activated). Let S be the set chosen by LGREEDY to cover c 2 . The shadowed parts of S * , Ŝ and S correspond to elements already covered by LGREEDY at the moment of arrival of c 2 . At this moment, S must contain at least as many uncovered elements as S * does and a fortiori at least one uncovered element for any yet uncovered critical element of S * (two uncovered elements for S appear below the dashed line for c 3 and c 4 ). Summing up inequalities (5), for = 1, . . . , h(S * i ), and setting

S Ŝ S * c 1 c 2 c 3 c 4
h(S * i )
=1 δ(S j ) = n i , we finally get for S i :

h (S * i ) (h (S * i ) + 1) 2 h(S * i ) =1 δ (S j ) = n i =⇒ h (S * i ) √ 2n i (6) Set, for 1 i r, n i = α i n, for some α i ∈ [0, 1]. Then, r i=1 α i = 1 and r i=1 √ α i √ r (7)
Using ( 3), ( 4), ( 6) and ( 7), we get:

k = r i=1 h (S * i ) √ 2n r i=1 √ α i √ r √ 2n √ k * √ 2n (8)
Dividing the first and the last members of ( 8) by k * , we get:

k k * 2n k * (9)
On the other hand, remark that, if k * = 1, i.e., if there exists S * ∈ S such that S * = {S * }, then LGREEDY would have chosen it from the beginning of its running in order to cover σ 1 ; next, no additional set would have entered the S . Consequently, we can assume that k * 2 and, using [START_REF] Th | A survey about how optimal solutions to some covering and packing problems can be approximated[END_REF],

k k * √ n ( 10
)
Combination of ( 9) and ( 10) concludes the competitive ratio claimed.

Fix an integer N and consider the following instance (S, C) of minimum set covering:

C = 1, . . . , N (N + 1) 2 S 1 = {1, . . . , N} S 2 = {N + 1, . . . , 2N -1} . . . S N = N (N + 1) 2
S N +1 = (i -1)N - i(i -3) 2 : i = 1, . . . , N S N +2 = C \ S N +1
Consider the arrival sequence (1, . . . , N(N + 1)/2).

LGREEDY might compute the cover S = {S i , 1 i N }, while the optimal one is S * = {S N +1 , S N +2 }. Hence, the competitive ratio in this case would be N/2, with N = (-1 + √ 1 + 8n)/2 which is asymptotically equal to n/2 as claimed.

For example, consider Figure 2. For Σ starting with 1, 6, 10, 13, 15, LGREEDY may have chosen sets {1, 2, 3, 4, 5}, {6, 7, 8, 9}, {10, 11, 12}, {13, 14}, {15}, respectively, while the optimal cover would consist of the two sets {1, 6, 10, 13, 15} and {2, 3, 4, 5, 7, 8, 9, 11, 12, 14}. The proof of the theorem is now complete.

Revisit [START_REF] Th | A survey about how optimal solutions to some covering and packing problems can be approximated[END_REF], set ∆ = max S i ∈S {|S i |} and take into account the obvious inequality: k * n/∆. Then, the following result is immediately derived from Theorem 1. The set-covering model dealt here is very economic and thus suitable to solve very large instances. Indeed, its memory requirements are extremely reduced since the only information LGREEDY needs at any step i is the encoding of the name of a set S j 0 i ∈ argmax{δ j i , j = 1, . . . , f i }. This is not the case for the intensive computations implied by the model of [START_REF] Alon | The online set cover problem[END_REF].

The counter-example instance given in the proof of Theorem 1 can be slightly modified to fit the case where, at each step, whenever a yet uncovered element arrives, the algorithm is allowed to take in the cover a constant number of sets containing it and such that the number of elements yet switched off that belong to these sets is maximized. For some ρ > 1 and for some integer N , consider the following instance:

S = X, Y, S j i : 1 i N, 1 j ρ C = N i=1 ρ j=1 S j i |C| = ρ N (N -1) 2 + N = n X = {x 1 , . . . , x N } S j i = N -i + 1 for i = 1, . . . , N S j i S k l = ∅, if i = l S j i S k i = {x i } , if j = k Y = C \ X
Consider the arrival sequence where x 1 , . . . , x N are firstly revealed.

LGREEDY might take in the cover all the S j i 's, while the optimal cover is {X, Y }. In this case, the competitive ratio is ρN /2, with

N = ρ -2 2ρ + ρ -2 2ρ 2 + 2 n ρ
i.e., the value of the ratio is asymptotically ρn/2. 0000000000000000000000000 0000000000000000000000000 0000000000000000000000000 0000000000000000000000000 0000000000000000000000000 0000000000000000000000000 0000000000000000000000000 0000000000000000000000000 0000000000000000000000000 0000000000000000000000000 0000000000000000000000000 1111111111111111111111111 1111111111111111111111111 1111111111111111111111111 1111111111111111111111111 1111111111111111111111111 1111111111111111111111111 1111111111111111111111111 1111111111111111111111111 1111111111111111111111111 1111111111111111111111111 1111111111111111111111111

x 1 x 2 x 3
x 4

x 5

Figure 3: A counter-example for the case where the algorithm is allowed to take a constant number of sets containing a recently arrived element.

For example, set ρ = 2 and N = 5 and consider the instance of Figure 3. For Σ starting with x 1 , x 2 , x 3 , x 4 , x 5 , the algorithm may insert to the cover the sets depicted as "rows", while the optimal cover would consist of the "column"-set {x 1 , x 2 , x 3 , x 4 , x 5 } together with the "big" set containing the rest of the elements (drawn striped in Figure 3).

In the weighted version of set-covering, any set S of S is assigned with a non-negative weight w(S), and a cover S of the least possible total weight W = S∈S w(S) has to be computed. A natural modification of LGREEDY in order to deal with weighted set-covering is to put in the cover, whenever a still uncovered element arrives, a set S i containing it that minimizes the quantity w(S i )/δ(S i ). Unfortunately, this modification cannot perform satisfactorily. Consider, for example, an instance of weighted set-covering consisting of a ground set C = {x 1 , . . . , x n }, and three sets, S = C with w(S) = n, X = {x 1 } with w(X) = 1 and Y = C \ {x 1 } with w(Y ) = 0. If x 1 arrives first, the algorithm could have chosen S to cover it, yielding a cover for the overall instance of total weight n, while the optimal cover would be {X, Y } of total weight 1.

A lower bound for a whole class of on-line algorithms

We now prove that, in the general model, no on-line algorithm can achieve, for the model dealt, competitive ratio better than n/2, even if it is allowed to choose at any step more than one set to be introduced in the solution.

Proposition 1.

Let A be an on-line algorithm for set-covering such that, at any step, it takes in the cover at least one set containing some not yet covered arriving element. Let k A be the size of the cover computed by A and k * be the size of the optimal cover. Then, k A /k * n/2.

Proof. Consider the following set-covering instance built, for any integer N , upon a ground set S = {x ij : 1 j i N }; obviously, |C| = n = N (N + 1)/2. A pathset of order i is defined as a set containing N -i + 1 elements {x ij i , . . . , x Nj N }. The set-system S of the instance contains all possible path-sets of each order i, 1 i N . Clearly, there exist N !/0! path-sets of order 1, N !/1! path-sets of order 2, and so on and, finally, N !/(N -1)! path-sets of order N , i.e., in all N !(1 + . . . + 1/(N -1)!) ≈ eN ! path-sets. Finally, the set-system S is completed with an additional set Y containing all elements of C but those of some path-set of order 1, that will be specified later (hence,

|Y | = n -N ).
As long as there exist uncovered elements, the adversary may choose to have an uncovered element x ij of the lowest possible i arriving, which will be contained only in all path-sets of order less than or equal to i. Notice that as long as algorithm A has r < N sets inserted in the cover, there will be at least one element x r+1 j for some j, 1 j k + 1, not yet covered. Suppose that after the arrival of σ t , the size of the cover computed by A gets equal to, or greater than, N . Clearly, 1 t N . At time t + 1, a new element arrives, contained in some path-sets and in Y , which can be now specified as consisting of all elements in C except of the elements of some path-set S * of order 1 containing σ 1 , . . . , σ t ; the rest of the arrival sequence is indifferent.

Clearly the optimum cover in this case would have been path-set S * together with set Y ; hence, k A /k * N/2, with N tending to √ 2n as n increases.

For example consider the instance of Figure 4, with N = 5 (the elements of C are depicted as cycles labelled by (i, j) for 1 j i 3). The S i sets can be thought of as paths terminating to a sink on the directed graph of Figure 4(a). Assume that (1, 1) arrives, and algorithm A chooses sets {(1, 1), (2, 1), (3, 1)}, {(1, 1), (2, 2), (3, 2)} for covering it; the uncovered element (3, 3) arrives next, so A has to cover it by, say, the set {(2, 1), (3, 3)} (Figure 4(b)). The optimal cover might consist of set {(1, 1), (2, 2), (3, 3)} together with a big set consisting of the rest of the elements, that could not have been revealed to A upon arrival of (1, 1), or of (3, 3) (Figure 4(c)).

(1,1) It is easy to see that the above construction can be directly generalized so that the same result holds also in the case that the on-line algorithm is allowed to take more than one sets at a time in the cover: if σ 1 = x 11 , then as long as the size of the online cover is less than N , there exists always some i -1 < i N and some j i for which x i j i is yet uncovered. Hence, if σ is this element, then the algorithm will have to put some sets in the cover. Finally, the algorithm will have put N sets in the cover, while the optimum will always be of size 2.

(2,1) (3,1) (2,2) (3,2) (3,3) (a) (1,1) (2,1) (3,1) (2,2) (3,2) (3,3) (b) (1,1) (2,1) (3,1) (2,2) (3,2) (3,3) (c)

Other on-line models

Let us first note that the greedy algorithm cannot do better if a rule concerning the already covered elements is added; the arrival sequence can be set in such a way that always arrive elements not yet covered, until the greedy online cover reaches all elements.

On-line minimum dominating set

Let us consider a different but related problem, the on-line version of the minimum dominating set problem. Consistently with the model that we have adopted for the setcovering problem, our model for this latter problem is as follows. Given a graph G(V, E) with |V | = n, assume that its vertices switch on one-by-one. Any time a vertex σ i does so, the measure of the optimum budget saving solution, this problem is clearly NP-hard since it implies computation of an optimum solution for minimum set-covering. Finally, denoting by c A (S, C) the cost of algorithm A when solving minimum set-covering on (S, C), the approximation ratio of maximum set saving is equal to:

B(S, C) -c A (S, C) B(S, C) -k * (13)
Obviously this ratio is smaller than 1 and, furthermore, the closer the ratio to 1, the better the algorithm achieving it.

Theorem 2. Under the model adopted, FGREEDY is asymptotically optimum for maximum budget saving.

Proof. Consider an instance (S, C) of minimum set-covering and denote by k F and k L , the sizes of the solutions computed by algorithms FGREEDY and LGREEDY, respectively. By what has been assumed just above, denoting by c F the cost of using FGREEDY, there exist some > 0 such that:

c F (S, C)) = k F + k 1- L (14)
Moreover, the following inequalities hold, the first one from [START_REF] Slavík | A tight analysis of the greedy algorithm for set cover[END_REF] and the second one from Theorem 1:

k F k * log n (15) k L k * √ n (16)
Using ( 14), ( 15) and ( 16), we get the following inequality for c F (S, C)):

c F (S, C)) k * 1-n 1- 2 + k * log n n 1- 2 + log n k * (17)
On the other hand, as assumed above:

B(S, C) = k * √ n (18)
Using ( 13), ( 17) and (18), we obtain:

B(S, C) -c F (S, C) B(S, C) -k * k * √ n -n 1- 2 + log n k * k * √ n -k * = √ n -n 1- 2 + log n √ n -1 (19)
It is easy to see that, for n large enough, the last term of (19) tends to 1, and the statement claimed by the theorem is true.

Remark also that if we are allotted with a budget equal to k * log n log m (i.e., the cost of the on-line algorithm of [START_REF] Alon | The online set cover problem[END_REF]) and we assume that the fine paid by algorithm FGREEDY

Theorem 1 .

 1 Consider an instance (S, C) of minimum set covering with |C| = n. Consider also the on-line model introduced above, and denote by S * = {S * 1 , . . . , S * k * } an optimal off-line solution on (S, C). Then, the competitive ratio of LGREEDY is bounded above by min{ 2n/k * , √ n}. Furthermore, there exist large enough instances for which this ratio is at least n/2.

Figure 1 :

 1 Figure 1: An example for (5).

Figure 2 :Corollary 1 .

 21 Figure 2: The ratio n/2 for LGREEDY is asymptotically attained. Corollary 1. The competitive ratio of LGREEDY is bounded above by √ 2∆.

Figure 4 :

 4 Figure 4: The counter-example of Proposition 1 for N = 5.

the name of its neighbor with the most neighbors still switched off is announced. Denote by v i 0 such neighbor of σ i . If σ i is not yet dominated by the partial dominating set V already constructed, then v i 0 enters V .

Consider the following classical reduction from minimum dominating set to set covering:

• the set S i ∈ S, corresponding to the vertex v i ∈ V , contains elements c i 1 , c i 2 , . . ., of C corresponding to the neighbors v i 1 , v i 2 , . . ., of v i in G.

The set-covering instance (S, C) so constructed, has |S| = |C| = n. Furthermore, it is easy to see that any set cover of size k in (S, C) corresponds to a dominating set of the same size in G and vice-versa. Remark also that the dominating set model just assumed on G is exactly, with respect to (S, C), the set-covering model of Section 3. Consequently, the following result follows immediately.

Proposition 2. The on-line set-covering algorithm of Theorem 1 is

√ n-competitive for minimum dominating set in graphs of order n.

A simplified set-covering on-line model

In this section, we assume the following set-covering model. Any time an element σ i of the arrival sequence Σ switches on, only the sequence (S 1 i , . . . , S f i i ), where S j i , j = 1, . . . , f i are as in Section 3, is revealed.

For this model, we consider the following algorithm, denoted by LGREEDY2:

Proposition 3. The competitive ratio of

LGREEDY2 is bounded above by f . Proof. Denote by c 1 , . . . , c k the critical elements of Σ, i.e., the elements having entailed the introduction of S 1 , . . . , S k in S . Denote also by S * an optimum off-line solution. Obviously, for any of the critical elements, a distinct set is needed to cover it, in any feasible cover for C; hence

On the other hand, since, for i = 1, . . . , k, f i f ,

Combining ( 11) and ( 12), the competitive ratio is immediately derived.

Note that algorithm LGREEDY2 is similar to the approximation algorithm for minimum set covering presented in [START_REF] Hochbaum | Approximation algorithms for the set covering and vertex cover problems[END_REF] and, furthermore, it guarantees the same approximation ratio.

The maximum budget saving problem

In this section, we study a kind of dual version of the minimum set-covering, the maximum budget saving problem. Here, we are allotted an initial budget B(S, C) destined to cover the cost of an algorithm that solves minimum set-covering on (S, C). Any such algorithm has its own cost that is a function of the size of the solution produced, of the time overheads it takes in order to compute it, etc. Our objective is to maximize our savings, i.e., the difference between the initial budget and the cost of the algorithm. For simplicity, we assume that the maximum saving ever possible to be performed is B(S, C) -k * , where, as previously, k * is the size of an optimum set-cover of (S, C).

We consider here that the set-covering instance arrives on-line. If a purely on-line algorithm is used to solve it, then its cost equals the size of the solution computed; otherwise, if the algorithm allows itself to wait in order to solve the instance (partly or totally) off-line then, its cost is the sum of the size of the solution computed plus a fine that is equal to some root, of order strictly smaller than 1, of the solution that would be computed by a purely on-line algorithm. We suppose that the budget allotted is equal to k * √ n, where n = |C|. This assumption on B(S, C) is quite natural. It corresponds to a kind of feasible cost for an algorithm; this is algorithm LGREEDY presented in Section 3.

The interpretation of this model is the following. We are allotted a budget corresponding to the cost of an algorithm always solving set-covering. In this way, we are sure that we can always construct a feasible solution for it. Furthermore, by the second part of Theorem 1, it is very risky to be allotted less than k * √ n since there exist instances where the bound √ n is attained. On the other hand, we can have at our disposal a bunch of on-line or off-line set-covering algorithms, any one having its proper cost as described just above, from which we have to choose the one whose use will allow us to perform the maximum possible economy with respect to our initial budget. The fact that the measure of the optimum solution for maximum budget saving is B(S, C) -k * , has also a natural interpretation: we can assume that there exist an arrival sequence Σ for C such that, for any σ i ∈ Σ, an oracle can always choose to cover σ i with the same set with which σ i is covered in an optimum off-line solution for instance (S, C). Under this assumption for is also computed with respect to the algorithm of [START_REF] Alon | The online set cover problem[END_REF]), then a similar analysis as in the proof of Theorem 2 leads to the same result, i.e., that FGREEDY remains asymptotically optimum.

Also, if the budget allotted is k * √ n and one calls the on-line algorithm of [START_REF] Alon | The online set cover problem[END_REF], this latter algorithm is asymptotically optimum for maximum budget saving.

Conclusions

We have introduced an on-line model associated with a natural greedy on-line algorithm achieving non-trivial competitive ratio √ n. Moreover, we have shown that this simple algorithm is strongly competitive since no on-line algorithm for this model, even if it introduces in the cover more than one sets at a time, can guarantee better than n/2. One of the features of our model is that the algorithm can run with an extremely small amount of memory and disk requirements (using, for example, only O(log m) space) and hence it is suitable to solve very large instances.

Next, we have introduced and studied the maximum budget saving problem. Here, we have relaxed irrevocability in the solution construction by allowing the algorithm to delay its decisions modulo some fine to be paid. For such a model we have shown that the natural greedy off-line algorithm is asymptotically optimum.

A subject for further research is the extension of our models to deal with minimumweight set-covering. For this version work is in progress.


Francesca Frontini
email: francesca.frontini@lip6.fr

Carmen Brando
email: carmen.brando@lip6.fr

Jean-Gabriel Ganascia
email: jean-gabriel.ganascia@lip6.fr

Domain-adapted named-entity linker using Linked Data

Keywords: named-entity disambiguation, evaluation, linked data, digital humanities

We present REDEN, a tool for graph-based Named Entity Linking that allows for the disambiguation of entities using domainspecific Linked Data sources and different configurations (e.g. context size). It takes TEI-annotated texts as input and outputs them enriched with external references (URIs). The possibility of customizing indexes built from various knowledge sources by defining temporal and spatial extents makes REDEN particularly suited to handle domain-specific corpora such as enriched digital editions in the Digital Humanities.

Introduction

Semantic annotation plays an important role in the construction of enriched digital editions in the domain of Digital Humanities. The TEI annotation standard 3defines specific tags to mark-up key words in texts and to link them to background knowledge by using external references. Thus, for instance, it is possible to annotate topics, citations, places, organization and person names. References can point to internal identifiers or to external resources that are available in the form of Linked Data (LD) on the semantic Web. Such annotations can be used to facilitate research on the enriched texts (by allowing the creation of indexes and the performing of advanced queries). Moreover, they can also enhance the utilization of texts by the final user, since TEI can be easily converted into other formats, notably Electronic Publication (EPUB). Physical supports such as ebook readers could in future make use of the enriched information in the form of external links.

The results of the work described here make up part of an editorial pipeline the aim of which is produce an enriched digital edition of a corpus of French literary criticism and essays from the 19th century 4 . Such a corpus, once completed, is intended to allow researchers to gain a more comprehensive perspective on the evolution of ideas both in literature as well as in the sciences over the years. While the production of high quality digital editions requires manual checking, natural language processing techniques can speed up the process to a great extent. In particular, the detection of person mentions is a very important step for the enrichment of such a corpus, as it allows researchers to trace references to authorities (authors, scientists, critics, etc.) over time and from different books.

While existing Named Entity Recognition and Classification (NERC) algorithms can help human beings to detect persons' mentions, previous experience has shown that this step is not particularly difficult for trained annotators. Conversely, disambiguation and linking of mentions to an identifier can often be painstaking when done manually, as it requires searching external sources, such as mainstream online encyclopedias (Wikipedia) but also domain-specific databases, such as library databases. Named Entity Linking (NEL) algorithms [START_REF] Rao | Entity linking: Finding extracted entities in a knowledge base[END_REF] can thus be of great use, as they automatically assign an external identifier to already detected mentions, performing disambiguation and semantic annotation at the same time. They rely on external sources of structured or unstructured information to perform this task which is complex, because an entity is usually mentioned in the text in ambiguous forms.

While current NEL algorithms perform well on the contemporary news texts domain adaptation is, as always in NLP, an issue. Nineteenth century essays for instance often mention persons that were well known at the time but are currently hard to identify even for specialists. Thus although existing NEL tools are very efficient they mostly rely on generic background knowledge such as Wikipedia or DBpedia that may not be sufficient to grant ample coverage for all domains.

The solution we present here is a NEL tool, REDEN, that makes use of state of the art graph-based algorithms and at the same time can easily leverage knowledge from different sources (both generic and domain specific). REDEN is applied to already detected mentions, and relies natively on knowledge drawn from linked data sources for disambiguation, requiring only an index of superficial forms and URIs to be used as candidates. Such indexes can be built out of different sources using crawlers.

The purpose of this paper is to show that such a solution can be efficiently used for texts in which a domain specific knowledge base is necessary. We evaluate REDEN on ad-hoc test-sets from our corpus of essays and compare the results with those obtained with a freely available NEL tool. We first present the current state of the art in NEL, then briefly describe the tool and then focus on the index building facilities; some experiments are presented to compare our proposed solution to the state of the art, and we conclude with some remarks and ideas for future developments.

Related work

Supervised methods usually perform very well in NLP tasks but they rely on pre-annotated corpora for training which are not available for specific domains such as French Literature and the Digital Humanities more generally. Therefore we concentrate on existing non-supervised approaches for NEL. These can be broadly divided into two main families. Those using text similarity along with statistical models and those using graph-based methods.

The best known tool from the first group is DBpedia Spotlight (DBSL) [START_REF] Daiber | Improving efficiency and accuracy in multilingual entity extraction[END_REF] which performs NER and DBpedia linking at the same time. It is based on cosine similarities and a modification of TF-IDF weights. More specifically, recognition of possible annotations in a text is performed using indexes built from the Wikipedia dumps and DBpedia by substring matching algorithms. DBSL generates DBpedia candidates for each possible annotation in two possible ways, using a language-dependent implementation (available for English and Dutch and more NLP-adapted) or a language-independent implementation which is more efficient but less precise. DBSL then selects the best candidates from the set of annotations by computing scores that combine statistical methods, the Wikipedia article links along with their anchor texts and textual context. This or similar methods are known to be very efficient, but they can are strongly dependent on the availability of textual descriptions for each entry.

Graph-based approaches rely on formalised knowledge in the form of a graph built from a knowledge base (e.g. the Wikipedia article network, Freebase, DBpedia, etc.). Reasoning can be performed through graph analysis operations. It is thereby possible to at least partially reproduce the actual decision process with which humans disambiguate mentions. A reader may decide that the mention "James" refers to philosopher "William James" and not to writer "Henry James" because it occurs in the same context as "Hume" and "Kant". In the same way such algorithms build a graph out of the available candidates for each possible referent in a given context and use the relative position of each referent within the graph to choose the correct referent for each mention. The graph is built for a context (e.g. paragraph) containing possibly more than one mention, so that the disambiguation of one mention is helped by that of the others. Hybrid approaches such as [START_REF] Usbeck | Agdistis -graphbased disambiguation of named entities using linked data[END_REF] can use both graph-based algorithms, more specifically graph-search ones, and text similarity measures; they rely on a single LD source.

The graph-based NEL is similar to graph-based Word Sense Disambiguation (WSD) [START_REF] Sinha | Unsupervised graph-basedword sense disambiguation using measures of word semantic similarity[END_REF], where a set of words in a given sentence needs to be labeled with the appropriate sense label by using the information contained in a lexical database such as WordNet. The key idea of this approach is that, for all ambiguous words in the context, senses that belong to the same semantic field should be selected, and that in this way two ambiguous words can mutually disambiguate each other. More specifically, a subgraph is built, constituted only of the relevant links between the possible senses of the different words, and then for each alternative sense labeling, the most central is chosen. This procedure, when applied to such context specific subgraphs, ensures that in the end the chosen senses for each word will be those that are better connected to each other.

Centrality is an abstract concept, and it can be calculated by using different algorithms 5 . In [START_REF] Sinha | Unsupervised graph-basedword sense disambiguation using measures of word semantic similarity[END_REF] the experiment was carried out using the following algorithms: Indegree, Betweenness, Closeness, PageRank, as well as with a combination of all these metrics using a voting system. Results showed the advantages of using centrality with respect to other similarity measures.

This graph-based approach has been applied to NEL, where mentions take the place of words and Wikipedia articles that of WordNet synsets. Here too centrality measures are performed on the Wikipedia structure in order to use the large set of relations to disambiguate mentions. More specifically in [START_REF] Hachey | Graph-based named entity linking with wikipedia[END_REF] English texts were disambiguated using a graph that relied only on English Wikipedia, and was made up of the links and of the categories found in Wikipedia articles. So for instance the edges of the graph represented whether ArticleA links to ArticleB or whether ArticleA has Here too "local" centrality is used to assign a correct link to an ambiguous mention. Such a WSD based tool for NEL is proposed by the DBpedia Graph Project6 . However, it is highly dependent on DBpedia structure and only links to this broad-coverage data set and not to other domain-specific ones.

Our disambiguation approaches

With REDEN, we propose a graph-based, centrality-based approach that is particularly adapted for digital humanities; in fact it can exploit RDF sources directly (thus allowing users to choose domain adapted knowledge bases) and takes TEI-annotated texts as input. The disambiguation algorithm processes a file where NE mentions are already annotated (e.g. using the tag <persName>).

Possible referents from all mentions in a given context and for a given class (e.g. person) are retrieved from an index built on the fly from selected LD sources. The fusion of homologous individuals across different sources is performed thanks to owl:sameAs or skos:exactMatch predicates; a graph is created where RDF objects and subjects are vertices and RDF predicates represent edges. Irrelevant edges are removed from the graph before calculating centrality: only edges which involve at least two vertices representing candidate URIs are preserved. Thanks to the selected centrality measure, the best connected candidates for each mention are chosen as referents and an enriched version of the input TEI file is produced.

To illustrate how REDEN works, we apply our approach to a paragraph from a French text of literary criticism entitled "Une thèse sur le symbolisme" (1936) written by Albert Thibaudet (1874-1936) 7 . Figure 1 shows an excerpt of the resulting graph where the chosen and correct mention candidates out of the nine present in the text are marked in bold. We can observe that the vertices yago:Symbolist Poets, dbpedia:Charles Baudelaire, dbpedia:French Dramatists And Playwrights are the ones influencing the centrality measure the most. We developed our implementation in Java 8 . In [START_REF] Frontini | Semantic web based named entity linking for digital humanities and heritage texts[END_REF][START_REF] Brando | Disambiguation of named entities in cultural heritage texts using linked data sets (accepted)[END_REF], we described the steps of the algorithm in detail. In the following section, we detail the software component for building on-the-fly a domain-adapted index of possible mention candidates.

Domain-adapted crawler of Linked Data

As previously described, REDEN identifies and looks for mention candidates' URIs in indexes built on the fly per class. So for instance, the entries of a person in the index correspond to superficial forms of that person's name and the corresponding URIs from different Linked Data sets. REDEN then retrieves the RDF data from the corresponding URIs found in the index for each selected source.

Clearly, a source can be more useful for certain domains than another, for instance the French National Library (BnF) linked data repository is the most appropriate source for a domain such as French literary criticism. BnF provides the catalog of authors for all books ever published in France; their entries contain information on dates of birth and death, gender, alternative names, works authored, etc. Most importantly, BnF provides equivalence links (owl:sameAs) to other sources such as DBpedia or IdRef. Thus, BnF can be chosen as the entry point for building an index of authors. In particular information on gender and full names can be used to generate further alternative names -for instance: surname only (Rousseau), initials + surname (J.J. Rousseau, JJ Rousseau, ...), title + surname (M. Rousseau, M Rousseau), ... Equivalence links may also be stored, so that later on REDEN can build fused graphs from different sources.

Likewise, using DBpedia as entry point an index of places can be assembled. For instance, the DBpedia entity Gare de Paris Saint-Lazare has the following name forms (familiar, official and old ones) -for instance: Gare Saint-Lazare, Gare Saint-Lazare (Paris), Embarcadère de l'Ouest, ... 8 Code source and useful resources can be found here: https://github.com/cvbrandoe/REDEN

We have therefore developed an index-building module which allows for the configuration and the implementation of a crawler for a chosen LD source. The main purpose of this module is to facilitate the construction and the update of entity indexes which should be suitable for the domain of the exploited corpora. In particular, the temporal dimension and possibly the spatial dimensions can be used as filters. For instance when working with 19th century texts, a time filter can a priori exclude the currently well-known singer Thierry Amiel as a candidate for the mention 'Amiel' and thus enable the identification of the correct referent, well-known writer Henri-Frédéric Amiel.

The proposed module takes into account domain parameters such as the temporal and spatial dimensions. For instance, a time period can be specified with respect to the date of birth of the persons described in the corresponding linked data set, or to any other property of the individual (date of death, periods of activity). Concerning the spatial extent of the index, one may be interested in including only persons who were born or have lived in Europe because the corpora probably concerns authors with these features. A bounding box can be defined by specifying a rectangle consisting of four Latitude and Longitude coordinates 9 . It is also straightforward to define new domain parameters to filter for themes, such as Symbolism or Psychology.

From a technical point-of-view, a crawler performs SPARQL queries using a selected end point. The created indexes can benefit from text search engines which enable the optimal querying of candidates by REDEN and therefore reduce query processing time.

Currently REDEN comes with two already implemented crawlers: one to collect an index of place candidates from DBpedia and one to crawl an index of author candidates from the LD repository of the BnF, containing alternative names for every entity. In the case of authors, as BnF entries point to DBpedia equivalents when available, these two sources can be easily fused using the aforementioned algorithm. In the case of places, there is no need to fuse other LD sources although one may be interested in including a place gazetteer available in linked data such as Pleaides10 when working with Ancient texts.

Tool assessment

In previous experiments [START_REF] Frontini | Semantic web based named entity linking for digital humanities and heritage texts[END_REF][START_REF] Brando | Disambiguation of named entities in cultural heritage texts using linked data sets (accepted)[END_REF], we have discussed and evaluated our graph-based method, which allows for state of the art accuracy in NEL for the texts in our domain. Here we assess REDEN as a tool, thus not only in terms of accuracy, but also of adaptability and usefulness. For this reason we compare the performance of our linker with an available state of the art tool such as DBpedia Spotlight (DBSL). As our texts are in French, the language independent version of DBSL is used. Thus the comparison is not fair, as this version performs both NERC and NEL at the same time, while we run REDEN on a TEI text with a pre-checked set of classified mentions. Nevertheless, the comparison can help to give an idea of the differences in coverage that our method offers.

Since REDEN treats one class at a time, DBSL too is called with the chosen class as a parameter. Moreover, we use the most relaxed configuration possible, accepting any matching results with no filter on support or confidence, to maximize recall. DBSL is installed locally and launched using French DBpedia as a knowledge base. As for REDEN, the chosen centrality measure is DegreeCentrality [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF].

The manually linked test corpus consists of a French text of literary criticism entitled "Une thèse sur le symbolisme" (A thesis about Symbolism) published by Albert Thibaudet in 1936, and a scientific essay entitled "L'évolution créatrice" (Creative Evolution) written by Henri Bergson and published in 1907. We can consider two measures of accuracy: A1, the proportion of correct links over the mentions for which a link was chosen, and A2, the proportion of correctly assigned links over the number of mentions overall. The second measure considers missing links as mistakes, and can be seen as a measure for coverage11 .

Experiment 1: Locations

Even though REDEN's strength lies in the possibility of merging resources, we will first compare the two algorithms on French DBpedia alone12 . Since DBSL cannot process more than a paragraph at a time, REDEN too is configured to use paragraphs as contexts for its graphs. We choose the task of linking location mentions, which, in our texts are rather sparse but not particularly domainspecific. A priori we expect most referents for locations' mentions to be present in the knowledge base. As shown by the results, both linking algorithms are comparable. They both achieve excellent correctness rates when they assign links, but they miss a certain number of places. Missing places occur often due to the lack of alternative names, such as "Lacédémone" (another name for Sparta), or from entries that are missclassified in DBpedia, such as "Berlin" which is classified as a Concept and not as a Location (in the French version of DBpedia). REDEN achieves a better coverage even when using the same knowledge base, possibly because it better exploits the available alternate names, or because DBSL does not provide an answer when it is unable to find a correspondence between the textual context of a mention and the description of a candidate.

As previously stated this evaluation is meant as a comparison of the algorithms, as REDEN works on pre-detected mentions while DBSL has to perform detection too. That said, in this experiment DBSL analyses only paragraphs containing locations and we force the type "location" in input; in most cases when DBSL is missing a link the name of the mention is written in capitalized words and coincides exactly with the title of a DBpedia entry; thus it is possible to conclude that, in such cases, it is not the detection but the linking that fails.

Experiment 2: Persons

The second experiment aims to show how our tool can achieve a much better performance on this corpus thanks to the possibility of combining two knowledge bases to target a specific domain. Here, the more difficult task of identifying authors' mentions is evaluated. DBSL is run using French DBpedia as usual, REDEN is run on an index of authors built from French DBpedia + the BnF linked data. Moreover, we exploit all the fine-tuning options offered by REDEN: in order to best exploit contextual information we increase the disambiguation context, using the chapter for Thibaudet, which is a text with high mentions' density, and the whole book for Bergson because it is poorer in mentions 13 . Moreover, we filter the index by preventing authors who weren't born or were too young at the time of publication of each work from becoming candidates. As shown in Table 2, DBSL achieves a high correctness rate for persons when it makes a choice, assigning almost perfectly each mention found on both corpora. On the other hand, the amount of entities found is much smaller. The reason is obviously that REDEN exploits additional information, granting coverage for authors who aren't present in DBpedia.

At the same time, we notice that DBSL correctly recognizes the mention of (Alphonse de) "Lamartine" but not those of (Maurice) "Barrès" and (Alphred de) "Vigny", when all three authors have a referent in DBpedia, and despite the fact that we are running the algorithm with the lowest possible confidence. This may mean that the unstructured information on which DBSL relies is not enough to make a decision, while the graph of relations that REDEN exploits is richer in information. Generally speaking REDEN's correctness rate is close to state of the art (even with respect to other graph-based algorithms, whose stated correctness rate is around 0.85), although Thibaudet, which is richer in mentions, gives better results.

It is important to note here that DBSL is more precise than REDEN in those cases where it actually chooses a link (A1). In particular, it beats our method when a paragraph contains only one ambiguous candidate mention. In this case, the unstructured textual context is a useful source of information to disambiguate, while the graph-based algorithm cannot use background information. Nevertheless, the greater coverage of the graph-based approach makes the overall post-processing work of manual checking less cumbersome in terms of both correction and integration.

Conclusions and future work

In this article we presented REDEN, a graph-based tool for Named Entity Linking that can be easily extended to different online sources and tailored to suit various different needs. Domain adaptation is enabled by entity indexes built on the fly using linked data crawlers. New sources for a particular domain can be added by configuring a new crawler with the appropriate SPARQL query. Experiments involving the disambiguation of persons' and locations' names in a corpus of French essays of the 19th century show how the graph-based algorithm gives us state of the art correctness results while allowing for more flexibility and coverage.

The experiment with DBSL highlighted some of the practical advantages of our tool. First, DBSL is very dependent on the DBpedia. Configuring it to use new knowledge bases such as BnF does not yet seem possible. Furthermore, REDEN works natively with RDF. The structured information used has thus the potentiality to grow as new links are added to the semantic web. REDEN uses online sources (end points) which allows for the easily downloading of the most up-to-date version of the data from the corresponding repository. These data are cached by REDEN in order to download an RDF resource only once. On the contrary, DBSL uses offline resources which can be an advantage when bandwidth is limited, however updating the DBSL knowledge base looks to be a very difficult and time consuming process. Another technical limitation is the size of the context that DBSL uses for its decision; the tool runs as a Web service accepting HTTP calls and the URL size is restricted. In REDEN, the size of the context does not need to be fixed, but can be set by the user according to predefined textual partitions in TEI; thus the tool can run using all mentions in a paragraph, a chapter, or a whole text as a disambiguation context. Finally crawlers can be customized in such a way as to apply (time or space) filters on candidates, thus making it domain adapted.

For these reasons we conclude that the proposed methodology seems better adapted to the task of linking named-entities to a knowledge base other than DBpedia. Thus it seems particularly useful for digital editions in the humanities, where texts are already in TEI format, and specialists have a good knowledge of the text and of relevant sources of information.

As prospective work we intend to perform an exhaustive comparison of RE-DEN to other graph-based NEL tools such as AGDISTIS [START_REF] Usbeck | Agdistis -graphbased disambiguation of named entities using linked data[END_REF] and the DBpedia Graph Project focusing on domain-specific test corpora, in particular, on texts used in French Literature and more generally in the Digital Humanities.

Fig. 1 .

 1 Fig. 1. Excerpt of the chosen URIs (in bold) for the candidates of the nine mentions; a color distinguishes candidates of a single mention; all edges represent rdf:type links except those marked differently.

Table 1 .

 1 Comparing the performance of REDEN with DBpedia spotlight on our two corpora for Locations. None=link not found.

	Corpus Mentions	REDEN Found Correct None A1 A2 Found Correct None A1 A2 DBSL
	Thibaudet	382	257	257	132 1.0 0.67 198	195	184 0.98 0.51
	Bergson	58	49	49	9 1.0 0.84 42	41	16 0.97 0.70

Table 2 .

 2 Comparing the performance of REDEN with targeted settings with DBpedia spotlight on our two corpora for Persons.

	Corpus Mentions	REDEN Found Correct None A1 A2 Found Correct None A1 A2 DBSL
	Thibaudet 1027	1004	878	23 0.87 0.85 177	174	850 0.98 0.17
	Bergson	277	274	222	3 0.81 0.68 8	8	269 1.0 0.03

http://www.tei-c.org/index.xml

http://obvil.paris-sorbonne.fr/corpus/critique/

For a discussion of the notion of centrality see also[START_REF] Rochat | Character Networks and Centrality[END_REF]

https://github.com/bernhardschaefer/dbpedia-graph but related published work is not available at this time

Full text can be found here: http://obvil.paris-sorbonne.fr/corpus/critique/ thibaudet reflexions.html

Some Web mapping tools easily provide this kind of information: http://www.mapdevelopers.com/geocode bounding box.php

http://pleiades.stoa.org

These measures may be considered to roughly correspond to precision and recall, though such terms seem less adapted to describe this type of task.

REDEN and DBSL use versions of 05/03/15 and of 17/07/2014, respectively. Unfortunately, it is technically not possible for REDEN to access a snapshot of DBpedia RDF resources from that particular date.

In[START_REF] Brando | Disambiguation of named entities in cultural heritage texts using linked data sets (accepted)[END_REF], we showed that considering different context sizes can increasingly improve correctness rates; we also assess the impact of filtering the knowledge base with temporal window.

Acknowledgements

This work was supported by French state funds managed by the ANR within the Investissements d'Avenir programme under reference ANR-11-IDEX-0004-02 and by an IFER Fernand Braudel Scholarship awarded by FMSH.