Adrian Kosowski
email: kosowski@labri.fr.

Alfredo Navarra
email: navarra@dmi.unipg.it

Cristina M Pinotti
email: pinotti@dmi.unipg.it

Synchronous Black Hole Search in Directed Graphs

come

Introduction

The subject of exploring an unknown graph by means of mobile entities has been widely considered during the last years. The increasing interest to the problem comes from the variety of applications that it meets. In robotics, it might be very useful to let a robot or a team of robots exploring dangerous or impervious zones. In networking, software agents might automatically discover nodes of a network and perform updates and/or refuse their connections. In this paper we are interested in the exploration of a graph with faulty nodes, i.e. nodes that destroy any entering entity. Such nodes are called black holes, and the exploration of a graph in such kind of networks is usually referred as black hole search. In what follows, we refer to the mobile entities as robots. According to the assumed initial settings of the network, and the knowledge and the capabilities of the robots, many results have been provided. Pure exploration strategies, without dealing with black holes, have been widely addressed, see for instance [START_REF] Gąsieniec | Fast periodic graph exploration with constant memory[END_REF][START_REF] Kosowski | Graph Decomposition for Improving Memoryless Periodic Exploration[END_REF] and references therein. In this case, the requirement is usually to perform the exploration as fast as possible. When black holes are considered, along with the time (or equivalently the number of edge traversals) required for a full exploration, the main goal resides in minimizing the number of robots that may fall into some black hole. We will say that a team of robots solves the black hole search problem if, at the end of the exploration, all the edges which do not lead into a black hole are marked as safe edges, and at least one robot from the team survives.

Related work

Undirected graphs. The literature dealing with black hole search problems mainly refer to undirected graphs. In this context, a further distinction is made between synchronous and asynchronous systems.

Concerning asynchronous systems, the most general results for undirected graphs can be found in [START_REF] Dobrev | Searching for a black hole in arbitrary networks: optimal mobile agents protocols[END_REF] where the black hole search problem was considered in the presence of a single black hole without any limitation on the network topology. The authors showed that ∆ + 1 robots are sufficient to complete the exploration and require Θ(n 2 ) steps, with ∆ being the degree of the black hole, and n the size of the network.

In [START_REF] Dobrev | Mobile search for a black hole in an anonymous ring[END_REF], the attention was devoted to rings. The authors showed that 2 robots are enough in order to detect one black hole and they provided an algorithm which requires O(n log n) moves, where n is the dimension of the ring. This approach was generalized to arbitrary graphs in [START_REF] Dobrev | Searching for a black hole in arbitrary networks: optimal mobile agents protocols[END_REF], where it is shown that with complete topological knowledge of the input graph, only two robots suffice and require Θ(n log n) steps to locate the black hole.

The variant in which the robot entering the node cannot learn the link by which it has arrived was studied in [START_REF] Glaus | Locating a Black Hole without the Knowledge of Incoming Link[END_REF]. For this scenario, a bound of ∆ 2 +∆ 2 + 1 on the number of required robots was established and shown to be tight for some instances of the problem.

Other restrictions have also been considered, like the knowledge of a map in [START_REF] Dobrev | Improved bounds for optimal black hole search in a network with a map[END_REF] where the authors provided a strategy for locating one black hole by means of 2 robots in O(n + d log d) moves, where n is the size of the network and d its diameter. In [START_REF] Dobrev | Black hole Search in Common Interconnection Networks[END_REF], one black hole is optimally located by 2 robots in O(n) moves in the case when the input graph has size n and its topology is among hypercubes, cube-connected cycles, star graphs, wrapped butterflies, chordal rings, multidimensional meshes or tori of restricted diameter. Time optimal algorithms for black hole search on ring networks have been recently provided in [START_REF] Balamohan | Time Optimal Algorithms for Black Hole Search in Rings[END_REF].

Concerning synchronous systems, in [START_REF] Czyzowicz | Searching for a black hole in synchronous tree networks[END_REF], the exploration subject was restricted to black holes in tree topologies. The authors showed that 2 robots are enough to perform the exploration when only one black hole exists. They provided a 5 3approximation algorithm with respect to the required number of edge traversals. In [START_REF] Klasing | Approximation bounds for Black Hole Search problems[END_REF], the authors assume that the map is known and then show that the problem of locating one black hole by means of 2 synchronous robots is not polynomial time approximable within any constant factor less than 389 388 , and provide a 6-approximation algorithm. A slightly different problem was considered in [START_REF] Cooper | Locating and repairing faults in a network with mobile agents[END_REF] where the network admits many black holes and if a robot gets destroyed into one, then such a black hole disappears but not the underlying node.

Directed graphs. The additional property of having directed edges can only increase the difficulty of the problem as a robot which has traversed an edge, cannot in general come back directly by reversing its move. The first results concerning directed graphs have been recently published in [START_REF] Czyzowicz | Black Hole Search in Directed Graphs[END_REF]. The authors considered a setting where robots are associated with unique identifiers (IDs), they know the number of nodes n of the input directed graph G = (V, A), and they know the number ∆ of edges belonging to G leading to the black holes. If BH ⊂ V is the set of black holes in G, the induced subgraph G[V \ BH] is assumed to be strongly connected. Each node v ∈ V is associated with a so called whiteboard which is an available bounded memory (with size polynomial in n) accessible in a mutually exclusive way by the robots located at node v. The obtained results show a general case lower bound on the number of robots required in order to accomplish the black hole search. Theorem 1.1 ([4]). In both the asynchronous and synchronous models, 2 ∆ robots are sometimes required to solve the directed black hole search problem, for all ∆ ≥ 1.

Such a worst-case example is obtained, e.g., by considering a directed cycle on n-1 vertices (including the homebase), and connecting ∆ of these nodes by outgoing links to a single black hole vertex. Using a combination-lock argument, by induction it was shown [START_REF] Czyzowicz | Black Hole Search in Directed Graphs[END_REF] that in this graph any team of less than 2 ∆ robots may sometimes perish in the black hole, without any of the robots traversing the last link of the cycle which leads back to the home base.

In [START_REF] Czyzowicz | Black Hole Search in Directed Graphs[END_REF] it is also shown that 2∆ + 1 robots are enough for solving the problem on planar graphs with the planar embedding known by the robots, and 2∆ robots are needed in the worst case.

Our results

In this paper, we extend the results on directed graphs by also separately considering the synchronous and the asynchronous cases, i.e. when the robots share or not a common clock. Under the same settings of [START_REF] Czyzowicz | Black Hole Search in Directed Graphs[END_REF], for the synchronous case we provide a general strategy which requires O(∆ • 2 ∆ ) robots. This answers the main question posed in [START_REF] Czyzowicz | Black Hole Search in Directed Graphs[END_REF], i.e. whether some number of robots, expressed as a function of parameter ∆ only, is sufficient to detect black holes in directed graphs of arbitrarily large order n. We also provide a strategy for ∆ = 1 and ∆ = 2 which requires 2 and 4 robots, respectively. For the asynchronous case, we show that 2 robots are still sufficient when ∆ = 1, but for ∆ = 2 at least 5 robots are sometimes required.

The paper is organized as follows. In Section 2 we recall the most important assumptions regarding the directed black hole search problem, and introduce some further notation. In Section 3 we state the main positive results of the paper for synchronous robots, proving that O(∆ • 2 ∆ ) robots suffice to explore any graph, and 4 robots suffice when ∆ = 2. The results for asynchronous robots for ∆ = 1 and ∆ = 2 are given in Section 4. Section 5 contains some concluding remarks.

The model

We assume the same scenario as that introduced in [START_REF] Czyzowicz | Black Hole Search in Directed Graphs[END_REF]. The explored digraph G = (V, A) contains a distinguished node called the home base (hb) from which all the robots start the exploration, and a distinguished set of black holes BH ⊆ V \ {hb}. We remark that from the perspective of this work, setting the number of black holes equal to |BH| = 1 does not affect any of the stated results. It is assumed that the induced subgraph G[V \ BH] is strongly connected. The set of arcs leading into some black hole, BA = A ∩ ((V \ BH) × BH), is known as the set of black hole arcs. All robots know two parameters of the graph: its order n = |V |, and the total number of black hole arcs, ∆ = |BA|. We remark that this assumption of the model comes from [START_REF] Czyzowicz | Black Hole Search in Directed Graphs[END_REF]; the algorithm which we propose in Section 3 only makes use of these parameters to determine the number of released robots and the waiting time between two successive robots are released, and hence knowledge of an upper bound on n and ∆ is sufficient. A robot located at a node v has access to its own built-in memory, the whiteboard associated with the node, a global timer counting the steps of the algorithm, and a local labeling of the arcs leaving node v (called an assignment of port numbers), which can be used to select the next arc in the robot's traversal. Note that nodes do not have unique identifiers, although such identifiers can potentially be created by the robots exploring the graph.

For a node v of a directed (multi)graph H, the number of arcs entering v is denoted by indeg H (v), and the number of arcs exiting v is denoted by outdeg H (v).

Algorithm for the synchronous model

In this section we propose a strategy for solving the directed black hole search problem using O(∆ • 2 ∆ ) synchronous robots. The robots are released from the home base hb one-by-one, at regular intervals of n 4 time steps. The strategy is formulated in such a way as to guarantee that within n 4 steps, i.e., before the next robot is released, the currently active robot is destroyed in some black hole.

