Matthias Gall É
email: matthias.galle@irisa.frpierre.peterlongo@irisa.frfrancois.coste@irisa.fr

Pierre Peterlongo

¸ois Coste

IN-PLACE UPDATE OF SUFFIX ARRAY WHILE RECODING WORDS

Keywords: suffix array, in-place update, dynamic indexing, word-interval 68-04, 68P05

Motivated by grammatical inference and data compression applications, we propose an algorithm to update a suffix array while in the indexed text some occurrences of a given word are substituted by a new character. Compared to other published index update methods, the problem addressed here may require the modification of a large number of distinct positions over the original text. The proposed algorithm uses the specific internal order of suffix arrays in order to update simultaneously groups of indices, and ensures that only indices to be modified are visited. Experiments confirm a significant execution time speed-up compared to the construction of suffix array from scratch at each step of the application.

Motivation

In this paper, we propose an algorithm to efficiently update a suffix array, after substituting a word by a new character in the indexed text. This work is motivated by grammatical inference or grammar-based compression, along the lines initiated by SEQUITUR [START_REF] Nevill-Manning | Identifying hierarchical structure in sequences: A linear-time algorithm[END_REF] in the framework formalized by Kieffer and Yang [START_REF] Kieffer | Grammar-based codes: A new class of universal lossless source codes[END_REF][START_REF] Kieffer | Grammar-based codes: a new class of universal lossless source codes[END_REF]. The goal is to infer a grammar G which generates only a given (long) sequence s in order to discover the structure that underlies the sequence, or simply, to compress the sequence thanks to a code based on the grammar. Learning and compression being often subtly intertwined (as for instance in the Occam's razor principle), in both cases the grammar is expected to be as small as possible. Kieffer and Yang introduced the definition of irreducible grammars and proposed several reduction rules allowing to transform a reducible grammar into an irreducible one, giving rise to efficient universal compression algorithms [START_REF] Kieffer | Grammar-based codes: A new class of universal lossless source codes[END_REF]. The sketch of these algorithms is to begin with a unique S → s rule generating the whole given sequence and to reduce iteratively the size of the grammar at each step by: 1) choosing a repeated substring, 2) replacing the occurrences of the repeated substring by a new symbol and 3) adding a new rewriting rule from this new symbol into the repeated substring. For instance, the sequence uRvRw, where u, v, w and R are substrings, and the length of R is strictly bigger than one, would be rewritten by a rule S → uRvRw. At the first step, this rule can be reduced into two rules S → uAvAw and A → R, where A is a new (non-terminal) symbol. At the following step, another repeated substring, including eventually the new inserted symbol A, is selected and factorized by the introduction of a third rule, and so forth for the next steps. As a result, the algorithm returns a compact grammar which can be used to get a hierarchical point of view on the structure of the sequence or which can be encoded in order to get a better compression than by encoding directly the sequence.

Algorithms of this kind are thus mainly based on the successive detection of repeats. They differ mostly in the order in which repeats are factorized. In SE-QUITUR [START_REF] Nevill-Manning | Identifying hierarchical structure in sequences: A linear-time algorithm[END_REF] and its variant [START_REF] Kieffer | Grammar-based codes: a new class of universal lossless source codes[END_REF], each repeat is replaced as soon as it is detected by a left to right scan of the sequence. More elaborate strategies for choosing the repeat to replace have been proposed. Kieffer and Yang [START_REF] Kieffer | Grammar-based codes: A new class of universal lossless source codes[END_REF], Nakamura and Bannai [START_REF] Nakamura | Simple linear-time off-line text compression by longest-first substitution[END_REF] and Lanctot, Li, and Yang [START_REF] Lanctot | Estimating dna sequence entropy[END_REF] proposed to replace longest matching substring. Apostolico and Lonardi [START_REF] Apostolico | Off-line compression by greedy textual substitution[END_REF] proposed in their algorithm Off-Line to choose the substring yielding the best compression in a steepest-descent fashion. A comparison between the different strategies can be found in [START_REF] Nevill-Manning | On-line and off-line heuristics for inferring hierarchies of repetitions in sequences[END_REF].

Efficient implementation of an elaborate choice of repeat often requires the use of data structures from the suffix tree family. These index structures are well suited for efficient computations on repeats but they have to be built at initialization, and then updated at each step of the algorithm with respect to sequence modifications. Yet, as pointed out by Apostolico and Lonardi [START_REF] Apostolico | Off-line compression by greedy textual substitution[END_REF], most of the published work on dynamic indexing problem [START_REF] Sahinalp | Efficient approximate and dynamic matching of patterns using a labeling paradigm[END_REF], by updating a suffix tree [START_REF] Chan | Compressed indexes for dynamic text collections[END_REF][START_REF] Ferragina | On updating suffix tree labels[END_REF][START_REF] Fiala | Data compression with finite windows[END_REF][START_REF] Gu | An efficient algorithm for dynamic text indexing[END_REF][START_REF] Mccreight | A space-economical suffix tree construction algorithm[END_REF] or suffix array [START_REF] Salson | Dynamic burrows-wheeler transform[END_REF] focuses on localized modifications of the string. They do not seem appropriate for efficiently replacing more than one occurrence of a given substring, as they would require one update operation for each occurrence.

Thus, index structures have usually to be built from scratch at each step of the algorithm. To our knowledge, only GTAC [START_REF] Lanctot | Estimating dna sequence entropy[END_REF], an algorithm applied successfully on genomic sequences by Lanctot, Li and Yang, updates a suffix tree data structure after the deletion of all occurrences of a word. More recently, [START_REF] Nakamura | Simple linear-time off-line text compression by longest-first substitution[END_REF] solved the same problem also in linear time. However, their updating scheme are specific to the longest matching substrings and seems difficult to adapt to other strategies.

In this paper, we propose a solution to the problem of updating efficiently an index structure while replacing some non-overlapping occurrences of a word of the indexed text by a new symbol. The first originality of our approach relies on the use of enhanced suffix arrays instead of suffix trees. Enhanced suffix arrays are known to be equivalent to suffix trees while being more space efficient [START_REF] Abouelhoda | Replacing suffix trees with enhanced suffix arrays[END_REF]. They can be In-Place Update of Suffix Array While Recoding Words 3 built in linear time [START_REF] Kärkkäinen | Simple linear work suffix array construction[END_REF][START_REF] Ko | Space efficient linear time construction of suffix arrays[END_REF][START_REF] Kyue | Linear time construction of suffix arrays[END_REF] but non-linear algorithms [START_REF] Larsson | Faster suffix sorting[END_REF][START_REF] Manzini | Engineering a lightweight suffix array construction algorithm[END_REF] are usually more efficient for practical applications. A simple way of updating suffix array (instead of enhanced suffix array, thus without the same efficiency objective) by lazy bubble sort has been used in [START_REF] Nevill-Manning | On-line and off-line heuristics for inferring hierarchies of repetitions in sequences[END_REF]. We propose here, to take advantage of the internal order offered by enhanced suffix arrays, to simultaneously handle groups of indices. This enables us to efficiently implement an update procedure for grammatical inference or grammar-based compression algorithm, choosing at each step a repeated substring, and replacing some or all of its occurrences by a new symbol.

Definitions and notations

A sequence is a concatenation of zero or more characters from an alphabet Σ. The number of characters in Σ is denoted by

|Σ|. A sequence s of length n on Σ is represented by s[0]s[1] . . . s[n -1], where s[i] ∈ Σ ∀ 0 ≤ i < n. We denote by s[i, j](j ≥ i) the sequence s[i]s[i + 1] . . . s[j] of s (if j < i then s[i, j] = ,
the empty string). In this case, we say that the sequence s[i, j] occurs at position i in s. Its length, denoted by |s[i, j]|, is equal to j -i + 1. Furthermore, the sequence s[0, j] (0 ≤ j < n), also denoted by s[..j], is called a prefix of s, and symmetrically,

s[i, n -1] (0 ≤ i < n), also denoted by s[i..], is called a suffix of s.
Definition 1 (Suffix Array) Consider a sequence s of length n over an alphabet Σ with an order ≺ extensible to Σ * . This lexicographically extension will be denoted also by ≺. Let s = s$, with a special character $ not contained in Σ, smaller than every element of Σ.

The suffix array, denoted by sa, is a permutation of [0.

.n] such that:

∀ i, 0 < i ≤ n : s[sa[i -1]..] ≺ s[sa[i]..]
Usually, the suffix array is used conjointly with an array called lcp, that gives the longest common prefix length between two suffixes whose starting positions are adjacent in sa. Formally,

lcp[0] = 0,
and

∀ i ∈ [1, n] : lcp[i] = k such that s[sa[i -1]..][0, k -1] = s[sa[i]..][0, k -1] and s[sa[i -1]..][k] = s[sa[i]..][k].
Eventually, a third array called isa (for inverse suffix array) may be used conjointly with sa and lcp. This array gives, for a position p in s, the index i in sa such that sa

[i] = p. Thus sa[isa[p]] = p.
The union of sa, lcp and isa arrays is called an Enhanced Suffix Array (ESA). An ESA enables O(n) computation of occurrences of different kinds of repeats (repeats, maximal repeats [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology[END_REF][START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF] or super maximal repeats [START_REF] Abouelhoda | Replacing suffix trees with enhanced suffix arrays[END_REF][START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology[END_REF]).

To avoid confusion, we will use the term position when referring to the index over a sequence and index when referring to any of the arrays of an ESA.

In this paper, we propose to update an ESA, deleting and moving some of its indices and keeping lcp consistent. In order to avoid shifting set of indices, we link consecutive indices using two additional arrays called next and prev. Thus, next [ It is worth noticing that an ESA DL does not have the exact same properties as an ESA. Indeed, going from an index i to index i + j may be done in constant time on an ESA, while this operation in an ESA DL requires O(j) time, as the next array has to be used j times.

Anyway, an ESA DL still allows the detection of repeats (general repeats, maximal repeats or super maximal repeats) in linear time, because the algorithms used advance one by one over the arrays like most of the algorithm over ESA (a notable exception is the algorithm searching for a substrings proposed in [START_REF] Sim | Time and space efficient search for small alphabets with suffix arrays[END_REF]).

We propose an in-place solution, where we always work with the same arrays and only update the values of their fields. Moreover, during the whole process, we modify only the prev, next and lcp arrays. Arrays sa and isa remain unchanged. This approach forces to extend the in-place behavior to the sequence: we also add two arrays to imitate a double linked list over the sequence.

The j th position after position i, is denoted by i⊕j. We compute i⊕j using links between sequence positions, indicating for each position its successor. Similarly i j points to the j th position before i. We define that, if i ⊕ j (respectively i j) is out of range, then i ⊕ j = n + 1 (respectively i j = -1).

We consider that the grammatical inference or grammar based compression algorithm proceeds by steps. At each step, the alphabet grows because of the introduction of a new character: Σ k will denote the alphabet in step k. At each of these steps the algorithm i) finds a repeat R k in a sequence s(k) defined on the alphabet Σ k and returns a list O k of non-overlapping occurrences of R k ii) updates the sequence s(k) and its associated ESA DL replacing the given occurrences of R k by a single new character C k , thus defining a new alphabet Σ k+1 = Σ k ∪ {C k }. The modified sequence is then called s(k+1) . The whole iterative process stops either if no more repeat is found in the sequence or after a fixed number of iterations.

Our contribution focuses on updating the ESA DL , at each step k of this algorithm (part ii).

In the next sections, we describe how to perform the three tasks needed for updating an ESA DL at each step k: 1) delete indices of suffixes starting inside an R k occurrence; 2) move indices with respect to the new alphabetic order; and 3) update lcp array with respect to recoding occurrences of R k by one single character. Note that a few values of the lcp array are also modified during step 1 and 2, but only as a consequence of deletions and moves.