Throughout the algorithm, each node v maintains a label f (v) stored in its whiteboard. Let the subgraph

H f (v) of G consist of all nodes u ∈ V \ BH having f (u) = f (v), and all arcs (u 1 , u 2 ) ∈ A such that f (u 1 ) = f (u 2 ) = f (v) and (u 1 , u 2 )
has been visited by at least one robot. The procedure is defined in such a way that initially f (v) is unique for all visited nodes (the definition of f (v) for unvisited nodes is irrelevant), whereas throughout the computation each of the graphs H f (v) remains strongly connected. Moreover, for each node v, the structure of the graph H f (v) and its embedding in the ports of G is encoded on the whiteboard of v.

The procedure is divided into ∆ phases. The p-th phase,

1 ≤ p ≤ ∆ consists of (∆ + 2) • S p robot releases, where S p = ⌈2 ∆ • ( √ 3/2) p-1 ⌉.
The phase is divided into the following three parts, involving robots with essentially different behavior:

• First part: S p searching robots are released.

• Second part: in each of ∆ iterations, S p cycle detection robots are released, following along a slight modification of the paths used by the searching robots from the first part of the phase.

• Third part: S p cycle contraction robots are released.

After the ∆ phases have been completed, all non-blackhole nodes belong to the same strongly connected component H f (hb) , which is encoded on the whiteboards of all these nodes, thus describing all the safe links of the graph. The procedures followed by the searching, cycle detection, and cycle contraction robots are discussed in detail below.

Procedure for the first part of the phase. The procedure for each searching robot r is defined as follows. Directly before and directly after traversing an arc, the robot writes this information on the whiteboards of the starting node and of the end node of the arc, respectively, together with its unique ID and the number of the move in the robot's move sequence. The robot proceeds to make its next move as follows:

1. Let the robot be located at an arbitrary node of some graph H i . Then, the robot explores all nodes of H i , identifying all arcs of G which leave or enter these nodes and do not belong to H i . If there exists an outgoing arc (u 1 , v 1 ) which was used by some robot r ′ at time t 1 , and an incoming arc (v 2 , u 2 ) which was used by the same robot r ′ at some later time t 2 , where

u 1 , u 2 ∈ V (H i ) and v 1 , v 2 ∈ V (H i )
, then robot r proceeds to extend component H i by including in it all the nodes on the route (v 1 , . . . , v 2 ) used by the robot r ′ between times t 1 and t 2 . (Robot r ′ was either a previously released robot, or r ′ = r.) More precisely, robot r visits all the nodes of all the graphs H f (v) , with v ∈ (v 1 , . . . , v 2 ), setting their labels to f (v) := i, and updating the stored graphs H f (v) accordingly.

When the extension from

Step 1 can no longer be applied, the robot performs the next move as follows.

• If there exists an arc leaving H i which has never been visited by any robot, then the robot proceeds along this arc.

• Otherwise, the robot proceeds along the arc leaving H i which has not been used by any robot for the longest time.

Note that the actions performed in Step 1 will never lead the robot into a black hole, and do not lead it out of the current explored strongly connected component, whereas either of the actions performed in Step 2 can potentially destroy the robot or lead it into a node which does not belong to component H i .

The number of steps performed by a searching robot can be upper-bounded by n 4 . Indeed, the graph has less than n 2 arcs, and the discovery of each new arc by an agent may require a complete exploration of the current strongly connected component H i , which can be performed in at most n 2 /2 steps.

Procedure for the second and third parts of the phase. To avoid confusion, we will write f (2) and H

(2) i to denote the value of labels f and graphs H i throughout the second part of the phase (the cycle detection robots do not update the labels), and likewise f (3) and H

(3) i to denote these labels and graphs at the end of the whole phase (after releasing all the cycle contraction robots).

Looking at the labels f (2) and graphs H (2) , which are defined at the time of the destruction of the last searching robot, observe that each searching robot r can be seen as performing a traversal of some sequence of graphs (H

(2) f 1 , . . . , H (2)
f k ), where a graph H (2)
f i appears in the sequence if at least one of its nodes has been visited by robot r. This implies a natural precedence relation (≺) between graphs H

(2) f i and H

(2) f j , that is, we will write H

(2)

f i ≺ H (2)
f j if for some searching robot r, graph H

(2)

f i appears before graph H (2)
f j in the robot's sequence of visits; see Figure 1 for an illustration.

Relation ≺ does not have to be acyclic. The goal of the cycle detection robots is to detect cycles of length at most ∆ in the graph of relation ≺. To do this, we release the robots in such a way that after the l-th of the ∆ iterations in this phase, each node of graph H

(2) f j stores a list of all f i such that H

(2)

f i ≺ l H (2) f j , where (≺ l ) is the l-th power of relation (≺). With each graph H (2)
f i , we associate a precedence set P f i whose copies are stored in the whiteboards of all of the nodes of H

(2) f i , and initially P f i = ∅. In the l-th iteration, for each searching robot r, exactly one cycle detection robot r ′ will retrace the route of r. Robot r ′ is defined so as to visit all nodes of all graphs in the same order (H

(2) f 1 , . . . , H (2)
f k ) as robot r, with transitions between adjacent graphs H (2) f i performed using the same arcs as those visited by robot r (this can be achieved since robot r may be assumed to store the information about its next move on the whiteboards of the nodes it is passing through). Additionally, for each H

(2) f j , robot r ′ now appends to the contents of set P f j the contents of all sets P f i , for all i < j, and also adds to P f j the element f i , for all i < j; all the copies of set P f j stored in the nodes of H

(2) f j are updated accordingly. Clearly, we have H

(2)

f i ≺ l H (2)
f j if and only if f i ∈ P f j . For easier manipulation of data in the next part of the phase, the precedence sets should store additional information about the ID of the searching robots r inducing the respective precedence relations.

Finally, the goal of the cycle contraction robots is to contract into a single connected component all graphs H

(2) f i forming cycles of length at most ∆ in the precedence graph induced by relation (≺). The cycle contraction once again retraces the route of corresponding searching robots from r. Upon detecting a cycle of length at most ∆ in the precedence relation, i.e., f i ∈ P f i for some graph H

(2) f i , they follow the arcs of the directed cycle of G which induces this relation (the identifiers of these arcs should be stored in set P f i as auxiliary information). For all the nodes v of all the graphs H (2) f j encountered in this cycle, the robots then update their labels, setting the new value f (3) (v) = f i and constructing the new contracted component H

(3) f i accordingly. These labels and components are then used by the searching robots in the next phase of the algorithm.

We remark that in all three phases of the algorithm, the number of steps performed by a robot before it is destroyed in a black hole or it returns to the home base, can be upper-bounded by n 4 steps, hence the release times of successive robots can be scheduled in intervals of n 4 steps. Proof. The number of robots used by the algorithm can indeed be bounded as follows:

∆ p=1 (∆ + 2)S p = (∆ + 2) ∆ p=1 ⌈2 ∆ • ( √ 3/2) p-1 ⌉ ∈ O(∆ • 2 ∆ ).
We now show that our strategy solves all instances of the black hole search problem.

Let {v 1 , . . . , v D }, where D ≤ ∆, be the set of vertices from which it is possible to exit by a black hole arc. At any given time step, consider the set of labels {f (v 1 ), . . . , f (v D )} = {f 1 , f 2 , . . . , f d }, with 1 ≤ d ≤ D, and let δ i denote the number of black hole arcs exiting from nodes of H f i , with 1≤i≤d δ i = ∆. As in the case of the other parameters, we will use the notation d (2) , d (3)

, f (2) i , f (3)
i , and δ

(2) i , δ

(3) i to denote the respective values during the second part and at the end of the third part of the phase.

First, we will prove by induction that at the end of the p-th phase, 1 ≤ p < ∆, we have d (3) ≤ ∆p. The claim is clearly true for p = 0; we will show that in each subsequent phase, either the black hole search problem has already been successfully solved (i.e., d (2) = 1 and H

(2)

f 1 = G[V \ BH])
, or the value of d (3) decreases by at least 1 (i.e., some two components H f i and H f j are contracted into each other during the phase). Consider for a moment the situation during the second part of the phase, and define the directed multigraph (H, R), where the set of nodes is H = {s, H

f 1 , H (2) f 2 , . . . , H (2)
f d }, with s being a special source node, while arcs are defined as follows. For each searching robot r released in the current phase, we add one arc from node H

(2)

f i to H (2) f j if
f i , H (2)
f j } in between these two visits. For each robot r, we also add an arc from the special source node s to the first of the graphs H

(2) f i visited by the robots, containing the homebase hb. Note that indeg (H,R) (s) = 0, and outdeg (H,R) (s) = S p .

We consider the following cases. 3) is smaller than that of d (2) for the current phase, hence d (3) decreases with respect to the previous phase.

(b) Multigraph (H, R) is acyclic, and no contractions are performed (d (2) = d (3) ); we can then extend R to a linear order, simply writing f 1 < f 2 < . . . < f d ; each searching robot of the current phase visits some subsequence of graphs H

f i in ascending orders of labels. For each f i , consider the set of black hole arcs exiting the component H

(2) f i . If at the start of the current phase some of these arcs exited different strongly connected components H a , H b (which were contracted into one by some searching robot), then the inductive claim holds, since for the current phase the value of d (2) is less than that of d (3) at the end of the previous phase. Thus, w.l.o.g. we can assume that H

(2) f i is obtained from some component H f i , which is perhaps enlarged by searching robots, but has the same set of exiting black hole arcs as H

(2) f i , throughout the phase. With this assumption, we now proceed to show the following auxiliary lemma.

f 1 = G[V \ BH],
or for all i, 1 ≤ i ≤ d (2) , the following condition holds:

outdeg (H,R) H (2) f i ≥ indeg (H,R) H (2) f i δ i + 1
.

Proof of lemma.

Let i be arbitrarily chosen, and consider an arbitrary sequence of δ i + 1 searching robots r 1 , . . . , r δ i +1 which consecutively went through H

(2)

f i , ordered
by increasing release times. We will show that at least one of the robots did not use a black hole arc to leave H

(2)

f i . Let H f i (r j )
denote component H f i directly after the destruction of robot r j ; recall that we have

H f i (r 1 ) ⊆ H f i (r 2 ) ⊆ . . . ⊆ H f i (r δ i +1 ) ⊆ H (2)
f i , and each H f i (r j ) has the same set of black hole arcs as H

(2) f i . Suppose now, to the contrary, that each of the robots r j left H

(2) f i by a black hole arc; this means that each of these robots also left H f i (r j ) by a black hole arc; moreover, since preference is given to arcs which were not used for a longer time, each of the robots r 1 , . . . , r δ i will be destroyed by a different black hole arc. Consider now the robot r δ i +1 . By the strong connectivity property of graph G[V \BH], unless

H f i (r δ i +1 ) = G[V \BH],
there exists at least one arc e outgoing from H f i (r δ i +1 ) which is not a black hole arc. This arc could not have been visited by any robot r released between r 1 (inclusive) and r δ i +1 (exclusive). Indeed, r never returns to component H f i (r δ i +1 ) after leaving it by arc e (since otherwise arc e would have been included into H f i (r δ i +1 ) by robot r δ i +1 ), and since we have r ∈ {r 1 , . . . , r δ i } (because r visits

H f i (r δ i +1 ) ⊆ H (2)
f i ), one of the robots {r 1 , . . . , r δ i } would have not been destroyed by any black hole arc leading out of H f i (r δ i +1 ), a contradiction. Hence, robot r δ i +1 finally leaves component H f i (r δ i +1 ) by an arc which is not a black hole arc, so it must contribute to the out-degree of node H

(2)

f i in multigraph (H, R). Since the sequence of δ i + 1 consecutive robots going through H (2)
f i was arbitrarily chosen, the claim follows directly. Now, we make a simple structural claim which relies only on properties of directed acyclic multigraphs. Lemma 3.2. Let M be any directed acyclic multigraph having set of nodes {s, v 1 , v 2 , . . . , v d }, such that indeg(s) = 0, and for all v i , 1 ≤ i ≤ d, we have:

outdeg M (v i ) ≥ indeg M (v i ) δ i +1
. Then: outdeg M (s) < d i=1 (δ i + 1).

Proof of lemma. Without loss of generality, we may assume that (s, v 1 , v 2 , . . . , v d ) is a valid linear ordering of the vertices of M obtained by topological sorting of the vertices. Let m i , 1 ≤ i ≤ d, be the cardinality of the set of arcs of M having their starting point in a vertex from the set {s, v 1 , . . . , v i-1 } and their endpoint in the set {v i , . . . , v d }. We also put m d+1 = 0. Observe that by assumption indeg M (v i ) ≤ (δ i + 1) outdeg M (v i ) + δ i , and for all i,

1 ≤ i ≤ d, we have m i+1 ≥ outdeg M (v i ).
Hence:

m i = m i+1 + indeg M (v i ) -outdeg M (v i ) ≤ ≤ m i+1 + (δ i + 1) outdeg M (v i ) + δ i -outdeg M (v i ) = = m i+1 + δ i (outdeg M (v i ) + 1) ≤ m i+1 + δ i (m i+1 + 1) = (δ i + 1)(m i+1 + 1) -1.
From the above inequalities, we obtain by induction starting from i = d the relation

m i ≤ d j=i (δ j + 1) -1. Hence, outdeg M (s) = m 1 < d j=1 (δ j + 1).
Lemma 3.3. Let δ 1 , . . . , δ d be positive integers such that

d i=1 δ i = ∆. Then d i=1 (δ i + 1) ≤ 2 ∆ • ( √ 3/2) ∆-d .
Proof of lemma. We will show a more general claim, namely, that for any sequence δ 1 , . . . , δ t of positive integers containing at most d elements equal to 1 and such that t i=1 δ i = ∆, we have t i=1 (δ i + 1) ≤ 2 ∆ • ( √ 3/2) ∆-d . Assume w.l.o.g. that δ 1 ≤ . . . ≤ δ t . First, we consider the case when δ i ∈ {1, 2} for all 1 ≤ i ≤ t, that is, for some c ≤ d, δ 1 = . . . = δ c = 1 and δ c+1 = . . . = δ t = 2. Then,

t i=1 (δ i + 1) = 2 c • 3 (∆-c)/2 = √ 3 ∆ (2/ √ 3) c ≤ √ 3 ∆ (2/ √ 3) d = 2 ∆ • ( √ 3/2) ∆-d
, and the claim holds. Analogously we show that the claim holds when δ i ∈ {1, 2} for all 1 ≤ i ≤ t -1 and δ t = 3. Finally, for any sequence δ 1 , . . . , δ t which does not belong to one of the two considered classes it is immediate to construct a sequence δ ′ 1 , . . . , δ ′ t ′ containing the same number of elements equal to 1, having the same sum, and such that t i=1 (δ i + 1) ≤ t ′ i=1 (δ ′ i + 1). Indeed, if the sequence δ 1 , . . . , δ t contains an element δ i > 3 then we can replace this element by some number of elements

δ ′ i 1 , . . . , δ ′ i k ∈ {2, 3} such that δ ′ i 1 + . . . + δ ′ i k = δ i ,
without affecting the sum and the number of ones in the sequence, and increasing the considered product. Moreover, if the sequence δ 1 , . . . , δ t contains some two elements δ i 1 = δ i 2 = 3, then we similarly replace them by three elements

δ ′ i 1 = δ ′ i 2 = δ ′ i 3 = 2
, retaining all the desired properties. This completes the proof of the lemma. Now, recall that the number of searching robots released in the current p-th phase is chosen as

S p = ⌈2 ∆ • ( √ 3/2) p-1 ⌉.
Since by the inductive claim from phase p -1, we have that d ≤ ∆p + 1, we obtain from the preceding lemma:

outdeg (H,R) (s) = S p ≥ 2 ∆ • ( √ 3/2) ∆-d ≥ d i=1 (δ i + 1)
. This means that the claim of Lemma 3.2 does not hold, and so the assumption outdeg (H,R) H

(2)

f i ≥ indeg (H,R) H (2) f i δ i +1
is violated for some component H

(2) f i . From Lemma 3.1 we thus immediately conclude that d = 1 and H

(2)

f 1 = G[V \ BH],
hence in this case the black hole search problem has been successfully solved. This completes the inductive proof that at the end of the p-th phase, d (3) ≤ ∆-p. Thus, after phase p = ∆-1, we have d (3) ≤ ∆-p ≤ 1, and so at the start of phase ∆, d = 1, and all the nodes belong to the same strongly connected component H f 1 . The black hole search problem is thus solved in phase ∆. Theorem 3.2. In the synchronous model, 4 robots are always sufficient and sometimes required to solve the directed black hole search problem with ∆ = 2.

Proof. The lower bound on the number of required robots is a direct consequence of Theorem 1.1. The upper bound is obtained by a similar strategy as that used in the proof of Theorem 3.1, simply releasing 4 searching robots r 1 , r 2 , r 3 , r 4 in a single phase (without any cycle detection or cycle contraction robots). Let {e 1 , e 2 } = BA be the two black hole arcs, originating from nodes v 1 and v 2 , respectively. Robot r 1 may either successfully solve the black hole search instance, or may be destroyed on one of the black hole arcs, say e 1 . In the latter case, robot r 2 will either successfully solve the instance or be destroyed in the other black hole arc e 2 (recall that robots choose to use unvisited arcs, whenever possible, and the graph is strongly connected). Suppose that robot r 3 is also destroyed in some black hole; this is possible, e.g., in the worst-case example from Theorem 1.1. Now, taking into account Lemma 3.2, we observe that at some point during the traversal performed by robot r 4 , nodes v 1 and v 2 will necessarily belong to the same strongly connected component H f (f (v 1 ) = f (v 2 ) = f ). Once robot r 4 has reached this component, it will always exit it by unvisited arcs. Since both arc e 1 and e 2 have already been used (by robots r 1 and r 2 , respectively), robot r 4 will never enter a black hole and will proceed to enlarge component H f , until the whole of the graph has been explored,

H f = G[V \ BH],
and will thus successfully complete the task. Proof. The lower bound on the number of required robots is a direct consequence of Theorem 1.1. The upper bound (which we obviously need to show for the asynchronous model, only) is obtained by simultaneously releasing two robots, each of which applies a strategy identical to that used by searching robots in the proof of Theorem 3.1. It is easy to observe that, throughout the process, each robot is either traversing arcs of an already identified strongly connected subgraph