In-Place Update of Suffix Array While Recoding Words 5

Algorithm

Before describing the different steps of the algorithms, we will define the left context tree which result useful to better understand the algorithm and the modifications it made over the suffix array.

The left context tree.

One of the most useful characteristics of a suffix array is that all indices corresponding to suffixes starting with the same word correspond to an adjacent block. We define here the corresponding concept of word interval. Based on this, we will define the left context tree of a word ω where the nodes correspond to a left context of ω.

An ω-interval is the set {k :

∃ , k = isa[ ] ∧ s[ .. + |ω| -1] = ω}.
This can also be denoted as an [i..j]-interval, where i and j are respectively the lowest and highest indices of an ω-interval. Let us note that different words can share the same interval. More precisely, any pair of words ω and ωα share the same interval if each occurrence of ω is followed by α.

This definition is thus slightly more general than the definition of ω-interval given by Abouelhoda, Kurtz and Ohlebusch [START_REF] Abouelhoda | Replacing suffix trees with enhanced suffix arrays[END_REF], since we also define ω-interval for words leading to implicit nodes of a compact suffix tree, and not only to internal nodes.

The left context tree of ω (ω ∈ Σ * ) for a sequence s is an implicit tree whose nodes are v-intervals (v ∈ Σ * ) such that:

• the root is the ω-interval • for each v-interval node corresponding to a non-empty interval, its children are all the av-intervals, for all a ∈ Σ • the leaves are empty intervals Given the isa array, it is easy to obtain the parent of a node. Let [i..j] be an av

-interval node. Given k ∈ [i..j], isa[sa[k] + 1] is an index belonging to the v- interval. Inversely, isa[sa[k] -1]
belongs to one of the child interval. The exact child depends on the character at s[sa[k] -1]. We introduce the successor and predecessor notations:

successor(i) = isa[sa[i] ⊕ 1] if sa[i] ⊕ 1 = n + 1 n + 1 otherwise, and
predecessor(i) = isa[sa[i] 1] if sa[i] = 0 -1 otherwise.
One may remark that predecessor(i) is the equivalent of the "suffix link" in a suffix tree [START_REF] Ukkonen | On-line construction of suffix trees[END_REF].

The problem that an ESA update algorithm must face is that the changes over the occurrences of a word ω not only affect the ω-interval, but also some of the vω-intervals (v ∈ Σ * ). The core of our algorithm is based on moving vω-interval in constant time, using the two following properties implied by the internal order of suffix arrays:

Proposition 2. Let [i..j] be an v-interval (v ∈ Σ * ), and k 1 , k 2 ∈ [i..j] with k 1 > k 2
and such that predecessor(k 1 ) and predecessor(k 2 ) belong to the same αv-interval

(α ∈ Σ). Then predecessor(k 1 ) > predecessor(k 2 ). Proposition 3. With i < j, the longest common prefix between s[sa[i]..] and s[sa[j]..] is min k∈[next[i],j] (lcp[k]).

Delete indices of suffixes occurring inside R k substituted occurrences