Results for the asynchronous model

H f of G[V \ BH],
or is exiting such a subgraph by some outgoing arc e. Arc e has either never been visited before by any robot, or is the unique arc exiting H f , which, due to the strong connectivity property of G[V \ BH], has to lead to some node of V \ BH. Thus, a robot may potentially enter a black hole only when using an arc which has been never visited before by any robot. Since ∆ = 1, this means that the black hole may destroy at most one robot, since the remaining robot will not traverse the unique black hole arc at any later time. The surviving robot(s) perform a search of the graph, exploring unvisited arcs, until the whole of the strongly connected component G[V \ BH] has been discovered and the search is complete. Theorem 4.2. In the asynchronous model, at least 5 robots are sometimes required to solve the directed black hole search problem with ∆ = 2.

Proof. The proof considers some possible cases that must be solved by any strategy A for the black hole search problem with ∆ = 2. We first assume that 4 robots are sufficient for solving the problem and then we obtain the claim by showing how an adversary can defeat all the robots. As usual, all the 4 robots start from hb which has two outgoing arcs. All of the examples we consider are such that the only arc of the graph returning to the homebase (marked in Figure 2 with a dashed line) will in some cases never be traversed by a robot. Consequently, we confine ourselves to an analysis of strategies in which all the robots leave the homebase without waiting for any robots to return.

According to A, there are three possible cases for the first move of each robot and three corresponding strategies of the adversary (see Figure 2 for a visualization): (i) all of them follow one direction; (ii) one goes through one direction and the remaining three to the other; (iii and iii') the four robots are equally distributed among the two directions. If (i), then the adversary can locate one black hole on the reached node, and all the robots get destroyed. If (ii), then the adversary can locate one black hole on the node reached by the majority of the robots, hence destroying three of them. The surviving robot reaches a safe node admitting another branching off. One of the two options leads to the black hole, while the other one to hb. As the robot has no further knowledge to distinguish between the two options, the branch it chooses will be set by the adversary as the one leading to the black hole, and again all the robots get destroyed. If (iii), by referring to Figure 2 we have that after the first move, two robots are on node u and two robots are on node v. From the point of view of the pair of robots located at u (respectively, v), this situation is indistinguishable from that of the pair of robots located at w in graph (iii'), where allowing any robot to wait could lead to an infinite deadlock, since all other robots may be destroyed. Hence, all the four robots at u and v in (iii) must move, without waiting for any other robot. The pair of robots on u (resp. v) cannot choose to move along the same arc because they may both be destroyed by the adversary. So, they have to move on distinct arcs. This implies that one robot from u and one from v get destroyed. The snapshot of the network now gives a robot on v and another on z. From v, both outgoing arcs have been already traversed and hence the robot has no further knowledge to distinguish among the two options apart from the ID-s of the robots that have been passing through such arcs. However, these IDs can be exchanged by the adversary by swapping the labels of ports exiting v, thus making this information useless. The robot is thus forced either to wait at v, or enters the black hole. The other robot, which is on z, has again two unexplored options, one leading to hb, and the other to u. The adversary forces the robot to reach u, from there it is analogously forced either to wait or to enter the black hole. Thus, all the robots are either destroyed or deadlocked, and the claim holds.

Conclusions

In this paper, we have considered the black hole search in directed graphs under both the synchronous and the asynchronous settings. The obtained results reflect the difficulty of the problem on directed graphs as well as the difference between the synchronous and the asynchronous settings. It is worth noting how the behavior of the robots must change even for small values of ∆, such as 2. This was not the case for undirected graphs. This makes the study of the problem on directed graphs even more intriguing. One major remaining open problem concerns the possibility of bounding the number of required robots in terms of ∆ in the asynchronous case.

Many variations of the problem still deserve investigation. Changing the assumptions to the initial knowledge of the robots, for instance by (partially) revealing the graph to the robots or providing topological information about the location of the nodes and ordering of the edges, could lead to completely different results.

Figure 1 :

 1 Figure 1: (a) A schematic representation of the paths followed by three consecutive searching robots r 1 , r 2 , r 3 . The strongly connected components H α , H β , H γ associated with respective black hole arcs are assumed to remain unchanged during the phase. (b) The corresponding graph of the precedence relation (≺) on H α , H β , H γ .

Theorem 3 . 1 .

 31 The proposed strategy solves the directed black hole search problem using O(∆ • 2 ∆ ) synchronous robots.

  (a) Multigraph (H, R) contains a directed cycle. Then, since the relation R restricted to nodes from H \ {s} is a sub-relation of precedence relation (≺), and |F | ≤ ∆, the graph of relation (≺) also contains a cycle of length at most ∆ on the connected components from H. Since all such components are contracted into one in the cycle contraction phase, we immediately obtain that the value of d (

Lemma 3 . 1 .

 31 If multigraph (H, R) is acyclic, then we either have d = 1 and H (2)

Theorem 4 . 1 .

 41 In both the asynchronous and synchronous models, 2 robots are always sufficient and sometimes required to solve the directed black hole search problem with ∆ = 1.

Figure 2 :

 2 Figure2:The possible ways that an adversary has to defeat any strategy which aims to solve the directed black hole search problem when using less than 5 robots.

  and only if robot r visited at least one node of H

			(2)
			f i
	before visiting a node of H	(2) f j , and did not visit any node of any other graph from
	H \ {H	(2)

* This work was done during a research collaboration supported by the Italian CNR Short-Term Mobility Program. A. Kosowski was supported Polish Ministry Grant N206 491738. A preliminary version of the paper appeared as [13].


Louise E Rasmussen

Anne S Meyer

Microbial and Enzyme Technology Endogeneous β-D-xylosidase and α-L-arabinofuranosidase activity in flax seed mucilage

Keywords: arabinofuranosidase, arabinoxylan, β-xylosidase, flax seed, mucilage Purpose

Endogeneous β-xylosidase and α-arabinofuranosidase

activity in flax seed mucilage

Introduction

Seeds from flax (Linum usitatissimum) are increasingly used in foods and are recognized to exert potentially positive effects on health due to their high contents of -3 lipids, antioxidants, and dietary fiber [START_REF] Weill | Le lin, son huile, sa graine et notre santé[END_REF]. When flax seeds are wetted, the epidermal cells of the flax seed coats release large quantities of mucilage that form a gel-like capsule surrounding the seeds [START_REF] Naran | Novel rhamnogalacturonan 1 and arabinoxylan polysaccharides of flax seed mucilage[END_REF]. This flax seed mucilage (FM) contains a mixture of arabinoxylan (AX) and rhamnogalacturonan 1 polysaccharides having rare side chain substitutions such as single terminal D-and L-galactose and Lfucose residues (Warrand et al. 2005a;2005b;[START_REF] Naran | Novel rhamnogalacturonan 1 and arabinoxylan polysaccharides of flax seed mucilage[END_REF]). In the AX isolated from FM the ratio of branched to unbranched xylose residues is 1.1:1 and the doubly substituted β-1,4-linked Dxylopyranosyl units, that have single, L-arabinosyl units attached via (α1→2) and (α1→3) bonds, constitute almost 80 mol% of the arabinofuranosyl substituted xylose residues in the AX backbone [START_REF] Naran | Novel rhamnogalacturonan 1 and arabinoxylan polysaccharides of flax seed mucilage[END_REF].

Enzyme-catalyzed degradation of cereal-derived AX is currently receiving significant attention both in relation to biofuel processing and prebiotic food ingredients production (Sørensen et al. 2006;2007;[START_REF] Pastell | In vitro fermentation of arabinoxylan-derived carbohydrates by Bifidobacteria and mixed fecal microbiota[END_REF]. Due to its heterogenous structure, the enzymatic degradation of AX requires coordinated action of several different enzymes: EC 3.2.1.8) catalyze the hydrolysis of the β-1,4 linkages in the backbone of AX (and other xylans), generating a mixture of xylo-oligosaccharides [START_REF] Biely | Microbial xylanolytic systems[END_REF]. β-Xylosidases (EC 3.2.1.37) catalyze the cleavage of xylobiose and the hydrolytic liberation of the terminal xylose unit from the non-reducing end of the xylooligosaccharides arising from endo-1,4-β-xylanase activity [START_REF] Rasmussen | Mode of action and properties of the βxylosidase from Talaromyces emersonii and Trichoderma reesei[END_REF]. Enzymes exhibiting β-xylosidase activity are categorized into seven different GH families: 3, 30, 39, 43, 51, 52 and 54 (http://www.cazy.org/CAZY; [START_REF] Cantarel | The Carbohydrate-Active EnZymes database (CAZy): An expert resource for Glycogenomics[END_REF]. Certain bifunctional β-xylosidases may also exert α-Larabinofuranosidase activity (and vice versa) -those are mainly categorized in GH family 3 (http://www.cazy.org/CAZY; [START_REF] Cantarel | The Carbohydrate-Active EnZymes database (CAZy): An expert resource for Glycogenomics[END_REF]). α-L-Arabinofuranosidases (EC 3.2.1.55),categorized in GH families 3,10,43,51,54,and 62, catalyze the hydrolysis of terminal non-reducing α-L-arabino-furanosyl residues from the xylopyranosyl residues in AX and may also catalyze the hydrolytic release of terminal α-L-arabinofuranosyl residues from other structures (http://www.cazy.org/CAZY; [START_REF] Cantarel | The Carbohydrate-Active EnZymes database (CAZy): An expert resource for Glycogenomics[END_REF]. A particular issue in relation to arabinoxylans is the presence of similarly linked α-L-arabinofuranosyls that require different α-L-arabinofuranosidase activities depending on whether the α-L-arabinofuranosyls are linked to singly or doubly substituted xylose residues or are linked via (α1→2) or (α1→3)-links to xylose [START_REF] Sørensen | Enzymatic hydrolysis of wheat arabinoxylan by a recombinant "minimal" enzyme cocktail containing β-xylosidase and novel endo-1,4-β-xylanase and α-L-arabinofuranosidase activities[END_REF].

We here report on the finding of endogenous β-xylosidase and α-L-arabinofuranosidase activities in flax seed mucilage. To our knowledge, this is the first time that the presence these endogenous activities in FM have been reported.

Materials and methods

Chemicals

Xylo-oligosaccharide standards (X2, X3, X4, X5 and X6) from birchwood xylan were purchased from Megazyme (Bray, Ireland). Pullulan with average molecular weights of 0.13 x 10 4 , 0.6 x 10 4 , 1 10 4 and 40

x 10 4 g mol -1 were from Fluka Chemie AG (Buchs, Switzerland).

Substrates

Water-unextractable arabinoxylan (WUAX) (arabinose:xylose (A/X): 0.61) and water-extractable arabinoxylan (WEAX) medium viscosity (A/X: 0.61), both from wheat, were obtained from Megazyme (Bray, Ireland). Birchwood xylan was purchased from Sigma-Aldrich and used as is. p-nitrophenyl β-Dxylopyranoside (pNPX) and p-nitrophenyl α-L-arabinofuranoside (pNPA) were obtained from Sigma-Aldrich (Bornem, Belgium).

Extraction of flax seed mucilage

Brown species of flax seed were bought from Sun Island (JAN Import A/S, Hadsted, Denmark). The mucilage was extracted from the flax seeds with water for 24 h at ambient temperature according to [START_REF] Naran | Novel rhamnogalacturonan 1 and arabinoxylan polysaccharides of flax seed mucilage[END_REF].

Enzymes

Viscozyme L9 was obtained from Novozymes (Bagsvaerd, Denmark). This enzyme preparation contained different enzymes including arabanase, cellulase, β-glucanase, hemicellulase, and xylanase (Sørensen et al. 2003). The Bacillus subtilis xylanase (BsX) was obtained from Danisco A/S (Brabrand, Denmark). BsX carries a Swiss Prot entry P18429, XynA_BACSU and has been classified as a glycosyl hydrolase family 11 xylanase according to sequence homology (http://www.cazy.org/CAZY; [START_REF] Cantarel | The Carbohydrate-Active EnZymes database (CAZy): An expert resource for Glycogenomics[END_REF]). The xylanase was purified from a Grindamyl H 640 enzyme preparation according to [START_REF] Sørensen | Mapping of residues involved in the interaction between the Bacillus subtilis xylanase A and proteinaceous wheat xylanase inhibitors[END_REF]. BsX had a molecular weight of 20 kDa, pH optimum at 6, and temperature optimum at 50 °C.

SDS-PAGE

Protein content was analyzed by SDS-PAGE using a Criterion XT Precast Gel, 12% Bis-Tris (Bio-Rad, Hercules CA, US). SDS-PAGE was run at 200 V for 60 min. The running buffer was XT MOPS (Bio-Rad) and the gel was stained with Bio-Safe Coomassie (Bio-Rad) according to the manufacturer's procedure.

Enzymatic hydrolysis of FM and other xylan substrates

Enzyme-catalyzed hydrolysis, by BsX, of the four substrates (FM, WEAX, WUAX, and birchwood xylan) was done as described in Rasmussen et al. (2010): Substrate (1% dry wt), 0.1 M sodium acetate pH 6 with 0.02 % sodium azide. BsX was added to the final reaction at 0.12 µmole enzyme g -1 DM substrate.

Samples were withdrawn at set times during the incubation and the enzymatic hydrolysis was stopped immediately by heating (100°C for 10 min). After centrifugation, the supernatant was analyzed further.

For studies of the endogenous activities in FM, the FM was preincubated for 10 min at 40°C with the substrates (WEAX, WUAX, and birchwood xylan) prior to addition of BsX. The final concentration of FM was 0.5 mg DM ml -1 . All procedures were performed in triplicate against a reference (no enzyme).

Enzyme assay and kinetics

Enzyme activity in the FM was assayed by the hydrolysis of 44 mM pNPX and pNPA, respectively in 0.1 M sodium acetate, pH 6 at 40°C for 30 min. FM was added in amounts sufficient to promote an increase in One unit (U) of β-xylosidase or α-L-arabinofuranosidase activity was defined as the amount of enzyme catalyzing the hydrolysis of 1 μmol of pNPX or pNPA min -1 , respectively. Specific activities are given as units (U) per mg total protein in the FM. For determination of the K M values for the β-xylosidase and arabinofuranosidase activities in FM, activity assays were performed on pNPX and pNPA at concentrations between 3.7 and 44 mM at pH 6 and 40°C. K M and V max values for both substrates were calculated from Hanes plots, i.e. [S]/v i vs. [S].

High performance size exclusion chromatography (HPSEC)

HPSEC was carried out as described in Rasmussen and Meyer (2010).

High performance anion exchange chromatography (HPAEC)

Separation and quantification of xylo-oligosaccharides in the hydrolysates were performed as described in Rasmussen et al. (2010).

Results

Composition of flax seed mucilage (FM)

Determination of the monosaccharide content of FM by HPAEC (Table 1) revealed that xylose was the most abundant monosaccharide of the FM constituting 43% (equivalent to 47 mol %) of the carbohydrate fraction. Galactose was the second most abundant monosaccharide making up about 20% by weight (17 mol %) of the carbohydrate fraction, with arabinose and galacturonic acid at relatively lower levels, and fucose, rhamnose and glucose present in lower amounts (Table 1). By summing up xylose, galactose, arabinose, fucose, and glucose the neutral polysaccharides of flax seed mucilage (FM) were estimated to make up about 83 % by weight (equivalent to 85 mol %) of the carbohydrates. Acidic polysaccharides calculated as rhamnogalacturonan 1 were estimated to constitute about 17 % by weight with rhamnose and galacturonic acid as the main constitutents. The proportion of acidic to neutral polysaccharides was similar to that previously reported by [START_REF] Warrand | Large-scale purification of water-soluble polysaccharides from flaxseed mucilage, and isolation of a new anionic polymer[END_REF] and [START_REF] Guilloux | Production of arabinoxylan-oligosaccharides from flaxseed (Linum usitatissimum)[END_REF], but the A/X ratio of 0.31 was slightly lower than that reported by [START_REF] Guilloux | Production of arabinoxylan-oligosaccharides from flaxseed (Linum usitatissimum)[END_REF] (they reported A/X 0.36).

The FM also contained about 9.5 % by (w/w) protein as determined by a BCA Protein Assay Kit (Table 1).

The protein was also seen when a sample of FM was analyzed by SDS-PAGE, where a smear of protein bands occurred, but with a band between 20 and 25 kDa being predominant (data not shown).

Enzymatic hydrolysis of FM

During treatment with BsX the reducing ends assay showed a modest increase in xylose equivalents released from FM as compared to from WEAX as a result of the xylanase activity (Fig. 1). The low degree of hydrolysis of FM was also observed with HPSEC where only a slight change in the molecular weight took place during enzymatic hydrolysis as compared to the hydrolysis of WEAX (Fig. 2A and3A). In order to analytically quantify the progress of the enzymatic hydrolysis, the HPSEC chromatograms were divided into fixed time intervals and the refractive index response (the area under the curve) was used for quantification (Rasmussen and Meyer, 2010)(Fig. 2B and3B). The main change in area on both substrates, representing the effect of the BsX activity, took place during the first 4 hours. Thereafter, no significant change was observed (Fig. 2B and3B), but the evolution of the area response levels within the time intervals differed for the two substrates (Fig. 2B and3B). Analysis by HPAEC of the activity of BsX on FM also revealed that the BsX was unable to catalyze the release of significant amounts of small xylooligosaccharides (DP 2-6) from FM during 24 h of incubation (data not shown).

Endogeneous activity

In order to examine if FM contained any endogenous activities or inhibitors for the BsX, FM was added together with BsX to different AX substrates which differed in structure: WEAX, WUAX and birchwood xylan. In all three cases significant amounts of small XOS (DP 2-6) were released from the substrates during 24 h of incubation (Fig. 4). The XOS were mainly contributed by xylobiose (X2), xylotriose (X3) and to some extent xylotetraose (X4), but xylose was released from all substrates and arabinose from WEAX and WUAX (Fig. 4). Previous results have shown that this BsX xylanase catalyzes the liberation of significant amounts of small XOS (DP 2-6) from these substrates, but no xylose or arabinose (Rasmussen et al. 2010). Therefore, the observed release of xylose and arabinose suggested the presence of endogenous β-xylosidase and α-L-arabinofuranosidase activities in the FM. Further analysis revealed that initially the arabinose was released faster than the xylose from both substrates. Nonetheless, after 24 h more xylose than arabinose had been released (Fig 4 .). This pattern was confirmed when the initial rates of arabinose, xylose and XOS release in the reactions with BsX and FM added together were compared for all three substrates (Table 2).

The finding that more xylo-oligosaccharides, xylose, and arabinose were released from WUAX than from WEAX during the combined BsX and FM catalyzed hydrolysis (Figures 4B andC) is in accordance with previous data signifying a higher propensity of BsX to attack WUAX than WEAX (Rasmussen et al. 2010).

The highest amounts of XOS and xylose were released from birchwood xylan (Fig. 4A). This can be related to the structure of this substrate since it has a much lower substitution degree than WEAX and WUAX hence presumably providing better access for the BsX enzyme to the xylan backbone. Moreover, the xylose content in birchwood xylan was higher than 90% (by weight) where WEAX and WUAX, both had an A/X ratio of 0.61. No arabinose was released from birchwood xylan which is accordance with the low (negligible) arabinose levels in birchwood xylan and confirming that while the BsX action on this substrate produced attack points for the β-xylosidase activity in the FM there were hardly any bonds to attack for the putative α-L-arabinofuranosidase activity.

The effect of the addition of FM to the BsX endo-1,4-β-xylanase reaction on WEAX was also evident on the HPSEC chromatogram when compared to that without addition of FM (Fig. 3A and5A). According to Fig. 2A, the FM contained polymers with a molecular weight larger than 400 10 3 Da and these polymers were also seen in Fig. 5A (appear less pronounced because of the scale difference on the vertical axes).

During the incubation period, the molecular weight of WEAX changed as result of the endo-1,4-βxylanase treatment, and an increase in low molecular weight molecules was also observed. These smaller molecules were not released when the WEAX was treated with the BsX alone. The areas in the 23-26 min and 26-29 min intervals changed most significantly during the incubation (Fig. 3B and5B). The decrease in the 23-26 min interval after 4 h incubation indicated that the molecules eluting within this time interval were substrates for the enzyme activities in FM since this decrease was not observed when WEAX was hydrolyzed by BsX alone. Furthermore, the increase in the area between 26 and 29 min, representing molecules smaller than 1.3 x 10 3 g mol -1 , was 46% higher than the area in the same time interval when hydrolysis of WEAX was catalyzed by BsX without addition of FM.

Kinetic parameters

The putative endogenous β-xylosidase and α-L-arabinofuranosidase activities in FM were assayed on pNPX and pNPA substrates in order to estimate the specific activity and kinetic parameters (Table 3).

The specific activities were calculated based on the total protein concentration in FM. Both the specific activity and the substrate affinity (as judged from the K M values) were higher on pNPX than on pNPA (Table 3). These findings contrast the HPAEC results that indicated that the putative α-L-arabinofuranosidase activity in FM catalyzed a faster release of arabinose than xylose on the genuine polymeric substrates (Fig. 4). The discrepancy may be due to the generally faster rate of β-xylosidase on short oligomers, xylobiose and pNPX than on longer AX chains. Nonetheless, since the β-xylosidase activity had a higher specific activity and also higher maximal velocity, more xylose than arabinose was released after 24 h incubation (Fig. 4).

Discussion

Previous analysis of the BsX catalyzed hydrolysis of WEAX, WUAX, wheat bran, and birchwood xylan have confirmed that this enzyme is a pure endo-1,4-β-xylanase that catalyzes the generation of significant amounts of small XOS (DP 2-6) without any liberation of xylose (or arabinose) from these substrates (Rasmussen et al. 2010). The finding that BsX treatment on FM only produced a limited degradation -as judged from the evolution of reducing ends -was presumably a consequence of the unique substitutions of the AX in the FM. The wheat AX employed for comparison had an A/X ratio of 0.61 with a distribution of doubly and singly substituted xylopyranosyls of approximately 50:50 and no other main chain substitutions [START_REF] Sørensen | Enzymatic hydrolysis of wheat arabinoxylan by a recombinant "minimal" enzyme cocktail containing β-xylosidase and novel endo-1,4-β-xylanase and α-L-arabinofuranosidase activities[END_REF]. The compositional analysis of FM showed an A/X ratio of only 0.31. However, relatively high levels of galactose to xylose were found (Table 1), and previous data have shown that the flax seed FM contains D-galactose [START_REF] Naran | Novel rhamnogalacturonan 1 and arabinoxylan polysaccharides of flax seed mucilage[END_REF]. [START_REF] Guilloux | Production of arabinoxylan-oligosaccharides from flaxseed (Linum usitatissimum)[END_REF] also suggested that the high ramification of flax seed AX polysaccharides could decrease the efficiency of enzyme catalyzed hydrolysis of flax seed AX. Co-incubation of FM and BsX produced xylose from birchwood xylan and both xylose and arabinose from the wheat arabinoxylan substrates (Fig. 4). This indicated that FM contained β-xylosidase and α-L-arabinofuranosidase activities that catalyzed the release of xylose and arabinose, respectively, from the xylan substrates. The presence in FM of these endogenous enzyme activities were confirmed by the activity measurements on pNPX and pNPA, respectively. The presence of active enzymes in the FM is most likely related to the extraction method where in this study, the mucilage was extracted at room temperature. In other studies of FM extraction was done at significantly higher temperatures, i.e. 80°C [START_REF] Guilloux | Production of arabinoxylan-oligosaccharides from flaxseed (Linum usitatissimum)[END_REF]) and 100°C [START_REF] Diederichsen | Variation of mucilage in flax seed and its relationship with other seed characters[END_REF]. The concentrations (and/or activities) of these endogenous enzymes were apparently relatively low and only a smear of bands and only a relatively low molecular weight band (25-30 kDa) appeared on the SDS PAGE. The approximate molecular weights of the fungally derived enzymes are generally much higher, e.g. approximately 100 kDa for β-xylosidase from T. reesei and 60-92 kDa for different fungal α-L-arabinofuranosidases [START_REF] Sørensen | Enzymatic hydrolysis of wheat arabinoxylan by a recombinant "minimal" enzyme cocktail containing β-xylosidase and novel endo-1,4-β-xylanase and α-L-arabinofuranosidase activities[END_REF]. Also, relatively high concentrations of pNPX and pNPA and a long incubation period (30 min) were necessary to measure the kinetic parameters. Whether FM contained two different enzymes or rather a bi-functional β-xylosidase/α-Larabinofuranosidase requires further study. Previous results have suggested the existence of bifunctional β-xylosidase/α-L-arabinofuranosidase enzymes, e.g. in roots of alfalfa (Xiong et al. 2009).

Conclusion

FM mucilage contains endogenous β-xylosidase and α-L-arabinofuranosidase activities being active on synthetic substrates like pNPX and pNPA and natural substrates like birchwood xylan, WEAX and WUAX.

Limited degradation of FM by a pure endo-1,4-β-xylanase, BsX, was observed, which may be ascribable to the high proportion of substitution of the FM xylan, notably a possible higher galactose substitution degree compared to e.g. wheat arabinoxylan. The finding of these endogenous activities was probably due to the relatively mild extraction method. The reducing ends were measured by the 4-hydroxybenzoic acid hydrazide (PAHBAH) assay with absorbance measurements at 410 nm [START_REF] Lever | Carbohydrate determination with 4-hydroxybenzoic acid hydrazide (PAHBAH): Effect of Bismuth on the reaction[END_REF]. Values represent the mean of three independent measurements and are shown ± 1 standard deviation. Tables Table 1 Monosaccharide content of FM as determined by HPAEC-PAD analysis [START_REF] Arnous | Comparison of methods for compositional characterization of grape (Vitis vinifera L.) and apple (Malus domestica) skins[END_REF] after acid and enzymatic hydrolysis [START_REF] Garna | New method for a two-step hydrolysis and chromatographic analysis of pectin neutral sugar chains[END_REF]. The data are expressed as mg dehydrated monosaccharide g -1 dry matter (DM), mmole dehydrated monosaccharide g -1 DM, and as relative percentage weight and molar distributions, respectively, of the carbohydrate fraction. Arabinose/xylose ratio (A/X) as calculated from HPAEC data and protein content as determined by the BCA Protein Assay Kit (Thermo Scientific, Rockford, US).

Figure legends

Fig. 1

 1 Fig. 1 Progress curves of formation of reducing ends assessed as xylose equivalents (xylose

Fig. 2

 2 Fig. 2 BsX catalyzed hydrolysis of FM. (A) HPSEC chromatographic profile after 0 min (------), 1 h (----

Fig. 3

 3 Fig. 3 BsX catalyzed hydrolysis of WEAX. (A) HPSEC chromatographic profile after 0 min (------), 1 h (--

Fig. 4

 4 Fig. 4Progress curves of the products generated from the catalyzed hydrolysis of different xylan substrates by BsX (0.12 µmole g -1 DM substrate) in the presence of FM (0.5 mg DM ml -1 ). (A) WEAX, (B)

Fig. 5

 5 Fig. 5 Enzyme catalyzed hydrolysis of WEAX by BsX and FM together. (A) HPSEC chromatographic profile

  Figures

Table 2

 2 Initial rates (v i ) [µM min -1 ] of arabinose, xylose and XOS release by the hydrolysis of individual polymeric substrates by co-inclubation with BsX and FM.

			v i
		Arabinose	Xylose	XOS
	WEAX	1.8±0.13	0.3±0.01	3.1±0.02
	WUAX	1.5±0.02	0.5±0.01	20.3±0.28
	Birchwood xylan	*	1.1±0.03	34.1±0.72
	* No arabinose was released from this substrate

Table 3

 3 Kinetic parameters for FM on pNPX and pNPA substrates ± standard deviation (n=3).

Acknowledgements

This study was partly supported by the Innovative Bioprocess Technology Research Consortium financed by the Danish Research Council for Technology and Production Sciences, Chr. Hansen A/S, Danisco A/S,


Christian Wengert

Matthijs Douze

Hervé Jégou

Bag-of-colors for improved image search

This paper investigates the use of color information when used within a state-of-the-art large scale image search system. We introduce a simple yet effective and efficient color signature generation procedure. It is used either to produce global or local descriptors. As a global descriptor, it outperforms several state-of-the-art color description methods, in particular the bag-of-words method based on color SIFT. As a local descriptor, our signature is used jointly with SIFT descriptors (no color) to provide complementary information. This significantly improves the recognition rate, outperforming the state of the art on two image search benchmarks. We will provide an open source package of our signature.

INTRODUCTION

We consider the problem of content-based image retrieval, for applications such as object recognition or similar image retrieval. This problem requires to produce a description of the image, typically a fixed-size vector. This description must be discriminative, but sufficiently invariant to handle the transformations the image may have undergone (cropping, different viewpoints, rotation, etc).

Most of the recent state-of-the-art large scale image search systems [START_REF] Nistér | Scalable recognition with a vocabulary tree[END_REF][START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF] rely on local descriptors, in particular the SIFT descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] and its variants. They are extracted from regions of interest using a scale-invariant detector [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Mikolajczyk | A comparison of affine region detectors[END_REF][START_REF] Matas | Robust wide baseline stereo from maximally stable extremal regions[END_REF]. These descriptors are often used jointly with the the bag-of-words (BOW) framework [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF], which produces a single vector from a set of local descriptors.

Surprisingly and despite its assessed relevance for image classification [START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF], most of the recent papers on large scale image search ignore color information. The best results reported for this task on popular benchmarks, such as the UKB [START_REF] Nistér | Scalable recognition with a vocabulary tree[END_REF] or Holidays datasets [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF], which both contain colorful images, are reported for techniques based on grey-level SIFT descriptors only. Related work on color descriptors: The body of literature dealing with color descriptors is vast. Some of these descriptors have been normalized in the MPEG7 standard. The color version of the GIST descriptor [START_REF] Oliva | Modeling the shape of the scene: a holistic representation of the spatial envelope[END_REF] is widely used for scene recognition. For the sake of conciseness, two color signatures will be used as reference, namely color GIST [START_REF] Oliva | Modeling the shape of the scene: a holistic representation of the spatial envelope[END_REF] and color SIFT [START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF]. The color SIFT descriptor is the counterpart of SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] with color integrated. Its Pre-print (author) version. To be published in ACM Multimedia 2011.

best variant [START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF] is the OpponentSIFT [START_REF] Van De Weijer | Boosting color saliency in image feature detection[END_REF]. Similar to SIFT, it describes regions of interest extracted by a detector. It has mainly be considered for image and video classification tasks. For this reason, it is used in conjunction with the BOW aggregation framework [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF]. However, this paper shows that much better results can be achieved using these descriptors by combining them with the state-of-the-art local descriptor matching method of [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF].

The main contribution of our paper is a simple color description method, which is used to produce either global or local descriptors. In the first case (global), computing the image signature is much faster than producing a BOW vector with [START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF]: the main bottleneck is the computation of a color histogram, which is fast. Most importantly, improved search results are obtained on the evaluation datasets compared to other global descriptors.

The paper is organized as follows. Section 2 introduces our color signature generation procedure and analyzes the impact of several parameters and variants. As a global descriptor, our signature outperforms other global descriptors, including BOW generated from SIFT or color SIFT descriptors. Section 3 explains how the signature is used to describe local patches. Our color signature used jointly with SIFT descriptors outperforms the state of the art for the same memory usage and complexity. It is also better than color SIFT used within a comparable search system.

BAG-OF-COLORS SIGNATURES

In this section, we propose a method to extract a color signature, called bag-of-colors (BOC). This signature is extracted either for the whole image, producing a global descriptor, or from a patch (extracted by a region detector [START_REF] Mikolajczyk | A comparison of affine region detectors[END_REF][START_REF] Matas | Robust wide baseline stereo from maximally stable extremal regions[END_REF]), in which case we obtain local color descriptors.

Since the method relies on computing a color histogram, the proposed signature is conceptually close to the work of [START_REF] Swain | Color indexing[END_REF]. However it departs from this method in several ways that drastically improve the recognition results. First, instead of using a regular color partition as in [START_REF] Swain | Color indexing[END_REF], the color codebook is learned on a set of realworld images. Most importantly, the histogram is constructed and normalized in a way inspired by the successful ingredients of the BOW framework [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] and recent improvement proposed for the Fisher kernel [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF], but here applied to color components. As a result, the signature is more robust and avoids the typical problem of [START_REF] Swain | Color indexing[END_REF], where the most frequent colors dominate the other colors in the final representation and deteriorate the performance.

Hereafter, we introduce the signature generation procedure, analyze its results, and finally give a comparison with a BOW approach which shows that our signature provides consistently better results.

Color descriptor pipeline

Our color signature generation pipeline includes several steps. Different choices of parameters are investigated and evaluated. Color space: Similar to most color descriptors, we use the CIE- Lab 1 color space in all our methods. This space is preferred to, e.g., the opponent space because it is more consistent with the Euclidean space structure, in particular the color dictionary generation procedure, which is based on k-means.

Color codebook: Our method needs a color dictionary C = {c1, . . . , c kc }, defined as a set of kc colors (often referred to as a palette). We first consider building a codebook by quantizing each L, a and b components separately and regularly in 4 or 8 bins, leading to kc = 64 or 512 colors in total.

Then, we also learn a color dictionary that is more adapted to natural images. It is obtained by selecting and clustering typical colors from real-world images. In order to reduce the impact of some images containing large uniformly colored areas, we propose the following procedure in order to collect typical and unique colors for producing the color dictionary. 1) Collect 10000 random images from Flickr.

2) Resize each image to 256×256 pixels, convert it to CIE-Lab and split it in blocks of 16×16 pixels (i.e., 256 blocks in total). 3) For each block, find the most occurring color. Ties are randomly resolved. If this color corresponds to less than 5 occurrences (out of 256), then select an arbitrary color from the block. 4) At this point, we have extracted 256 Lab colors per image. The set of 256×10000 colors from all images is clustered using a k-means algorithm, producing kc Lab colors palette. The palettes learned by our procedure are shown in Figure 1 for different values of kc. Some colors (e.g., dark grey/brown) are more represented than others in the palette, due to the unbalanced color statistic of natural images.

Color signature: The first step of our color signature method consists in computing the histogram of colors in the image for the fixed color codebook C. This is done by first resizing (isotropic scaling) the image to a fixed number (≈16384) of pixels. For each pixel p we select the closest color (w.r.t. the Euclidean distance) in the codebook C, and increment the corresponding bin of the output kc-dimensional histogram.

Inverse document frequency is a successful technique in BOW. It downweights the contribution of the most common visual words and increases the importance of rare visual words by multiplying the frequency component with its corresponding idf weighting term. Similar to this technique, we update the histogram components by applying color idf weighting terms.

Normalization: power-law and normalization. Two techniques are considered. First, the "power-law" transformation 1 More precisely, we used the ITU-R recommendation BT.709 using the D65 white point reference. Table 1: Color signature construction in CIE-Lab space. Impact of the dictionary: structured refers to a typical palette (Lab is split in either 4x4x4 or 8x8x8 components, leading to kc = 64 or 512), learned refers to our color learning procedure for natural images. Our BOC method is #8.

proposed in [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF] for Fisher vectors is applied component-wise. For a vector x = (x1, ..., x d ), it consists in updating each component as xi := √ xi.

Similar to idf, the objective of the power-law update is to downweight colors in images that have very high frequencies, but in contrast to idf it does not take into account the statistics of other images in the dataset. The empirical distribution of colors gives very limited importance to less occurring colors, for instance those associated with small objects. The power-law method regularizes the contribution of each color in the final descriptor.

Finally, a L1 vector normalization is performed to make the vectors more comparable. The vector is updated as x := x/ i=1..d xi.

Although an Euclidean normalization is often adopted in the BOW framework (e.g., in [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF][START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF]), the L1 normalization provides consistently better results for our color signatures.

Comparison metric: Signatures are compared to find the nearest neighbors of the query image in a database of signatures. The choice of the comparison metric is therefore critical. We compare the simple Manhattan (L1) and Euclidean (L2) distances, as well as distances specifically used for histograms: the fast Earth-Mover-Distance of [START_REF] Pele | Fast and robust earth mover's distances[END_REF], the χ 2 distance, the Shannon-Jenson divergence (SJD). The histogram intersection (HI) which were used in [START_REF] Swain | Color indexing[END_REF] for color histograms are equivalent to the L1 distance if the vectors are L1-normalized.

Evaluation

To motivate our final method, we analyze the impact of the choices involved in the bag-of-colors generation process. The search quality is evaluated as the mAP on the INRIA Holiday dataset [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF], computed by the evaluation package available online. In this section, for the sake of exposition, our analysis is conducted on global descriptors only. The results for local descriptors obtained with the same signature generation method are analyzed in Section 3.

Dictionary, normalization and comparison metric have an impact that is summarized in Table 1. First observe that a learned vocabulary gives much better results that the original scheme by Swain which regularly splits the L, a and b axes (leaving many bins empty, as the Lab colorspace is not a cube). Second, the power-law transform has an important impact: an improvement of at least +8% of mAP is achieved by this simple component-wise preprocessing, showing that it is important not to consider dominant colors only. Third, the idf weighting provides a slight improvement of SIFT-based BOW framework. Overall, the best comparison metric is the L1 distance, which is slightly better than the χ 2 distance and JSD. The HI and FastEMD distances provide poor results on our features.

The RGB space has also been investigated. Results are consistently worse than for the CIE-Lab space in all our experiments: for reference, using this color space provides mAP=59.9% at best, compared to 63.8% in the CIE-Lab space.

The number kc of colors in the learned palette is the key parameter of the method. Its impact on both quality and timings is given by Table 2. We measured the signature extraction time with our Matlab implementation (the image is assumed to be resized already to 16k pixels). The search timings correspond to the cost of finding the 100 nearest L1-neighbors in a dataset of 1 million vectors. They have been measured by querying 500 kc-dimensional vectors using exhaustive search.

Our bag-of-colors method is denoted by BOC in the following. It corresponds to the best choices for the global color signature: a palette learned with our procedure, the power-law, idf weighting and L1 normalization. The best comparison metric is L1, which is fortunate as the triangular inequality can therefore be exploited for indexing purpose.

A comparison with the standard BOW method [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] directly applied on raw color pixels (i.e., using CIE-Lab, Euclidean normalization, cosine similarity and idf, but without power-law) leads to mAP=38.4%. This score is comparable with that of Swain's method (Experiments #1 to #4), which gives a mAP between 38.0% and 45.3%, for kc = 64 and 512, respectively.

The comparison with the state of the art is provided in Table 3. It is carried out on two benchmarks: the INRIA Holiday dataset and the UKB benchmark [START_REF] Nistér | Scalable recognition with a vocabulary tree[END_REF]. On UKB the accuracy is measured as the average number of images correctly ranked in top four positions (best score=4).

BOC significantly outperforms BOW: [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF] reports mAP=54.9% for this BOW baseline on Holiday and [3] a score=2.99 on UKB. Besides, it does not achieve the best results of [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF], which reports mAP=81.3% and score=3.42, respectively, with an improved matching scheme based on geometry and Hamming Embedding. However, our approach is significantly simpler, the descriptor extraction orders of magnitude faster, and our descriptors requires only 256 floats, while [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF] requires about 30KB per images. In the next section, we will comment the other results of Table 3, which shows that BOC is also a powerful descriptor for local patches.

LOCAL COLOR SIGNATURE

The color descriptor proposed in the previous section has been shown to provide excellent performance on standard benchmarks. However, because at this point we used it only as a global descriptor, it is not able to cope with the most difficult cases such as strong cropping. Moreover, it does not capture texture information which had made the success of gradient based descriptors such as SIFT. Table 3: Comparison with the state of the art. quality: mAP on Holiday and score/4 on UKB (higher is better). All schemes are compared without the spatial verification re-ranking scheme. N/A means that the image is not represented by a single vector of fixed length D but by a set of descriptors' signatures (typically requires 30kB/image in memory).

In this section, our color signature is applied directly on patches and used in conjunction with SIFT descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] to provide a rich combination of both color and texture, which was shown successful in the recent color extension of SIFT descriptors [START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF]. It is integrated within our own implementation of the image matching method of [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF], called Hamming Embedding (HE), which is a stateof-the-art extension of BOW.