By replacing the word R k by a single letter, the sequence is compressed and so is its ESA DL : consequently, any suffix of sequence s(k) appearing inside an R k substituted occurrence must be deleted. An example is shown in Figure 1 where the deletion of index j affects the lcp[next [j]] that now should contain the length of longest common prefix between ATGT and ATAC which is 2, equal to the longest common prefix of ATGT, ATGA and ATAC.

Algorithm 1 presents the procedure for deleting indices. The notation EN D refers to the last index of the suffix array (prev[n + 1]).

Move indices, with respect to new alphabetic order

After replacing the word R k by the new character C k , some ESA DL lines may be misplaced with respect to the chosen order of C k in Σ k+1 .

Indices in the R k -interval are potentially misplaced. Moreover, for v ∈ Σ * k , index inside an vR k -interval are misplaced if the substitution of R k into C k affects their lexicographical order with respect to the previous and next index over the suffix

(k) DL , R k , O k } 1: for i ∈ O k do 2: for ∈ [1, |R k | -1] do 3: j ← isa[i ⊕ ] 4: if next[j] = EN D then 5: lcp[next[j]] ← min(lcp[j], lcp[next[j]]) 6: end if 7: next[prev[j]] = next[j] 8: prev[next[j]] = prev[j] 9:
end for 10: end for array. Thus, lines belonging to node-intervals of the left-context tree of R k may have to be moved.

In our approach, we decided to give to C k the largest rank in the lexicographic order of the alphabet Σ

k , i.e. ∀ α ∈ Σ k : α ≺ C k .
With respect to this arbitrary choice, the R k -interval is moved to the end of the suffix array. Furthermore, for any v ∈ Σ * k , the vR k -interval is moved after the last index of the v-interval.

If an vR k -interval is already at the end of the v-interval (it is naturally well ordered), for any v ∈ Σ * k , the v vR k -interval is also at the end of the v vR k -interval and does not have to be moved.

Based on this property, our algorithm uses a recursive approach in order to move groups. The recursion starts on the initial R k -interval. During recursion, if the group of an vR k -interval is moved, the recursion continues on groups of αvR k -intervals, with α ∈ Σ k .

From a theoretical point of view, the algorithm starts on the root of the leftcontext tree of R k and if the group corresponding to the interval of the node is moved, it recursively treats its children in a breadth first traversal (a FIFO is used).

In practice, the recursion on a vR k -interval works as follows:

(1) detects the end position of the vR k -interval, During a call on predecessor of an index of the group, either this is the first time the matched group is called and by construction the call is done on its first element, or the group was already treated, and the recursion stops.

The algorithm for this step is shown in algorithm 2. This recursive function receives three parameters besides the data structures: the starting position of the group, the current depth over the left-context and a boolean flag (see below).

Algorithm 2 Restore consistency of suffix array order update order{ESA End procedure 3: end if

(k) DL , R k , O k , i start , depth
4: i ← i start 5: while i = EN D ∧ lcp[next[i]] ≥ depth + |R k | do 6: i ← next[i] 7: end while 8: i end ← i 9: minLCP ← min j∈[i start ,i end ] lcp[j] 10: if move then 11: while i = EN D ∧ lcp[next[i]] ≥ depth do 12: i ← next[i]
if i start = i f irst ∧ depth = 0 then 20: i f irst ← next[i end ]
newdepth ← depth+ (if predecessor(i) ∈ O k then len else 1) 30: if move ∨ (sa[prev[predecessor(i)]] > newdepth ∧ sa[prev[predecessor(i)]] ⊕ newdepth ∈ O k ) then 31: update order(ESA (k) DL , R k , O k , predecessor(i), newdepth, i dest = i end ) 32: end if 33: i ← next[i] 34: end while
In first place, the end of the vR k -interval is found (lines 5, 6 and 8). This is done from the first element of the interval, following the next array while the visited index corresponds to a suffix starting with vR k (lcp ≥ |v| + |R k |). After finding the extremes of the group, the destination index of this group according to the chosen order for the new character is found (lines 11, 12 and 15). This is done by finding the end of the v-interval in the same way (lcp ≥ |v|).

Moving the group to its new position is now simple and is done in constant time. Thanks to the well-ordered property of the suffix array, the whole interval is moved by changing only the delimiting positions. Let i start , i end , i dest be respectively the starting and ending positions of the vR k -interval, and the last position of the vinterval. Moving the group [i start , i end ] to the position after i dest is simply done by jumping over the group and inserting it into i dest and next[i dest ]. See the algorithm 3 for implementation details.

Two longest common prefix values are modified as a consequence of the deletion of the group and its insertion:

(1) lcp[next[i end ]]: contains the value of the length of the longest common prefix between prev[i start ] and next[i end ], which according to proposition 3, is the minimum of the lcp values of the group and itself (2) lcp[i start ]: we assign to it the value of depth, that is the correct value over sk+1 . This serves also to set a stop-point for future recursions calls (see below).

As i f irst points to the first line over the suffix array that contains a selected repetition, we also update i f irst (line 19) if this line is moved.

Figure 2 shows the ESA DL of sequence GAAGAAGC, where R 1 = GA is substituted by C 1 . One remarks that the initial interval of suffixes starting with GA (indices 6 and 7) is moved as well as suffix starting with AGA (index 3). Note also that suffix starting with GAAGA has to be moved with respect to suffix GAAGC.

(k) DL , R k , O k , i start , i end , i dest } 1: next[prev[i start ]] = next[i end ] 2: prev[next[i end ]] = prev[i start ] 3: next[i end ] = next[i dest ] 4: prev[next[i dest ]] = i end 5: next[i dest ] = start 6: prev[i start ] = i dest

A special case

Once an interval is treated, the recursion continues either if the current group was moved, or in the special case described in what follows.

Consider for instance the following case, where the substituted repeat is T A. i CTATTTAC. . . i+1 CTATTTAG. . . i+2 CTATTA. . . , and suppose that the T T A-interval containing the index isa[sa[i + 2] ⊕ 3] (the underlined suffix in the figure) was already at its right position and therefore does not have to be moved. So, its children in the left-context tree are not considered for future moves, and as a consequence, neither is index i+2. Supposing that we cut the recursion here, that means that when treating the CT AT T -interval, lcp[i + 2] = 5. This interval ends at the index i + 1, but because we use the lcp array to detect it, we also consider index i + 2 as part of the CT AT T -interval.

To resolve this special case, the recursion continues even when the current interval was not moved. In this case, it will never be necessary to move an interval, but maybe update some lcp values to set stop-points for future recursion calls. This is the reason for introducing the last parameter in algorithm 2 (the boolean flag move). It differentiates the normal case (when it is necessary to detect the destination index and move the interval) from the case in which the current interval is considered only to set a stop-point at the first index of the interval. The recursion continues in both cases.

Filtering non substituted R k occurrences

Among each vR k -interval, suffixes starting with vR k where R k is not substituted (whose position does not belong to O k ) may occur. The associated indices in the ESA DL should not be moved with the vR k -interval. Thus, before applying the recursive procedure previously exposed, a straightforward filtering step is applied. During the recursion, each line i of each group is first checked in order to detect if it corresponds to an index of a selected occurrence (sa[i] ⊕ depth ∈ O k ). Once a non-selected occurrence is detected, we move it to the beginning of the group (before i start ). As previously mentioned, this also involves modifications of the lcp In-Place Update of Suffix Array While Recoding Words 11 array for maintaining its consistency.

Update lcp values after the substitution of R k occurrences to a single character

The substitution of any occurrence of R k of length |R k | ≥ 2 by C k of length 1 involves the modification of the length of all common prefixes involving such an occurrence.