Binary signatures

In [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF], the SIFT descriptors are assigned to visual words, but are additionally described by a binary signature of 64 bits. Each binary signature is computed from the SIFT descriptor, complementing the information given by the visual word. The Hamming distance between binary signatures is used to remove non-matching feature pairs and assign a voting score to the selected matches.

Since this distance removes mismatches, it offers an alternative to the dramatic increase in visual vocabulary sizes required by other approaches (up to 1M visual words in [START_REF] Nistér | Scalable recognition with a vocabulary tree[END_REF]). It is also an elegant way of taking into account the density variations in descriptor space. Indeed, the Hamming distance is implicitly normalized with respect to the local density in the BOW quantization cell. This property facilitates the early fusion of heterogeneous binary signatures, in our case the binary color signature described below.

Color binary signatures

Our approach follows the guidelines of [START_REF] Jégou | Improving bag-of-features for large scale image search[END_REF], but instead of using the 64 bits to describe the SIFT, some of the bits are dedicated to represent color information. A local BOC descriptor is extracted from the elliptical region on the image that is used to compute the SIFT descriptor. We use a palette of kc=256 colors. The vector is then binarized into a short binary signature of fixed size. The Hamming distance between two binary color signature should, at best, reflect the similarity between the original BOC descriptors.

The 256-dimensional BOC vector needs to be reduced to a small number of bits bc (bc = 0..64, depending on the balance between SIFT and color). This descriptor tends to be sparse because it is computed on small regions: on average 80 % of its components are 0. We therefore adopt a dimensionality reduction inspired by [START_REF] Jégou | Packing bag-of-features[END_REF], which was shown effective to reduce sparse BOW vectors. We first generate a sparse binary matrix B of size kc × kc such that each row and each column of B sum up to 8, and keep only the first bc rows, producing a sparse binary matrix B ′ of size bc × kc.

The color binary signature is obtained from a given local BOC vector x by first computing the projected vector

x ′ = B ′ × x.
Second, each component of x ′ is compared to the median value for this component (learned on a training set), which produces a bit. Note: From our experiments, this strategy is better than using a projection obtained by principal component analysis. This might be due to the fact our sparse projection is more consistent with the L1 distance, which is clearly better than L2 for BOC vectors. It is also better than binarizing a BOC vector generated by a palette comprising kc = bc colors.

Experiments

As in Section 2.2, our evaluation is performed on Holiday and UKB. To obtain a fair comparison, we have adjusted the threshold of the color SIFT detector so that, on average, it approximately produces the same number of descriptors per image, as shown below:

Benchmark

Holiday UKB Hessian-Affine + SIFT 2988 1048 color SIFT 3244 1066

The trade-off between color and texture is shown by Figure 2 for a fixed signature of 64 bits, where bc bits are used for color and the remaining 64 -bc bits are the ones defined for SIFT by HE. The importance of color clearly depends on the dataset: SIFT alone performs better than the LBOC descriptor on Holiday, but this observation is reversed for UKB2 . Overall, the optimum is clearly obtained when sharing the bits between these descriptors, with approximately 70 to 75% of the signature dedicated to SIFT and the rest used to represent color.