In the previous step, it was easy to update the lcp values of the limits of the intervals while they were moved. In this step, we update the lcp values of the internal position of the intervals.

For this, we traverse the left-context tree of R k . Contrary to the moving step, where it was possible to move one line several times, in this step we update each lcp index only once. To do this, we recalculate all the lcp values for the root (R kinterval) and use this information to update the lcp of the other intervals.

As a consequence of propositions 2 and 3, the lcp between two indices of the same interval-node is simply one plus the lcp between their successor indices belonging to the parent interval-node:

Let i, j belong to the same aw-interval and let us assume that i > j.

Then lcp(s[sa[i]..], s[sa[j]..]) = min ∈[next[successor(i)],successor(j)] lcp[ ]

With this inductive approach, it is sufficient to re-calculate the lcp of only the first interval (the root of the left-context tree). This is straightforward (see algorithm 4).

Algorithm 4 Calculate the value of the lcp for index i recalculate lcp{ESA DL , i}

1: lcp[i] ← 0 2: if prev[i] ≥ 0 then 3: i ← sa[i] 4: j ← sa[prev[i]] 5: while i < n ∧ j < n ∧ s[i] = s[j] do 6: i ← i ⊕ 1 7: j ← j ⊕ 1 8: lcp[i] ← lcp[i] + 1 9:
end while 10: end if During the iterative call, if an index that is already treated appears, it is skipped. Indeed, its lcp value is then up-to-date. The pseudo-code for this step is exposed in algorithm 5.

Because in each step we use the value of all the lines of the previous group, we traverse once again the left context tree in a breadth-first order.

Algorithm 5 Update lcp of step k update lcp{ESA (k) DL , R k , O k } 1: q ← queue() 2: for i ∈ O k do 3: recalculate lcp(ESA (k) DL , isa[i]) 4:
q.push ((predecessor(isa[i]), 1)) 5: end for 6: while not q.empty() do 7:

(i, depth) ← q.top 8:

q.pop 9:

if i ≥ 0 ∧ lcp[i] not already updated ∧ lcp[i] ≥ depth then 10: lcp[i] ← (min j∈[next[successor(prev[i])],successor(i)] lcp[j]) + 1 11:
q.push((predecessor(i), depth + 1))

12:

end if 13: end while

Efficiency

The space complexity is O(n). The ESA DL structure needs to complete the ESA with two arrays of length n. During the execution, a queue of length O(n), and an array of length n are used to check in constant time whether a couple (i, depth) was already used.

The worst case time complexity of the update algorithm is bounded by O(n 2 ). This case is reached while replacing for instance AA occurrences in an ESA DL indexing the text A n T . A better bound on time complexity could be obtained by considering amortized complexity, but it will still be unlikely to be better than the O(n) complexity required for building the suffix array from scratch. Nevertheless, the algorithms building suffix arrays that currently perform best in practical cases, are not the linear ones (see [START_REF] Schürmann | An incomplex algorithm for fast suffix array construction[END_REF] for a description of the different suffix array construction algorithms and their strengths). We propose in this section to evaluate the practical efficiency of our update algorithm, comparing it to the standard approach that recreate the suffix array.

A prototype implementing the proposed algorithm has been developed using the C++ language. It is available at http://www.irisa.fr/symbiose/mgalle/suffix array update . It has been tested on different types of text. For the sake of brevity, in this paper we only report the results on the following classical corpora from the literature:

• the standard and large Canterbury corpus (http://corpus.canterbury.ac.nz/ [START_REF] Arnold | A corpus for the evaluation of lossless compression algorithms[END_REF]), • the Purdue corpus (http://www.cs.ucr.edu/ stelo/Offline/ [START_REF] Apostolico | Compression of biological sequences by greedy offline textual substitution[END_REF])

In-Place Update of Suffix Array While Recoding Words 13

Results on other corpora can be found on our internet site.

To compare the execution time with a recreating from scratch approach, we took three different suffix array creation algorithms: the linear time one proposed by Kärkkäinen and Sanders [START_REF] Kärkkäinen | Simple linear work suffix array construction[END_REF], the non-linear algorithm of Larsson and Sadakane [START_REF] Larsson | Faster suffix sorting[END_REF] and the Induced Sorting algorithm of Zhang, Nong and Chan [START_REF] Zhang | Fast and space efficient linear suffix array construction[END_REF] (again a linear one). The source code of the first two were retrieved from the Internet sites specified in the associated articles. Note that Kärkkäinen and Sanders' code "strives for conciseness rather than for speed" [START_REF] Kärkkäinen | Simple linear work suffix array construction[END_REF]. For the Induced Sorting algorithm, we used the optimized implementation of Mori [START_REF] Mori | An implementation of the induced sorting algorithm[END_REF].

In the last years, suffix array creation algorithms has proven to be a rich field of research. New strategies and improvements are proposed each year, and for a complete taxonomy of the state of art we refer to [START_REF] Puglisi | A taxonomy of suffix array construction algorithms[END_REF]. But some of them do assumptions over the alphabet that could no be fulfilled by our grammar based application:

(1) the size of the alphabet. Manzini and Ferragina's algorithm [START_REF] Manzini | Engineering a lightweight suffix array construction algorithm[END_REF] and Yuta Mori's libdivsufsort [START_REF] Mori | libdivsufsort[END_REF] suppose a size of alphabet less than 256. In our approach, in each iteration we introduce a new non-terminal, so this bound is too tight. (2) it is possible that, after a replacement, a letter does not occur any more in the sequence because all its occurrence where inside the selected repeat. That is because we discarded algorithms that suppose a contiguous alphabet (like [START_REF] Maniscalco | An efficient, versatile approach to suffix sorting[END_REF]).

The tests were executed on 1GHz AMD Opteron processors with 4Gb of memory.

First, to have an idea of the complexity of the algorithm, we studied how the length of the sequence influences the execution time of the algorithm. From the large Calgary corpus, we extracted sequences of different lengths by considering successively bigger (by steps of 100 characters) prefixes of the sequences. On each extracted sequence, we performed 250 iterations of selecting a random repeat, replacing it over the sequence by a new character and updating the associated suffix array. Time (user + system time) required for updating the suffix array was reported, averaged over 5 different runs corresponding to 5 different random seeds. The same experiments, replacing the update algorithm by the "from scratch" construction algorithms of the suffix array by Kärkkäinen and Sanders (K & S), Larsson and Sadakane (L & S) and Zhang, Nong and Chan (ISA) have been performed. The plots, shown in figure 3, confirm that the execution time of our updating algorithm is not directly correlated to the length of the sequence, and is significantly smaller than the execution time required by reconstruction "from scratch" algorithms, especially when the length of the sequence increases.

We present a more exhaustive evaluation and comparison on all the corpora using different strategies for the selection of the repeated word. In each test we performed 500 iterations of selecting a repeat, replacing it over the sequence and updating (or building from scratch) the associated suffix array. The different strategies for the selection of the repeat were:

• take a random one (using the same seed for the random number generator),

• take the longest, • take the one that covers the maximal number of positions a .

Information over these files are summarized in figure 4. Results are given in figure 5 (page 18). For each selection strategy, we measured time (user + system time) spent in updating ESA DL with our algorithm (column update), and time spent in building ESA from scratch at each iteration with the three creation algorithms. For easier comparison, we only report the times given by the update algorithm and the ratios of the time spent by each of the three "from scratch" algorithms over the update algorithm. A ratio lower than 1 means that the from scratch algorithm was faster than the update. Time spent by a from scratch algorithm can be obtained by multiplying the time reported in the "update" column by the respective ratio. Some of the files (notably fields.c, grammar.lsp and xargs.1) are too small to draw significant conclusions, but results are shown here for the sake of completeness. On the other files, results show that a significant speedup is usually achieved by using our algorithm. The main exceptions are the Spor All 2x.f asta file (an artificial file obtained by concatenating Spor All.f asta with itself) from the Purdue corpus, and the ptt5 file from the Canterbury corpus (a fax image with very long zones of the same byte). One can also remark that the ratio is less favorable when the repeat to replace is chosen according to the maximal compression strategy. On the one hand, in each iteration the resulting sequence is smaller and the suffix array creation from scratch for this sequence faster. On the other hand, there are more positions affected by the substitution and this affects the update algorithm.

These cases allow us to illustrate an intrinsic limit of the update approach when the length of the sequence is highly reduced by recoding: when the number of positions to update is larger than the number of positions in the resulting sequence, it may be worth adopting the "from scratch" construction algorithm (let us remark that the best algorithm to use can vary along the iterations). A solution to handle these extreme cases, would be to design a criterion on the repeat and its coverage to automatically choose the best algorithm to use (eventually at each iteration).

Conclusion and future work

We introduced in this paper an approach allowing to update an enhanced suffix array while substituting some of the occurrences of a word in the indexed text We did not consider singular insertions or deletions, but simultaneuos substitution.This is of particular interest for grammatical inference or grammar based compression methods which use these data structures and are iteratively performing a large number of such substitutions.

a choose at each step the repeat that maximize (|O k | -1) * (|w| -1) -2, which actually corresponds to a maximal compression approach [START_REF] Nevill-Manning | On-line and off-line heuristics for inferring hierarchies of repetitions in sequences[END_REF] In-Place Update of Suffix Array While Recoding Words 15

Our approach uses the specific internal order of suffix arrays to simultaneously update groups of adjacent indices and ensures that only indices to be modified are visited. This specific property of the suffix arrays allows to design an efficient update procedure which has been implemented and tested on classical corpora. The experimentation confirms that, in regard to the direct method reconstructing the suffix array, our approach enables significant speed-up of the execution time of a factor up to 70 when choosing randomly a repeat to replace.

The time complexity of the new algorithm depends mainly of the size of the left context tree. This grows with both the average lcp of the sequence, and the number of positions the chosen repeat covers. In some cases -specially when these two factors are big -, the update method is less efficient than building the enhanced suffix array from scratch. Intuitively, when the number of lines to change is larger than the number of lines in the new suffix array, a reconstruction algorithm is likely to be more efficient than an update approach. In order to be even more efficient, a criterion allowing to decide automatically which algorithm to use could be designed. This would require a finer complexity analysis of the update algorithm, but also of the chosen building algorithm, in order to identify easy-to-compute key parameters involved in the execution time complexity.

Of course, the question of the existence of a practical efficient O(n) algorithm remains open. But the results on the construction of suffix arrays suggest that a better way of improvement could be the design of other practical update algorithms. Finally, these results have been obtained by using a suffix array. It would be interesting to study how easily this approach can be adapted to suffix trees and how much it depends on the properties specific to suffix arrays.

In-Place Update of Suffix Array While Recoding Words 17

Fig. 1 .

 1 Fig. 1. Deletion of index j.

Algorithm 1

 1 In-Place Update of Suffix Array While Recoding Words 7 Delete indices at step k, replacing R k by C k delete indices{ESA

  detects the end position of the v-interval, (3) if necessary: 3.a. moves the group to the end position of the v-interval, 3.b. call the recursion on predecessors of indices of the group.

9 Fig. 2 .

 92 Fig. 2. Moves induced by substituting GA by C 1 .

Fig. 3 .Fig. 4 .

 34 Fig. 3. Large corpus: bible.txt, world192.txt and E.coli. Times are given in hundredth of seconds and the size in thousands of characters bible.txt

  i] (resp. prev[i]) gives the index of the next (resp. previous) valid entry in the ESA. Initially, next[i] = i + 1 and prev[i + 1] = i. We call the set ESA plus next and prev arrays the ESA DL for Double Linked Enhanced Suffix Array.

  , move} 1: if Couple (i start , depth) already treated during another recursion call then

	2:

  Move the group [i start , i end ] after the position i dest

	10 Gallé, Peterlongo and Coste
	Algorithm 3 move group{ESA

  The files from the purdue corpus contains comments in fasta notation, but most of the sequences are composed only of 4 symbolsIn-Place Update of Suffix Array While RecodingWords 19 Fig. 5. Comparison between update and reconstruction from scratch of the suffix array. Times are given in hundredth of seconds. A ratio lower than 1 means that the from scratch algorithm was faster than the update algorithm

		ISA	ratio	2.61	2.88	2.83	5	div 0	1.5	3.97	4.49	0.28	2.18	7		5.41	3.4	5.8		2.66	1.74	1.61	2.95	0.25	1.22	4.92	1.27	1.62
	file CANTERBURY CORPUS alice29.txt asyoulik.txt cp.html fields.c grammar.lsp kennedy.xls lcet10.txt plrabn12.txt ptt5 maximal compression time ratio 269 4.06 182 4.76 18 3.06 update K & S L & S ratio 1.9 2.23 2.22	3 6 2	size (number of symbols) average lcp alphabet size 152089 7.76 74 125179 6.61 68 24603 12.47 86 11150 12.67 90 3721 8.63 76 1029744 7.56 256 426754 10.32 84 481861 7.12 81 513216 2353.31 159 0 div 0 1541 3.16 749 7.76 887 8.84 1900 0.44 28 2.93 2 2 10285 15.37 14808 9.51 5573 16.28 2350 6 884 3.12 165 2.32 19 2.89 61 0.57 413 1.88 25 2.24 33 1.82 73 1.6 div 0 1.08 3.02 3.28 0.19 1.71 1 3.7 2.11 4.54 1.77 1.28 1.16 2.63 1.16 0.97 1.88 1.18 0.9
	sum xargs.1 LARGE CORPUS ISA ratio	7.45	8.69	5	3.88	38240 4227 div 0 10.87 14.01	16.26	3.41	4	4		21.96	21.8	21.2	51.31 5.35 19.34 13.88	7.11	5.65	0.26	255 74 8.25 8.27	10.2	5.85
	bible.txt E.coli world192.txt PURDUE CORPUS All Up 1M.fasta All Up 400k.fasta Helden All.fasta Helden CGN.fasta Spor All 2x.fasta Spor All.fasta maximal length time ratio 192 12.28 update K & S L & S ratio 7.14	127 13.6 8.34	15 6.4 4.27	8 2.38 2.63	4047392 4638690 2473400 1001002 399615 112507 32871 444906 222453 0 div 0 1230 29.24 522 31.51 div 0 11.22 12.35	606 31.84 15.35	696 7.65 5.32	34 5.5 2.91	2 3 1		5168 64.39 22.5	6307 53.46 24.03	3089 60.7 21.11	13.97 17.38 23.0 18.75 15.32 20.84 7.2 56022.6 818.061 1200 46.16 481 27.64 122 11.17 19.99 13.93 7.65	34 6.82 5.24	57 0.6 0.77	63 4 94 46 46 61 51 54 54 250 13.26 26 8.46 8.56 7.31	15 11.07 8.07	62 8.16 6.39
	Spor EarlyI.fasta					31039									7.12				49
	Spor EarlyII.fasta Spor Middle.fasta ISA ratio	9.47	8.78	6.6	6.17	25008 54325 3 9.73 6.07	19.42	4.81	3.9	4.83		22.8	26.59	22.12	6.94 7.57 19.03 13.88	7.51	4.87	0.5	46 51 8.29 4.76	7.9	6.78
	Note: random	update K & S L & S	time ratio ratio	163 17.25 9.18	131 16.11 8.47	15 8.8 6.33	6 6.33 5.17	3 1.67 1.67	1323 26.38 9.7	1248 5.92 3.7	516 33.24 13.32	588 38.53 15.06	42 5.57 3.6	6 4.17 1.5		5055 66.81 22.84	5534 69.14 27.36	3084 65.06 21.75		1238 49.8 19.87	501 27.86 13.53	119 12.7 8.09	31 7.87 5.55	112 0.73 0.84	246 14.87 8.57	34 5.5 4.47	20 7.25 7.55	51 10.31 6.88
			CANTERBURY	alice29.txt	asyoulik.txt	cp.html	fields.c	grammar.lsp	kennedy.xls	lcet10.txt	plrabn12.txt	ptt5	sum	xargs.1	LARGE	bible.txt	E.coli	world192.txt	PURDUE	All Up 1M.fasta	All Up 400k.fasta	Helden All.fasta	Helden CGN.fasta	Spor All 2x.fasta	Spor All.fasta	Spor EarlyI.fasta	Spor EarlyII.fasta	Spor Middle.fasta

Gallé, Peterlongo and Coste

Gallé, Peterlongo and Coste


Anh-Tuan Gai
email: anh-tuan.gai@inria.fr

Laurent Viennot
email: laurent.viennot@inria.fr

Optimizing and Balancing Load in Fully Distributed P2P File Sharing Systems (Scalable and Efficient Keyword Searching)

A peer-to-peer file sharing system includes a lookup and a content distribution protocol. Very efficient peer-to-peer protocols exist for content distribution, but efficient indexing is still an open problem. Numerous work on structured overlay networks such as distributed hash tables offer a promising framework. However, balancing the load of publishing, storing indexes and answering request still remains a challenging task. We sketch a general architecture framework for solving these problems in the case of a file sharing application. Our design goals include reducing the work of file providers (they should not bare all the publishing process) and enabling keyword searching based on the assumption that few words are associated with each file.

Introduction

Peer-to-peer file sharing system [9,4,[START_REF] Fessant | Mldonkey, a multi-network peer-to-peer file-sharing program[END_REF][START_REF] Cohen | Incentives build robustness in bittorrent[END_REF] has become an attractive alternative to client-server content distribution. Instead of uploading data from a unique source, the upload cost is redistributed among peers. Before downloading, the first problem to solve while searching a data is to identify precisely the data we are interested in and then to find peers sharing it. In this paper we are particularly concerned with fully distributed file sharing systems. In such environments, the participants give some of its resources in exchange for using the service. They would thus naturally expect a workload proportional to their use of the service. In particular, we cannot expect some of the peers to bear the load of a dedicated server.

Unfortunately, conventional lookup protocols are inherently not well matched to a fully distributed environment. In flooding based lookup protocols, the workload is not optimized since the systems may not return addresses of peers sharing a file until the whole network has been explored. In routing based solutions, such as distributed hash tables (DHT), few messages are exchanged but some nodes responsible for widely spread words may have to store many associations and to answer many requests. This conflicts with the expectation that all members should share the workload.

Distribution systems such as eDonkey [4] release on powerful servers. If some node play the role of these powerful servers this conflicts with the expectation that all member should share the tracking load.

We introduce a general framework which enables efficient keyword searching. We propose solutions to optimize the associations storage load and distribute it among participating nodes. Moreover, we distribute among interested nodes the association lists upload cost.

The key idea is to combine a resilient DHT and an efficient distribution protocol such as BitTorrent [START_REF] Cohen | Incentives build robustness in bittorrent[END_REF] both for lookup and distribution. We use the distribution protocol to redistribute the load of large association lists. We use the lookup protocol to find trackers that help users downloading the same file meeting each other. The key challenge is to efficiently redistribute the lookup workload, and the workload of tracking a file, among peers sharing interest.

The rest of this paper is organized as follows. A brief description of BitTorrent, and a recall on distributed hash tables (DHT) and bloom filters is given in Section 2. We introduce solutions to redistribute and optimize the publishing load, the storage load and the request load in Sections 3, 4 and 5 . Section 6 describes related work and Section 7 concludes.

Background

Distributed Hash Tables

Distributed hash tables (DHTs) are a class of decentralized distributed systems which partition ownership of a set of keys among participating nodes; they can efficiently route messages to owners of any given key. Each node is responsible for a part of a hash table. DHTs are typically designed to scale to a large number of nodes and to handle continual node arrivals and failures. This infrastructure can be used to build more complex services, such as distributed file systems, peer-to-peer file sharing systems, cooperative web caching, multicast, anycast, and domain name services. Many DHTs have been recently proposed.

BitTorrent

BitTorrent [START_REF] Cohen | Incentives build robustness in bittorrent[END_REF] has quickly become one of the most used peer-to-peer file-sharing system in terms of traffic. When a file is made available using HTTP, all upload cost is placed on the hosting machine. With BitTorrent, when multiple people are downloading the same file at the same time, they upload pieces of the file to each other. This redistributes the cost of upload to downloaders, thus making hosting a file with a potentially unlimited number of downloaders affordable. BitTorrent is different from other peer-to-peer systems because it does not include any lookup protocol. Downloaders find ".torrent" files on websites using any search engine like Google or dedicated websites. ".torrent" files are small metadata files containing information about length, name, hashing information and tracker of a given file. Trackers are responsible for helping the torrent downloaders finding each other (files downloaded via BitTorrent are called torrents). The latest version of BitTorrent also includes a DHT in case of tracker failure. Since peers downloading a file have already retrieved the unique file ID from the ".torrent", a node responsible for the file ID may replace the tracker.

Bloom filters

A bloom filter [START_REF] Broder | Networks applications of bloom filters: A survey[END_REF] is a hashed-based data structure that summarizes membership in a set. More precisely, a bloom filter is an array of bits initially all equal to 0. To encode a set, each element is hashed by the same set of functions. When an element is hashed, the result correspond to a bit position of the bloom filter which is changed to 1. The membership test consist in hashing with the same hash functions set an element. If all resulting bit are equal to 1 in the bloom filter the test is positive. Nevertheless, the membership test returns false positives with a tunable, predictable probability and never forgets true members. Given optimal choice of hash functions number, the probability of a false positive is p f p = .6185 s/e where s is Bloom filter's size in bits and e is the number of elements in the set. Thus, to maintain a fixed probability of false positives, the size of the Bloom filter must be proportional to the number of elements represented.

Associations

In all peer-to-peer file sharing systems, some information about files and peers are distributed among participating nodes. These informations are necessary to enable efficient keyword searching. For a given keyword all systems should return files containing the keyword in the file name or in the file descriptors (author, album, or year for example). Then for a given file all systems should return addresses of peers sharing and downloading it. We thus distinguish two associations classes: keyword and file. A keyword association associates a keyword (or it's ID) to a file ID. A file association associates a file ID to addresses of peers downloading the file. Furthermore, we propose that both associations contain the file name and the descriptor list (see Sections 3 and 4 for more details).

Publishing Load

Less than 10 percents of peers share the majority of files available in file sharing systems and 70 percents of peers do not share files [START_REF] Saroiu | A measurement study of peer-to-peer file sharing systems[END_REF]. Moreover, the few percents of generous nodes share more than 1000 files each. In conventional routing based systems, a node publishing a file performs a lookup for each keyword of each file it publishes. A node sharing files will thus performs F * D lookups, where F is the number of file it shares and d the average number of keywords per file. Ideally, a peer-to-peer file sharing system should give incentive to share files and should redistribute the publishing load among peers. To redistribute the publishing load, we now introduce the 2-levels publishing scheme.

2-levels publishing scheme

Similarly to associations classes, we distinguish two publication classes: file and keyword. Like in conventional publishing scheme, in the 2-levels publishing scheme a node sharing a file is responsible for the file association publication (file info associated to the sharing node address). On the other hand, to redistribute the keyword association publishing load, the nodes responsible for the file association are responsible for keyword associations publications (file info associated to the file ID). A node sharing a file thus needs only one lookup to publish it and keyword publications cost is redistributed over the system since the files IDs are themselves balanced. Figure 1 illustrates the distribution of words contained in the file name over one million of distinct eDonkey files. The average number of words per file is 5, and less than 1 percent of the files contain more than 25 words.

Using 2-levels publishing scheme also optimizes the publishing traffic. If a has been already published, nodes responsible for the file ID do not republish keyword associations each time a node publishes an association for this file. Notice that the distribution of copies per file may be unbalanced and thus nodes responsible for a spread file ID will significatively reduce their keyword publishing load. In the whole system, the number of lookups for keyword publicais thus divided by C, where C is the average number of copies per file in the system. Furthermore, to optimize the republishing load, a node sharing a file does not republish the file association, it is regularly contacted by nodes responsible for the file ID. It thus replies to a ping instead of performing a lookup. Similarly, nodes responsible for keyword associations regularly contact nodes responsible for the file ID. Finally, if the node sharing a file (resp. responsible for the file ID) is not contacted by nodes responsible for the file association (resp. keyword association) after a given timeout period, it republishes the file association (resp. keyword association). Using 2-levels publishing scheme together with pings, the F * C * D lookups in conventional system per republishing time period, are replaced by F * C + F * D pings, where F is the number of distinct files and D is the average number of keyword per file in the system.

Associations Storage Load

Key collisions introduced by widely spread keywords ("mp3" for example) requires some balancing mechanisms. Otherwise, a node responsible for a widely spread keyword will be overloaded in storage capacity (key collision hotspot) and in bandwidth capacity (request hotspot). Figure 2 illustrates the keyword occurrences distribution over two millions eDonkey files.

Figure 2. keywords ranked by number of occurences

In conventional routing based systems, associations are stored on the k closest nodes to a given ID. Let l be the maximum number of associations a node stores for a given keyword. If a keyword appears in more than l associations, we would like to redistribute the storage load among participating nodes. The main challenge is to find a rule to ensure that each association is stored by O(k) nodes. Ideally, we also would like these nodes to be close (in number of hops) to the original ID.

Mixed Hashing

Similarly to double hashing, in case of key collisions, the system must provides an alternative ID to store associations. The key idea is to store keyword associations of spread keywords on peers close to a mix of most of the keyword ID digits and some of the file ID digits. If the nodes responsible for a spread keyword ID v already store l associations, further associations will be stored on nodes responsible for ID u composed with one digit of the associated file ID and digits of the keyword ID. Then, if the nodes responsible for u also store more than l associations for v, further associations will be stored on nodes close to ID composed with two digits of the associated file and digits of the keyword ID, and so on... If the mixed ID is well constructed, retrieving nodes storing associations consists in pushing further ahead the lookup (instead of performing another lookup). Moreover, using bi-directional protocols such as Broose [START_REF] Gai | Broose: A practical distributed hashtable based on the de-bruijn topology[END_REF], nodes storing associations may be on the routing path to the word ID (in Broose, associations should be stored on nodes close in number of hops to the keyword ID using right-shifting and lookups for request should use left-shifting1 ). Notice that finding associations on the routing path may be useful to redistribute the request load (see section 5 for more details).

Smaller Keyword Associations

Another challenge is to optimize association size. If a keyword association is reduced to the couple {word ID, file ID}, it's size is typically 320 bits (2 SHA-1 160 bits identifiers). To obtain smaller list, the file ID can be reduced to the first 40 or 50 bits. In a system with less than 2 30 users, the k closest node to the real file ID is are not the k closest node to the ID composed with the first 50 file ID bits completed with 0, with probability less than k 2 50-30 . Association storage for keyword u is reduced to (160 + 50 m) bits instead of (160 + 160 m) bits, where m is the number of associations for u. When m is large, the keyword association storage can thus be reduced by a factor 3.2.

Request load

Some association lists of spread keywords contain more than one million associations (see Figure 2). Using mixed hashing introduced in Section 4 redistributes the storage load of large associations list. Nevertheless, nodes responsible for frequently requested list will be overloaded in download by requests and in upload by association list distribution. Similarly, nodes responsible for meta-info files (".torrent") distribution will be overloaded if the associated file is frequently requested or if the ".torrent" is large. The main breakthrough of BitTorrent is to redistribute the file upload cost among peers sharing or downloading a file. We propose to use a protocol similar to BitTorrent to redistribute the association list and the meta-info file (".torrent") load. Moreover, we optimize the size of association list returned to save network bandwidth.

Request Hotspot

We propose to use a solution similar to the the solution introduced in Kademlia [START_REF] Maymounkov | Kademlia: A peer-to-peer information system based on the xor metric[END_REF] to alleviate request hotspots. To redistribute the load of receiving request, answers should be cached on nodes likely to be on the path of further requests for the same ID such that nodes close to the requested ID are not overloaded by receiving request. To avoid over caching, associations are cached during a period of time exponentially inversely proportional to the number of hops between the current node and the node responsible for the key.

A complementary solution consists in distributing all these informations for frequently requested files or keywords associations list by all peers in the system or all peers sharing same interest (publish-subscribe) using a protocol similar to BitTorrent. We propose to introduce a global torrent of very requested file and keyword IDs. When a node is overloaded for a given file or keyword ID, it adds it to the global torrent and shares a new bloc containing informations it is frequently requested for.

Associations list Upload Cost

We would like to redistribute a large requested list upload cost among peers downloading it by sharing it. If many nodes want the same large association list they should retrieve it in a cooperative way and thus use a distribution protocol such as BitTorrent. When a peer looks for files relevant for a given keyword, it performs a lookup over the keyword ID. If the nodes responsible for the keyword ID are not overloaded, they act as trackers and as seeds for the keyword association list. If the nodes responsible for a given keyword u are overloaded, nodes storing associations for u act as trackers for the whole list and as seeds for a bloc of the association list. Furthermore, nodes on the routing path to u cache addresses of peers interested by the association list and thus also act as tracker. However, to enhance connectivity and to redistribute the tracking load, peers downloading the association list exchange their contact list.

Furthermore, If a keyword is widely spread and frequently asked by a peer, this peer should store the corresponding association list and regularly update it. Adding the first publication date to an association enables a peer to ask only for association published after it's last update. Moreover, since this peer has already many associations it will act as seed for old associations.

Smaller Association Lists Uploaded

In this section we introduce solutions to optimize the traffic generated by the association list upload cost. If word associations only contain a word ID associated to a file ID, a node has to retrieve the association list for each words appearing in the request before it can choose a file in the lists intersection. Since bandwidth is the most expensive resource (compared to storage), we propose to add the filename and the file info (author, byterate, year, etc...) to the keyword association. When a node is looking for files relevant for several keywords, it only performs one lookup for one of the keyword (preferentially the rarest). Nodes responsible for the word ID only return associations where all requested keywords appear. The global torrent described in Section 5.1, may be useful to learn which words are widely spread.

Including file descriptions induces both storage and bandwidth overheads for keyword associations. We now introduce another solution to optimize the size of keyword association. For each file, a Bloom filter over its words is computed. Recall a Bloom filter is a hashed-based data structure that summarizes membership in a set. This Bloom filter replace the filename and the file infos of word associations. With a 20 bits per keyword Bloom filter the probability of false positive is less than 10 -4 instead of 80 bits for a 10 characters keyword. This can reduce the keyword list size by a factor approximately 4.

Reynolds and Vahdat [START_REF] Reynolds | Efficient peer-to-peer keyword searching[END_REF] have shown that more than 70% of requests contain two or more keywords. Another solution to reduce the size of associations list returned to requests could be the following. Nodes responsible for a file ID, also publish associations of keyword couple {keyword ID, keyword ID, file ID}. The storage load would also be O(F * D 2 ) but with O(F * D 2 ) publish lookups instead of O(F * D) with the previous solution proposed.

Hashes Distribution

To download a file with BitTorrent the client needs the ".torrent" file. Some recent studies [START_REF] Felber | Self-scaling networks for content distribution[END_REF] have shown that the download is faster and fairer if the file is divided into small chunks (to enhance exchanges). Having many chunks implies having many hashes and thus a big ".torrent" file. In centralized systems, powerful users upload the ".torrent" files from servers.

To redistribute the upload cost of the ".torrent" to downloaders, we introduce the ".metatorrent" file (".torrent" of the ".torrent"). The trackers (nodes responsible for the file ID) store the ".metatorrent" file. A ".metatorrent" is simply a ".torrent" of the ".torrent". It contains all information necessary to start downloading the ".torrent" and the file. More precisely it contains the ID of the desired file, the size of the ".torrent", the size of the file, the size of chunks, and the hashes of the ".torrent" chunks. To start downloading the file quickly, BitTorrent verification procedure should be modified. A client can download file chunks even if it does not have the hashes of these chunks. With the size of the file and the size of a file chunk contained in the ".metatorrent" the node can already ask for and download some file chunks. The file chunks verifications with hashes are performed when the ".torrent" downloaded has been verified with the hashes contained in the ".metatorrent".

Related Works

Many routing based peer-to-peer systems have been proposed recently, e.g. [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF][START_REF] Rowstron | Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems[END_REF][START_REF] Naor | Novel architectures for p2p applications: the continuous-discrete approach[END_REF][START_REF] Kaashoek | Koorde: A simple degreeoptimal distributed hash table[END_REF][START_REF] Fraigniaud | The content-addressable network d2b[END_REF][START_REF] Abraham | A generic scheme for building overlay networks in adversial scenarios[END_REF][START_REF] Maymounkov | Kademlia: A peer-to-peer information system based on the xor metric[END_REF][START_REF] Gai | Broose: A practical distributed hashtable based on the de-bruijn topology[END_REF][START_REF] Cohen | Incentives build robustness in bittorrent[END_REF].

Several systems based on DHT enable to find the closest nodes to a given ID [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF][START_REF] Rowstron | Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems[END_REF][START_REF] Naor | Novel architectures for p2p applications: the continuous-discrete approach[END_REF][START_REF] Kaashoek | Koorde: A simple degreeoptimal distributed hash table[END_REF][START_REF] Fraigniaud | The content-addressable network d2b[END_REF][START_REF] Abraham | A generic scheme for building overlay networks in adversial scenarios[END_REF][START_REF] Maymounkov | Kademlia: A peer-to-peer information system based on the xor metric[END_REF][START_REF] Gai | Broose: A practical distributed hashtable based on the de-bruijn topology[END_REF]. Chord [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF], Pastry [START_REF] Rowstron | Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems[END_REF] and first generation De Bruijn graph based DHT [START_REF] Naor | Novel architectures for p2p applications: the continuous-discrete approach[END_REF][START_REF] Kaashoek | Koorde: A simple degreeoptimal distributed hash table[END_REF][START_REF] Fraigniaud | The content-addressable network d2b[END_REF], 1] need a strict topology maintenance. This implies many messages exchanges and low resilience to node departures. Kademlia [START_REF] Maymounkov | Kademlia: A peer-to-peer information system based on the xor metric[END_REF] and Broose [START_REF] Gai | Broose: A practical distributed hashtable based on the de-bruijn topology[END_REF], are more resilient to node failure and churn but do not resolve the key collision hotspots.

BitTorrent [START_REF] Cohen | Incentives build robustness in bittorrent[END_REF] offers an efficient solution to file distribution but the content lifetime and availability rely on powerful servers. Moreover, in the solution presented the upload cost of the ".torrent" is redistributed among peers downloading the file.

A solution using Bloom filters over files membership [START_REF] Reynolds | Efficient peer-to-peer keyword searching[END_REF] is efficient when keywords appear in few associations. If keywords may appear in 10000 associations, the optimal size of Bloom filters is 10 KB. Figure 2 illustrates that some words like "mp3" have much more occurrences. Furthermore, in the solution introduced in [START_REF] Reynolds | Efficient peer-to-peer keyword searching[END_REF], nodes responsible for requested associations exchange messages to limit false positive associations returned. Thus, nodes responsible for many associations answer a lot of requests on the one hand and exchange messages to limit false positive on the other hand. However, we introduce a solution to optimize associations lists. Bloom filters computed over descriptor considerably reduce the descriptor association size and the upload associations lists cost can be distributed on peers interested in retrieving the list.

Conclusion

We have introduced a general framework for fully distributed file sharing system. The multi-level publication scheme introduced significatively reduces the publication traffic since keyword associations are published only once. Using pings instead of lookups reduces the republishing load by a factor O(log n). The mixed hashing scheme al-lows to redistribute the storage load on nodes close (in number of hops) to nodes responsible for the original ID. The solutions provided enable efficient keyword searching without any flooding mechanism and support inherent unbalanced associations distribution due to spread words. Using Bloom filters over keywords and smaller file ID allow to reduce the size of keyword association lists. Moreover, we are able to distribute the query load for spread keywords on peers interested by the corresponding keyword association lists. Finally, the solutions provided are designed for distributed hash tables but could be adapted to skip graph or other lookup protocols.

Figure 1 .

 1 Figure 1. distribution of number of words per file name

Table 1 . characteristics of some DHTs. k is the redundancy parameter, it represents the number of contacts a peer can choose at each lookup step.

 1 Table 1 represents the different characteristics of some DHTs. All DHTs usually follow the same framework: nodes maintain neighborhood links for safe routing and local republishing. Long links enable small graph diameter. The k nodes with IDs close to the file or word ID u for a given metric are responsible for u associations.

	protocol	topology	diameter	contacts	k
	Chord [16]	hypercube O(log n)	O(log n)	1
	Pastry [14]	hypercube O(log n)	O(log n)	1
	De-Bruijn	De Bruijn O(log n)	O(1)	1
	[12, 10, 7, 1]	graph
	Kademlia [11] hypercube O(log n) O(k log n) k
	Broose [8]	De Bruijn O(log n)	O(k)	k

In De Bruijn lookup based protocols, the contact list of node u contains nodes with prefix ID obtained by shifting u prefix address and inserting new digits.