The comparison with the state of the art is shown by Table 3. Abusing the notation, the method that uses jointly SIFT and our binarized color signature is denoted by LBOC (local bagof-colors). The color SIFT descriptor provides better results than SIFT on Holiday. However on UKB this descriptor suffers from not being invariant to rotation. The results of HE are significantly better than those obtained with BOW, as reported in the literature. The best results are clearly obtained with our LBOC approach, outperforming the reference method (SIFT+HE) and color SIFT by 4.4 % and 2.4 % points of mAP, respectively. Large scale experiments have been performed on Holiday merged with 100K images from Flickr. With SIFT+LBOC, we ob-tain mAP=65.3 % against 61.2 % for HE with SIFT only. Querying the inverted file takes 0.56 s using a single processor core (2.5Ghz). This timing and the memory usage, about 30 kB/image, do not depend on the input descriptor (SIFT, LBOC or a combination).

CONCLUSION

We have proposed a color signature inspired by the bag-of-words framework, and used it either as a global or a local descriptor. Our experiments show that color information significantly improve the retrieval quality in large scale image search, which is often ignored in this context. Our global descriptor exhibits very competitive performance compared to more sophisticated methods. Used as a local descriptor, the results are better than those obtained by a state-ofthe-art system based on SIFT or color SIFT descriptors.

Figure 1 :

 1 Figure 1: Color dictionaries learned by our procedure for kc = 16, 32, 64. Best viewed in color.

Figure 2 :

 2 Figure 2: Trade-off between SIFT and color on Holiday and UKB. Each detected region is represented by 64 bits in total, shared by the representation of the SIFT and the LBOC descriptor. The performance scale on the left is for the Holiday dataset, on the right it is for UKB.

Table 2 :

 2 1 point of mAP, comparable to what is typically observed for the standard Impact of the palette size on accuracy (mAP on Holiday), signature extraction time and search time for querying a dataset of 1 million vectors (one processor core).

	kc	16	32	64	128	256	512 1024
	mAP	41.2 51.8 57.1 61.0 63.8 64.0 64.6
	ms/signature	22	25	27	47	65	128	220
	ms/search	31	59	112	223	432	851 1692

Note, however, that even for UKB with all 64 bits allocated to color in the signature, the visual word already provides a partial information about the SIFT descriptor. Therefore one should not conclude that color is more important than SIFT on this benchmark.

Acknowledgments:

This work was realized as part of the Quaero Project, funded by OSEO, French State agency for innovation.