Maeva Antoine
email: ma.antoine06@gmail.com

Fabrice Huet
email: fabrice.huet@unice.fr

Multiple Order-Preserving Hash Functions for Load Balancing in P2P Networks

Keywords: hash functions, load balancing, structured overlays, skewed data, lexicographic order Rugby Node Id: 180 Key: T ennis Node Id: 60 Key: F ootball (a) Default Chord. (b) Default hash function Node Id: 180 Key: T ennis Node Id: 60 Key: F ootball

Hash functions are at the heart of data insertion and retrieval in DHTbased overlays. However, a standard hash function destroys the natural ordering of data. To perform efficient range queries processing, in a minimum number of hops, more and more systems opt for an order-preserving hash function to place data. Unlike a standard hash function, this technique cannot evenly distribute data among peers. In this paper, we propose a novel approach to improve the data dissemination using several order-preserving hash functions. We describe a protocol that allows an overloaded peer to change its hash function at runtime. Then, we show that all peers should not necessarily use the same hash function in an overlay to insert or look for an item. Finally, we demonstrate through simulations that this strategy greatly improves the dissemination of data items. As this technique does not require any overall coordination, it is well suited to overloaded P2P systems facing unstable topologies. To our knowledge, this is the first load balancing solution using multiple order-preserving hash functions in structured overlays.

at The 15th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT), Hong Kong, 9-11 December 2014.

Introduction

Many Peer-to-Peer (P2P) systems like Chord [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF], Content Addressable Network (CAN) [START_REF] Ratnasamy | A scalable contentaddressable network[END_REF], Pastry [START_REF] Rowstron | Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems[END_REF] or Kademlia [START_REF] Maymounkov | Kademlia: A peer-to-peer information system based on the xor metric[END_REF] face unstable topologies (Dhurandher et al. 2009), making it difficult to insert and locate data items in the network. In such systems, each node only has a partial knowledge of the other peers located in the overlay. To improve file search in P2P systems, several techniques have been proposed in the literature [START_REF] Dhurandher | Using bee algorithm for peer-to-peer file searching in mobile ad hoc networks[END_REF], [START_REF] Navimipour | A comprehensive study of the resource discovery techniques in peer-to-peer networks[END_REF]). Hashing is commonly used in structured overlays to determine which node should store an item. When hashing, a peer that wants to insert or retrieve an item applies a hash function on this item and looks at its Distributed Hash Table (DHT) in order to find the coordinates corresponding to where in the overlay the item should be stored. Consequently, the hash function being used is directly responsible for both determining the efficient retrieval of resources in the overlay and also the good distribution of data across the nodes.

Hashing can be an efficient load balancing technique to uniformly distribute data among peers. Given a set of i items and a set of n possible nodes to store these items, a perfect hash function should map each item to a distinct hashed value and all the nodes should be responsible for the same number of hashed values so that each node stores i/n items. However, such a hash function destroys the semantics of data and a uniform distribution usually implies the loss of the possible links between the items. The drawbacks associated with this random distribution of data affect, for instance, the time required for the execution of range queries, as the matching results are possibly distributed all over the network. This is why some distributed systems for data storage and retrieval tend to use an order-preserving hash function to distribute data across nodes, as proposed by [START_REF] Cai | MAAN: A multi-attribute addressable network for grid information services[END_REF] and more recently for Big Data management systems [START_REF] Escriva | Hyperdex: A distributed, searchable key-value store[END_REF][START_REF] Filali | Modular P2Pbased approach for RDF data storage and retrieval[END_REF]. Data is no longer randomly distributed, and syntactically close items can be retrieved in a minimum number of hops. Peers still use a hash function to determine an item's location: the function uses the natural value of the item (e.g. its lexicographic value) to generate its coordinates in the overlay's identifier space. Unfortunately, this technique cannot always guarantee a satisfying distribution of data among peers since such a hash function cannot efficiently disseminate skewed values. Indeed, when hashing similar keys using an order-preserving hash function, the hashed values are consequently similar as well and may be mapped to a very small area of the identifier space. Such a poor data dissemination may have major impact on the performance of a system, if large workloads are sent to very few nodes. This is a typical challenge for Big Data management systems, as the datasets they manage very often contain skewed values. For instance, [START_REF] Kotoulas | Mind the data skew: distributed inferencing by speeddating in elastic regions[END_REF] have shown a DBpedia [START_REF] Auer | Dbpedia: A nucleus for a web of open data[END_REF] dataset, made of extracted information from Wikipedia, may contain the same key (a popular term) in up to 55% of its records.

As hash functions are at the heart of data distribution for DHT-based overlays, we present in this paper a new load balancing technique relying on the use of several order-preserving hash functions at the same time in a network, to improve the skewed data dissemination. To our knowledge, this is the first load balancing solution using multiple order-preserving hash functions in structured overlays. Our goal is to allow an overloaded peer to modify the hash function it applies on data, in order to be responsible for a smaller interval of values and hence store less items.

To summarise, our work makes the following contributions:

• We describe a protocol that allows a peer to change its hash function at run-time.

• We show that all peers should not necessarily use the same hash function in an overlay to determine an item's coordinates.

• We demonstrate through simulations that this strategy greatly improves the dissemination of Unicode-encoded data items.

The rest of the paper is structured as follows. In Section 2, we present existing load balancing strategies based on multiple hash functions in structured P2P networks. Then, in Section 3, we introduce our approach using variable order-preserving hash functions to dynamically distribute skewed datasets in structured overlays. In Section 4, we detail our solution along with the rules to follow when implementing it in order to maintain an overlay consistent. In Section 5, we present the experiments we ran in CAN and Chord overlays using highly skewed values from real world datasets. Finally, Section 6 concludes this paper.

Related work

P2P systems are an efficient and scalable solution for data storage and retrieval in large distributed environments. However, many P2P systems for data management face the problem of load imbalance between their nodes. These imbalances may be caused by different factors, like churn [START_REF] Ho | Churn: a key effect on realworld p2p software[END_REF] or the lack of information availability [START_REF] Misra | On increasing information availability in gnutella-like peer-to-peer networks[END_REF]. Many different solutions have been proposed to address these issues [START_REF] Felber | Survey on load balancing in peer-topeer distributed hash tables[END_REF], including data replication [START_REF] Pitoura | Replication, load balancing and efficient range query processing in dhts[END_REF], node replication [START_REF] Gupta | Meghdoot: content-based publish/subscribe over P2P networks[END_REF] or keys reassignment [START_REF] Taank | Load balancing algorithm for dht based structured peer to peer system[END_REF]. In this section, we focus on load balancing schemes based on multiple hash functions.

The use of multiple hash functions is mainly suggested in the literature as a solution to address two load imbalance issues: it is usually proposed as a replication scheme for popular items, and more rarely as a way to distribute data items among peers.

Multiple hash functions for popular items

A data item may be more popular than others and, consequently, the peer storing this item has to face an important number of queries, which affects its processing capacity. To speed up response time when a request for a popular item is made, some load balancing strategies replicate a popular item by applying n different hash functions on this item, in order to replicate it at n different locations. For example, the original CAN paper proposes to allow a peer looking for an object obj to apply n hash functions on obj. Each hash function maps obj to a different CAN coordinate and a peer looking for obj can choose the hash function associated with the nearest coordinate to its location in order to minimize the number of hops to retrieve obj. However, this technique requires that all peers know all the different hash functions used to place data in order to be able to choose from where to retrieve it afterwards.

Other papers propose similar replica placement strategies based on multiple hash functions to deal with popular items. [START_REF] Xia | Algorithms and performance of loadbalancing with multiple hash functions in massive content distribution[END_REF] consider a P2P system for file storage where a peer can replicate a popular file at a location found by applying on the file a uniform hash function currently unused in the overlay. At most m uniform hash functions may be used to replicate a popular file. If a file f , currently replicated at i different locations corresponding to hash functions h 1 (f ), ..., h i (f ), exceeds a popularity threshold on a peer p, p has to replicate f at another location using h i+1 (f ). To find f 's current number of replicas (i.e. the value of i), the paper proposes an algorithm that works as follows: p applies x hash functions h 1 , ..., h x on f until h x points to a peer that does not store f , i.e. x = i + 1. When a peer wants to retrieve f , it uses a random binary search algorithm: the peer applies h r (f ) where r is a random value comprised between 1 and m. If f is not found when using this hash function, the peer applies h r2 (f ) where r2 is comprised between 1 and r, and so on until the peer finds f . [START_REF] Mu | Dynamic load balancing with multiple hash functions in structured p2p systems[END_REF] present their approach to dynamically increase or decrease the number of replicas for a popular object. The authors assume a peer can evaluate which of its items are the most popular, in terms of load consumption for a set of predefined load criteria. Every time a node reaches a given load threshold, it creates a i th replica of its most popular item by using a hash function h i and sends the replica to the corresponding peer. Each original object embeds a counter number (equal to i) indicating the number of replicas existing for this object. The authors also assume a peer can distinguish its own original items from those that are replicas received from other peers. Whenever the load of a peer caused by one of its own popular objects decreases under a given threshold (i.e. the object becomes less popular), the peer can launch a removal process of one of its replicas. Concerning the retrieval of items, a peer looking for an object obj for the first time can only use the default hash function known by all peers in the overlay. When retrieving the original item, the peer also retrieves its associated counter number and thus knows the range of hash functions used to replicate this item. If, later, the same peer wants to retrieve obj again, it will be able to contact one of the i locations of obj by computing a hash function between h 1 and h i . [START_REF] Wu | An efficient load balancing scheme for resilient search in kad peer to peer networks[END_REF] use the concept of multiple hashes for data storage and retrieval in the Kademlia P2P network. The authors consider a system where objects are indexed in the overlay according to a keyword value. If all peers use the same hash function to index objects, a bad dissemination of objects occurs when most of them are associated with the same subset of popular keywords. The authors propose that the same keyword may be hashed different times with the same hash function, in order to produce different keys. Each of these keys refers to the same keyword but points to a different peer and hence objects associated with the same keyword can be indexed on different peers instead of only one. For example, hash(word) is the default hash function of the system for keyword word and derived hash functions h 2 and h 3 would respectively correspond to hash(hash(word)) and hash(hash(hash(word))). Up to N hash functions can be used, thus the same keyword may be stored by N peers. [START_REF] Byers | Simple load balancing for distributed hash tables[END_REF] suggest the use of multiple hashing functions for a different purpose than popular items replication. Their approach, presented on the Chord P2P network, aims at addressing load imbalances in terms of items stored per peer, by trying different hash functions on an item to insert it at the least loaded location. To do so, the paper presents a variant of the power of two choices paradigm [START_REF] Mitzenmacher | The power of two choices in randomized load balancing[END_REF]. The power of two choices paradigm consists in applying two hash functions picked at random on an item's key to eventually pick the least loaded node out of the two possible locations to store this item. This paper extends this paradigm to the use of two or more hash functions to compute the potential locations of an item. A node that wishes to insert an item applies d hash functions picked at random on the item's key and gets back d identifiers (each hash function is assumed to map items onto a ring identifier). Afterwards, a probing request is sent for each identifier computed previously and the peers managing the identifiers answer with their load. Once this load information is retrieved, the peer with the lowest load p low is adopted for indexing the item. The other d -1 peers that were contacted but not selected receive a redirection pointer (key space identifier) to p low for the corresponding item. When a peer wants to retrieve an object obj but does not know which hash function has been used to index obj, the peer applies on obj's key a random hash function h r (obj key ) among the d possible hash functions that were applied previously to store obj. Even if h r does not point to the peer storing obj, the peer receiving this query necessarily owns a redirection pointer to obj. Thus, a lookup can be achieved by using only one hash function among d at random and it may take only one more hop to reach the desired resource. However, this technique implies that all peers are aware of the d possible hash functions applied when indexing resources, in order to use one of them, albeit randomly chosen, when looking for an item. The power of two choices paradigm is a load balancing solution that can be used with various types of distributed systems. Recently, [START_REF] Nasir | The power of both choices: Practical load balancing for distributed stream processing engines[END_REF] presented the direct applicability of this paradigm on distributed data stream processing systems, in order to address load imbalances in terms of sub-streams managed by each worker.

Multiple hash functions for data dissemination

Multiple Hash Functions

Unlike the existing strategies, we propose a solution based on multiple hash functions where each node can use its own hash function to place and retrieve data. Moreover, it is not required that all the nodes learn about all the hash functions that can be used in the overlay. To show the interest of our load balancing strategy, we present in this section how the use of multiple order-preserving hash functions can improve the distribution of Unicode-encoded data items according to the lexicographic order.

Order-preserving hash function

Let us consider an overlay made of n nodes (denoted as peers). Each peer p is responsible for an interval of coordinates [min p ; max p ] in the overlay's identifier space ranging from O min to O max . For instance, Figure 1(a) presents a 2-dimensional CAN overlay where each peer manages a zone bounded by an interval on each dimension. Each peer's interval is constant and can only be modified during join or leave node operations. Minimum and maximum Unicode values U min and U max are set to determine the Unicode range that can be managed within the overlay: in Figure 1, U min is equal to A and U max is equal to Z (for more clarity, we use a single character to represent each bound's value). A Unicode value is associated with each bound of a peer and a peer is responsible for storing the items whose Unicode value falls between these bounds. For example, in Figure 1 When a peer receives a new data item to insert or a query to execute, it has to convert the Unicode-encoded values into coordinates to check whether it is responsible for this item/query or not. For example, the hashed value of string P roductT ype1 in the context of an overlay storing worldwide data (wide Unicode range, up to codepoint value 2 20 , as depicted in Figure 2) would be equal to coordinate 0.00004673 (i.e. at the far-left in the identifier space). By default, strings made of Latin characters have a low hashed value, whereas strings made of any East-Asian characters have high values (close to O max ) because such characters are located towards the end of the Unicode table. If the hashed value does not match the peer's coordinates, it means the peer is not responsible for the corresponding item. In this case, the peer forwards the item/query to a neighbour managing an interval closer to the requested one. The order-preserving storage technique presented above suffers from a major drawback regarding data distribution. Figure 2 shows a system where only items made of Latin characters are stored, which means only a very small area of the overlay is always targeted when storing or querying data. The most basic (no accent) Latin Unicode range only includes about 100 different characters whereas there are about one million characters in the whole Unicode table, which makes Latin-encoded values very skewed. In consequence, peer p1, whose zone includes the small Latin interval, may become overloaded, while the rest of the network stores nothing as it is dedicated to other Unicode characters. A solution could be to dedicate the entire network to Latin Unicode data storage. However, being able to manage characters in any language has now become essential, typically for any application using Web data. Data published by the social networks or in the Linked Data [START_REF] Heath | Linked data: Evolving the web into a global data space[END_REF] format can be written in any language, using any Unicode character. For instance, the DBpedia datasets contain characters from 125 different languages. Nowadays, as more and more data is produced, often to be processed in real time, it becomes crucial to dynamically adapt the allocation of resources depending on the incoming data, whose language may vary according to the current trends or even time of day because of the different time zones.

Skewed data, skewed distribution

Based on this observation, our goal is to allocate more space for skewed values in the identifier space, while maintaining the lexicographic order as well as an area for all the other Unicode scripts.

Variable hash functions for overloaded zones

Enlarging the zone dedicated to the Latin data in the identifier space would result in an improved data dissemination among peers, as shown in Figure 3. Concretely, this means that each peer being fully included in the highlighted area becomes exclusively responsible for a given subset of Latin-encoded values. Thus, extending the interval of coordinates dedicated to a given Unicode subset requires that the peers in this interval reduce the Unicode interval they manage. As this mapping between Unicode values and coordinates differs from the standard mapping previously introduced, a non-standard hash function must be used to place the Latin items. The corresponding hash function for the overlay in Figure 3(a) (to be applied on any "enlarged" dimension) is shown in Figure 3(b). Extending the Latin interval in the overlay leads to a different hash function for all the peers in the highlighted area, as the end of this interval (represented by the character Z) is now located at coordinate 0.7.

Computing a new hash function

In this subsection, we explain how a new hash function can be calculated to manage the load imbalance. We consider the number of items stored by a peer as the imbalance criterion, assuming all items are of a similar size.

Let p be a peer storing a given number of items noted as load p in its Unicode interval [U min p ; U max p [. If p is overloaded, it has to send all its items above a certain limit, lim, to its neighbour(s), such as the new value of load p ≤ lim. Basically, p has to reduce its Unicode interval, such as only at most lim data remain in p's zone. This is achievable by simply changing p's hash function from h1 to h2 such that h2(U max p ) = max p and the new value of U max p is equal to the Unicode value of p's (lim + 1) th item (as we consider p can sort its items lexicographically). Thus, by deciding how many items it wants to move, an overloaded peer also implicitly determines its new hash function. An example is shown in Figure 4, where a peer is considered as overloaded if it stores more than 6 items. In Figure 4(a), p1 is overloaded and has to change its hash function on max p1 , associated with the Unicode value mango. A new hash function h2 should transform p1's 7 th triple f ig (as lim is equal to 6) into max p1 . In Figure 4(b), p1 and p2 have changed their hash function to h2 respectively on max p1 and min p2 , and their load is evenly balanced.

Figure 4 Load distribution before and after rebalancing. In this example, a peer is said to be overloaded if it stores more than 6 items.

Rules to Update a Hash Function

As there is no central coordination in an overlay, it is very difficult to change the overall hash function applied in the network. However, it is not necessary for all the peers to use the same hash function to get a fully functional overlay. Routing is done on the go, from one peer to another, and each peer applies its own hash function when receiving a message, to determinate its next recipient (as each peer should know the hash function used by its neighbours). Therefore, the initial sender of the message potentially has no precise idea about where in the system the message will be processed. Overall, different hash functions may be used as long as the rules presented below are observed.

Message propagation

A peer should know the hash function of all its neighbours, and should notify them as soon as it changes its hash function. This ensures the arrival of new peers (division of an existing zone between two peers) is correctly handled. Also, when routing an item/query in the network, this allows a peer to choose among its neighbours which one will be the most efficient for routing this message.

To ensure the overall consistency of the overlay, two neighbouring peers should share a common Unicode-based value, even if they use different hash functions. Given two neighbour peers p1 and p2 using h1 and h2 as their respective hash functions, if max p1 = min p2 , then h1(U max p1 ) = h2(U min p2 ). This rule prevents concurrent hash function changes from creating overlap or empty areas no one is responsible for in the identifier space.

In d-dimensional overlays, like CAN, all peers having a bound at a given coordinate should apply the same hash function on this bound, through the whole dimension. To maintain the routing optimal, peers whose interval includes this bound should also know this hash function, without needing to apply it. Figure 5 describes the impact of this rule by showing the scope of a hash function change in a CAN. Peer p1 decides to change its hash function to reduce its Unicode interval on its bound at coordinate 0.75. Thus, all peers on 0.75 (the grey area in Figure 5) should also apply this new hash function. A multicast message is sent by p1 and routed to all the concerned peers, which also includes p2. Indeed, p2 will not apply the new hash function but must be aware of it, as its CAN interval [0.5; 1] comprises 0.75. This way, if a new peer wants to join p2 and split on its horizontal interval, p2 and the new peer will both know which Unicode value to apply on their new 0.75 CAN bound. Also, p2 must continue routing the multicast message in order to reach p3 and the other concerned peers. The overloaded peer cannot predict if this change will overload some of the concerned peers since they may not be its neighbours. However, this can be easily addressed, as the peers applying this new hash function can also trigger their own hash function change later on.

Bound reduction

Peers having their upper bound in the identifier space equal to the maximum authorized coordinate O max should also be able to reduce their upper Unicode bound. Otherwise, if, for example, a large amount of non-Latin items is sent into the system, they would probably be stored by the peer at the far right in the identifier space, with no possibility for it to balance its load. To avoid this situation, we allow the peers located at the far right of the identifier space to reduce their upper Unicode bound like any other peer. To do so, we take advantage of the tore-ring topology of many overlays like CAN and Chord, and consider O min = O max , which means all Unicode updates associated to O max must also be applied to the peer(s) on O min . As a consequence, the peer(s) on O min can become responsible for two Unicode intervals within a single interval of coordinates. This is shown in Figure 6, representing a CAN where the minimum Unicode value allowed U min is A and the maximum U max is Z. In Figure 6 (b) p7 reduces its upper bound from Z to V, so does p4.

(c) p1, p5 and p6 now own two Unicode intervals.

Concurrency and message filtering

For a given bound, a peer p receiving an update message will allow the new Unicode value only if it is lower than p's current Unicode value for the same overlay-based bound. Thus, it is forbidden to ask for a forwards reduction of the minimum bound, in order to avoid inconsistent concurrent reductions (i.e. on different directions). For example, in Figure 7, if two peers (p1 and p4) decided in a short time interval to modify their Unicode value (respectively U max p1 and U min p4 ) on the same coordinate (0.5) but on different directions (backwards for p1 and forwards for p4), it would become difficult to tell which one has priority over the other, especially since their multicast messages may not be received in the same order by all the concerned peers (p1, p2, p3, p4). Therefore, only p1 should be allowed to reduce its bound. Moreover, a peer is not allowed to modify its hash function while it has received update messages it has not processed yet. Also, if update messages asking for different Unicode values are sent by different peers at the same time and for the same overlay-based bound, we ensure all peers will end up choosing the same value: the lowest one. Thus, the peers will reject the other messages and stop their multicast routing. This rule is very efficient as it guarantees the same value will be picked by all the concerned peers without any mutual consultation. The only case where a higher Unicode value would be accepted is when the reduction is made by a peer already containing two continuous intervals on one dimension (as discussed above in Section 4.2) and the new value is included in the first interval. In

Data movement

After a peer p has changed its hash function, it has to send all the items it is no longer responsible for to its neighbour(s). To do so, p has to wait until they apply the update as well (it should be done quickly as they are only one hop away from p). In the meantime, p still processes queries for the items it wants to move. After sending them, p waits until it receives a storage acknowledgement message from its neighbour(s) before deleting these items, in order to ensure no data is lost during this process.

Data retrieval

Using variable hash functions implies peers may not know where exactly in the overlay an item should be located. However, this does not affect data retrieval, if the rules set out in Section 4 are respected. Let us consider p1 initiates in Figure 9(a) a lookup query to retrieve a data item containing the value Hawaii on dimension 0. Figure 9(b) represents the overall non-linear function used in the overlay, while Figure 9(c) shows p1's knowledge about this hash function. As stated in 4.1, p1 knows the hash functions used by its neighbours p2 and p4 (torus topology). However, p1 has no idea about the hash function used between CAN coordinates 0.5 and 0.75 on dimension 0. As p1 cannot know to which CAN coordinates Hawaii is associated, p1 will route its query towards the closest coordinate to Hawaii it knows of. In our case, this corresponds to the value G associated to CAN value 0.5 on neighbour p2. Then, p2, whose hash function knowledge includes p3 (Figure 9(d)), will be able to estimate item Hawaii should be stored by p3 and will route the query to p3.

Experiments

Experimental set-up

To validate our approach, we ran extensive experiments in the cycle-based simulator PeerSim [START_REF] Montresor | Peersim: A scalable p2p simulator[END_REF], in order to perform large-scale experiments with many peers concurrently modifying their hash function at the same time. A cycle represents the time required by a peer to perform a basic operation (message routing, load checking, etc.). We simulate a network composed of 1000 peers. The maximum Unicode value supported U max is set to character number 2 20 , to encompass the whole Unicode table of characters.

In order to make realistic experiments, we used a dataset made of real world data from two different sources. The first one is only composed of Latin Unicode characters, from the Berlin BSBM benchmark [START_REF] Bizer | The berlin SPARQL benchmark[END_REF]. The second source is extracted from DBpedia and contains Japanese Unicode characters. Each data item takes the form of a triple of three Unicode-encoded elements (<subject;predicate;object>) according to the Resource Description Framework (RDF) [START_REF] Lassila | Resource Description Framework (RDF) model and syntax specification[END_REF] format used to represent Semantic Web data. The subject value represents a resource, the predicate is a property of this resource and the object is the value of this property. One million triples are inserted into the network in the space of 15 cycles, to simulate bursty traffic with a continuous insertion of data.

Load balancing policies

Various load balancing policies may be conceived to implement the multiple hash functions strategy, regarding how a peer evaluates its load state and how many items should be moved. Table 1 summarises the different policies we used during our experiments for these two behaviours.

CAN experiments

We simulated a 3-dimensional CAN for RDF data storage with each dimension being associated with one of the three parts of an RDF triple [START_REF] Filali | Modular P2Pbased approach for RDF data storage and retrieval[END_REF], as shown in Figure 9. Let us consider z smin , z smax , z pmin , z pmax , z omin and z omax the minimum (min) n/a and maximum (max) borders of a peer's zone according to the subject axis (z smin , z smax ), the predicate axis (z pmin , z pmax ) and the object axis (z omin , z omax ). We consider that a triple t =< s, p, o >∈ z only if z smin ≤ s < z smax , z pmin ≤ p < z pmax and z omin ≤ o < z omax , where s, p, o respectively represent the subject, the predicate, and the object of the triple t and z is a zone of the CAN overlay. For better understanding, consider the example presented in Figure 10. Suppose that node n 0 receives an insert(t) request aiming to insert the RDF triple t in the network. Since no element of t belongs to the zone of n 0 , and as s fits into the zone of n 1 , n 0 routes the insert message to its neighbour n 1 according to the subject axis (S -axis). The same process will be performed by n 1 , by means of the predicate axis (P -axis) which will forward the message to its neighbour n 3 . Once received, n 3 checks whether one of its neighbours is responsible for a zone such as o belongs to this zone. Since the target peer is not found, the message will be forwarded at each step according to the object axis (O -axis) to the neighbour whose object coordinates are the closest to o. The idea behind this indexing mechanism is sketched in Algorithm 1. Additionnally, in order to efficiently propagate the messages sent by the peers, an optimal broadcast algorithm [START_REF] Henrio | An optimal broadcast algorithm for contentaddressable networks[END_REF]) is used. The goal of such algorithm is to ensure a message will be received by each peer only once. end if 8: end event

Reference algorithm

In order to evaluate the efficiency of our solution, we ran a first series of experiments to compare our results with those obtained when using a well-known load balancing strategy relying on a unique and linear hash function. The scheme consists in adding a new peer at the location of an overloaded peer. This technique is the default CAN load balancing strategy and is used by famous P2P storage systems such as Meghdoot [START_REF] Gupta | Meghdoot: content-based publish/subscribe over P2P networks[END_REF]).

To perform experiments using this reference algorithm, we consider an overlay composed of a single peer, at the beginning. Then, periodically, a new peer is added at the most loaded peer's location. When a new peer p new joins an existing zone managed by an overloaded peer p old , p old hands over half of the zone it manages in the coordinate space to p new . Hence, the data located in this area does not belong to p old anymore and is moved to p new . For this different strategy, there is no particular balance to achieve as the peers do not compare their load with a threshold. The experiment consists in starting with one peer receiving the one million triples, then new peers are periodically added until having a network made of 1000 peers. Load balancing is triggered by an external event (a new peer joining), thus the experiments were stopped once all peers were added. Table 2 summarizes the results obtained for each load balancing strategy at the end of simulations. Results are expressed in terms of number of peers storing data (out of 1000), hash functions updates sent by overloaded peers, cumulated total number of triples moved from peers in order to balance their load, cycles to achieve balance (after all triples are stored by the very first peer) and standard deviation in terms of RDF triples stored.

Results

Without applying any load balancing strategy, results show that only 2 peers would store data, because of the large bias between datasets (Latin vs. Japanese characters). These two peers respectively correspond to the one at the far-left of the CAN on each dimension, responsible for storing all Latin triples, and the peer at the far-right of the CAN on each dimension, responsible for storing all Japanese triples. When using multiple hash functions, data was disseminated over up to 818 peers (with the "local" policy). A perfect distribution would correspond to all 1000 peers storing 1000 triples. However, this is not achievable in practice for two reasons. First, the CAN topology may not be perfect (some zones larger than others). Secondly, real RDF data is often very skewed, due to the large scope of the whole Unicode and the fact that the RDF triples may contain very similar values, like ID values that differ by a single character. Also, the predicate values are often not very distinct. For instance, thousands of different triples could share the same predicate: typeOf, specifying the RDF type of the subject. Overall, our datasets contained less than 50 different values of predicate, which explains the impossibility to perfectly distribute data on the predicate dimension of the CAN. When adding peers at the most loaded locations, i.e. when using a linear hash function shared by all peers, data is far less well distributed (407 peers). The main reason for this lies in the fact that the skewed data is mapped to an extremely small area in the identifier space, as shown in Figure 11(b), depicting a simplified version of the CAN after several peers have joined the most loaded peer. By adding new peers, data is moved from one peer to another but the items' coordinates still remain the same as the hash function applied by all peers on data does not change. This considerably limits data dissemination and, at some point, becomes ineffective.

Using variable hash functions required to move an important volume of data to balance the load. However, our results show that a more conventional strategy fails to achieve better results in terms of data items moved between peers: around 9 million triples were moved when adding peers against approximately 4.5 and 5 million for the local and overall schemes. Therefore, our solution, although not perfect, is not more costly regarding data transfer than other existing load balancing strategies. Moreover, it has the advantage that it does not require data to be moved far away in the overlay because only one hop is necessary to move data to a direct neighbour. To date, generally speaking, it remains impossible to address the load imbalance issue regarding data storage without having to move large amounts of data.

To ensure that the load balancing operations do not affect the consistency of the overlay, 200 random queries were sent to random peers throughout the experiments. For all of them, the correct result was received within a reasonable time (an average of 15 hops to route queries or results, hence 15 cycles). The number of update bound messages created by peers and the fact that these updates may not be applied by all peers at the same time did not affect the resolution of queries within our system. This is because an item is always stored at least on one peer. Moreover, moving data is only done once an update bound message is applied by both the sender and the receiver. Thus, reaching the new responsible peer for a given item should not require more than a few hops in the network, at the very most. (c) CAN using variable hash functions.

We ran a second experiment to evaluate the efficiency of our load balancing policies depending on the two behaviours chosen for estimating the load state of peers and selecting the load to move. Table 3 presents the different results regarding data distribution among peers. Results show that the data distribution can be notably improved depending on these two behaviours. It is interesting to note that a better distribution occurs when taking into account the load information of other peers to calculate the amount of load to move. When being associated to an overall knowledge of the network load to estimate a peer's load state, the distribution is almost perfect, with 945 peers storing data out of 1000. As such knowledge might not be achievable in practice, relying only on the load information received from neighbours or even no external information to estimate a peer's load state also seems to offer a convincing data dissemination (respectively 818 and 715 peers concerned). This means we could consider a strategy with no load information exchange before a peer gets oveloaded and, only in this case, messages would then be exchanged with neighbours to estimate their load and hence, the amount of load to move. Such strategy could be regarded as efficient for a system whose peers only know a very small subset of the network (their neighbours), and have few or no contact with other peers. Indeed, with this strategy, no communication between peers is needed to exchange load information as long as no peer gets overloaded. Moreover, the load information exchange would be restricted as an overloaded peer would only contact its neighbours to determine the best amount of load to move. These results show that the efficiency of this technique is strongly linked with the policies used to determine a peer's load state and the new hash function to be applied by the overloaded peer. Many variants are possible depending on what are the key issues for a particular system: we tried to distribute the load as much as possible but it is also conceivable to opt for a variant offering a lower dissemination in order to offload some machines while avoiding large data transfers.

Chord experiments

Finally, we ran another experiment to show the multiple hash functions strategy can also be applied to a Chord overlay for Unicode-encoded data storage.

Multiple hash functions in a Chord overlay

We consider the same context that was presented in Section 5.1. Each node n, represented by a fixed Node Id, is associated with a key identifier, and should store all items whose hashed value is comprised between ]key n.predecessor ; key n ]. The default hash function used in Chord destroys the natural ordering of data that we want to preserve. Thus, our default hash function will maintain the lexicographic order. On the ring, this means that nodes are assigned key identifiers ordered according to the lexicographic order. A key refers to an attribute of the data being stored, hence this technique may be applied more generally for any NoSQL data storage for instance. In our example, the key corresponds to the value of an RDF triple's object. We chose the objects as their values are not as biased as predicates, hence this should result in a better distribution. A triple t will be located at successor(t object ): the successor peer of t's object value. As keys correspond to only one part of a triple, routing a query or a triple can be made according to this part only.

We use the node identifier (Node Id) of a node as the fixed coordinate to be associated with the node's key identifier, which can vary, to establish the hash function of the overlay. Unlike the default Chord implementation that assigns node and key identifiers using a consistent hash function, we separate the assignment of node identifiers from the assignment of key identifiers. By default, the key identifier of a node is computed using its node identifier and, very often, the ambiguous notion of identifier is used when referring to either a node or key identifier. In our implementation, both terms refer to two different notions. A node identifier refers to a node and its value can be computed by applying a consistent hash function on the node's IP address (we consider this value should not change), like in any Chord overlay.

The key identifier of a node refers to the maximum key value managed by this peer. We allow a peer's key identifier to change over time by using variable hash functions. This implies, among other things, that peers should dissociate node and key identifiers when routing a message: in our overlay, routing should only be done according to a peer's key identifier. Therefore, the knowledge maintained by peers about their neighbours or finger table entries should include both node and key identifiers. More precisely, a finger table entry in our Chord implementation should contain the node identifier and the IP address of a peer (as in any Chord overlay) to identify a node, but also the key identifier associated to this peer in order to resolve lookups.

Whenever a peer is overloaded, according to a given load balancing strategy (the same as those described in Table 1), this peer can reduce its key identifier value in order to store less data. For example, in Figure 12, N ode 160 (N 160) has reduced its key identifier to only store values between interval ]F ootball; Golf ]. As a consequence, its successor N ode 180 has a wider Unicode interval to manage (]Golf ; T ennis]). As presented in Section 4.1, a peer updating its hash function must notify its neighbours. This means N 160 has to notify all its successor(s). As there is no notion of dimension in Chord, there is no need to propagate this information any farther to maintain the overlay consistent. The new hash function, depicted in Figure 12(d), requires N 180 to capture part of N 160's keys (hence also data items) between ]Golf ; Rugby]. However, other peers might still include N 160 in their finger table associated with key value Rugby. As the finger table link is unidirectional, N 160 does not know which peers are concerned, thus cannot directly inform them of its new key identifier (i.e. its new hash function). A similar problem is experienced by the default Chord overlay when a new peer joins the system and captures some keys but the existing nodes' finger table entries are not up-to-date. To address this issue, Chord uses a stabilization protocol to help peers maintain correct information about their successor, predecessor and finger table entries. By default, each node periodically runs this protocol to learn about new nodes. In our case, they also learn about new hash functions (i.e. new key identifiers).

Reference algorithm

In order to evaluate the efficiency of our solution, we also ran a series of experiments using another load balancing strategy, relying upon the migration of underloaded nodes. We chose this solution as it is commonly used [START_REF] Bharambe | Mercury: supporting scalable multiattribute range queries[END_REF], [START_REF] Konstantinou | Fast and cost-effective online loadbalancing in distributed range-queriable systems[END_REF]) and suited to the constraints of order-preserving storage systems. This mechanism is based on low overhead random sampling to create an estimate of the data value and load distribution. Basically, each peer periodically sends a probing request to another peer using random routing. This offers a global system load assessment whose values are collected into histograms maintained on peers. Using this information, a heavily loaded node can contact a lightly loaded node and request it to leave its location in the routing ring (and hence hand over its data to a neighbour) and re-join near the location of the heavy node (leave-join mechanism), to become its predecessor. Finally, the underloaded peer captures half of the keys the heavy peer (its successor) is responsible for. To perform experiments using this reference algorithm, we consider a Chord ring composed of a 1000 peers and use some of the policies presented in Table 1. We apply the overall strategy to consider a peer as overloaded and consider a peer as underloaded if its load is lower than the overall average load. The median strategy is used to determine which items should be moved by an overloaded peer. Table 4 summarises the results obtained for our experiments in a Chord overlay. When moving underloaded peers to overloaded zones (leave-join mechanism), the load is distributed over 712 peers. The amount of items moved between the peers is the highest out of all our experiments, as the underloaded peers must send their items to a neighbour before leaving their location, which increases data transfer between nodes. At the end of our experiments, 323 underloaded peers had left their initial location, which implies many links had to be repaired between the peers. Conversely, the multiple hash functions strategy did not require to modify the network topology and was able to distribute the items over more peers. The threshold strategy allows to share workload among all peers as we consider only one dimension based on the object of triples, whose value is much more distinct than the predicate value. Such perfect distribution was obtained as the volume of data to be inserted was known beforehand, which helped us estimate the perfect threshold. The goal of such experiment was to show how efficient variable hash functions can be to disseminate data in a Chord overlay. However, in practice, it might be harder to distribute data over 100% of the nodes if the amount of data to store is not known in advance. The local strategy, which measures the load of a peer's successors to decide whether to induce a rebalance or not, was able to distribute data among 806 peers. The overall strategy offers the lowest standard deviation between the 760 peers storing data at the end of experiments. These two schemes were less effective to distribute data as too low threshold/coefficient values would have caused an infinite oscillation, hence the need to use higher values that may not trigger load balancing as often as expected to obtain a perfect distribution.

Results

For all these strategies, the number of triples to move and the number of hash functions changes were higher than those obtained when using a CAN overlay, for several reasons. First, the better distribution among peers consequently involves more triples to be moved between peers. More importantly, triples are moved from successor to successor, as they have to apply the new hash function, which may lead them to rebalance their load as well. Finger tables, that would help save some hops, are not updated as quickly and hence are not as efficient as usually. Finally, in a CAN overlay, a hash function update is propagated on the whole dimension, which means many peers may potentially benefit from this change. Indirectly, a single overloaded peer may prevent many other peers from being overloaded when asking them to modify their hash function, and hence these peers will not need to initiate their own update later on. In our Chord approach, such saving is impossible and each overloaded peer has to trigger its own hash function update.

Conclusion

When storing highly skewed values in an order-preserving manner, the distribution of data among peers is consequently highly skewed as well. Since hash functions are at the heart of data distribution in DHT-based overlays, we proposed to address this issue by allowing an overloaded peer to modify the hash function it applies on data, so that it can reduce the interval of values it is responsible for. This results in the coexistence of several different hash functions used by different peers. In order to maintain optimal routing and consistency in the overlay, we have shown that it is not necessary for all the peers to use the same hash function as long as some rules are observed. To our knowledge, this is the first load balancing solution for structured overlays based on the coexistence of multiple order-preserving hash functions to improve data dissemination. To evaluate the effectiveness of this solution, we simulated an overlay composed of 1000 peers and injected 1 000 000 highly skewed RDF triples (Semantic Web data). Results have shown that the number of peers storing data is 2 out of 1000 when using no load balancing strategy. When implementing this multiple hash functions solution, up to 945 peers store data at the end of experiments. We also compared our solution with a well-known strategy consisting in adding a peer at the location of an overloaded node. Our solution appeared more efficient to disseminate the load and also less costly regarding the amount of data to move to achieve balance. We performed our experiments on both CAN and Chord overlays but we believe that the use of multiple hash functions could be applied to other DHT-based overlays. Likewise, we only used RDF data in our experiments but the same principles could be followed with any other Unicode-encoded data representation (e.g. key-value pairs, tuples).

  (a) Example of a 2-dimensional Unicode CAN storing items in the form of < attribute 0 ; attribute 1 >. Dimension 0 is dedicated to attribute 0 values and dimension 1 to attribute 1 values. (b) Standard hash function on dimension 0.

Figure 1

 1 Figure 1 Standard hash function of a CAN, that can be used to determine the CAN coordinate between [0; 1] to be associated with a Unicode value (between [A; Z]).

  Figure 1(b)). For instance, "G" corresponds to coordinate 0.25 on the hash function graph, which means this value is managed by p2 on dimension 0 because its interval is [0.25; 0.5[.

Figure 2

 2 Figure 2 Default hash function inefficient to disseminate data items (represented as black dots at the top-left corner of the CAN).

Figure 3

 3 Figure 3 Possible enlargement of the interval for Latin Unicode data storage, in order to disseminate skewed values over several peers while still dedicating a part of the overlay to other Unicode scripts.

  (a) Extension on both dimensions (dots represent data items). (b) Non-standard hash function to place data items over the enlarged area for skewed values (highlighted on the graph).

  (a) Load imbalance between p1 and p2.(b) Even data distribution after p1 has induced an hash function update.

Figure 5

 5 Figure 5 Hash function update message routing in a 2-dimensional CAN overlay.

  (c), peers p1, p5, and p6 own two different intervals: respectively [[V ; Z]; [A; M [] for p6 and [[V ; Z]; [A; G[] for p1 and p5. Therefore, when a peer is responsible for two Unicode intervals, the first interval must stop at U max and the second one must start at U min .

Figure 6

 6 Figure 6 Unicode reduction process on the Omax bound.

  (a) p7 gets overloaded.

  Figure 6(c), if, later, p1 wants to reduce from G to Y , it would no longer be responsible for two Unicode intervals (only [V ; Y [), but its neighbour p2 would ([[Y ; Z]; [A; M []).

Figure 7

 7 Figure7Inconsistent reductions for two bounds on the same coordinate (0.5).

Figure 8

 8 Figure8Routing process in an overlay using different hash functions.

Figure 9

 9 Figure 9 3-dimensional CAN for RDF data storage.

Figure 10

 10 Figure 10 Insertion of RDF triples using an order-preserving storage technique.

Figure 11

 11 Figure 11 Load distribution depending on the strategy used.

  (a) Standard CAN. (b) CAN with peers iteratively added at the most loaded location.

Table 1

 1 Load balancing policies used during our experiments. "Load state" refers to how a peer checks whether it should induce a rebalancing or not, and "Limit" describes how the new Unicode interval of an overloaded peer is calculated.

	Strategy Load State: p overloaded if	Limit: new value of U max p
	Internal load p > 8000 (CAN) or 1000 (Chord) Unicode value of p's 8000 th
			(CAN) or 1000 th (Chord) item
	Median n/a	Value of p's median item
	Local	load p > (30000+avg neighbours load) Value of p's item at position
			corresponding	to	avg
			neighbouring load (including
			load p )
	Overall load p > overall avg load ×15

Table 2

 2 Data dissemination over peers and cost of each load balancing strategy to achieve balance.

	Strategy	Peers	Changes	Items moved Cycles to	Standard
		storing	of	hash		achieve	deviation
		data	function		balance
	None	2	0		0	n/a	235702
	Add peers	407	0		9334233	n/a	1487
	Internal	652	156		10333076	80	1618
	Local	818	170		5153092	100	2675
	Overall&Median 602	90		4626023	45	1900

Table 3

 3 Variation regarding the data distribution when using different load balancing policies. This table shows the number of peers (out of 1000) storing data at the end of experiments depending on how a peer evaluates its load state, associated to how an overloaded peer defines its new Unicode interval ("Load to move").

	P Move P P Load to P	P P	Load State P P P P P P P Estimation Internal	Local	Overall
	Internal		652	433	508
	Local		715	818	945
	Median		672	577	602

Table 4

 4 Load balancing results for each strategy applied on a Chord ring.

	Strategy	Peers	Changes	Items moved Peers moved Standard
		storing	of	hash			deviation
		data	function
	None	2	0		0	0	235702
	Leave-join	712	0		30938483	323	1438
	Internal	1000	1328		23589693	0	743
	Local	806	1874		23098537	0	6353
	Overall&Median 760	1339		21313525	0	1141

She received a MSc in Databases and a MSc in Computer Science applied to Business Management from the University of Nice Sophia-Antipolis project manager in the private sector. He is a member of SCALE, a joint research group between


Maroun Geryes

Sébastien Ménigot

Walid Hassan

Ali Mcheick

Jamal Charara

Jean-Marc Girault

Sebastien Ménigot

Detection of Doppler Microembolic Signals Using High Order Statistics

Keywords: Signal processing, micro-embolic detection, standard detection, skewness, kurtosis. 1

come   L'archive ouverte pluridisciplinaire

Introduction

Sudden intensity increases in the Transcranial Doppler (TCD) signal are majorly interpreted as signatures resulting from cerebral emboli. The passage of cerebral emboli through blood ves-sels feeding the brain could result in blockage of these vessels and consequently lead to Stroke; the second cause of mortality worldwide. Embolic strokes constitute up to 14% of all strokes [START_REF] Murtagh | Cardioembolic stroke[END_REF]. Therefore, embolic strokes represent a major death threat and thus the early detection of the smallest micro-emboli is an important issue for which robust solutions must be found. This early detection would be a basis for early stroke diagnosis and thus avoiding its occurrence. Nowadays, TCD is considered the most effective embolic stroke diagnosis system.

Although the characteristics and physical nature of embolic signals, in the TCD signal, have been well defined, the task of detecting embolic and particularly small micro-embolic signals still poses a tough challenge. The gold standard method of detecting the passage of emboli is the audible detection of the sudden 'chirp' or 'moan' produced by emboli as well as the visual detection of the time-frequency representation (spectrogram) generated on the TCD screen. A main limitation of the gold standard is the inability to audibly detect micro-embolic signals located at the systolic phase due to temporal and frequency masking effects in audio files.

The standard signal processing method of detecting embolic signals, is based on calculating the energy from the spectrogram and applying constant thresholds to pick up the emboli which, according to Rayleigh theory [START_REF] Mccord | Theoretical acoustics[END_REF] , backscatter ultrasound energy higher than that backscattered by the surrounding blood. The major limitations in standard techniques reside in the inability of detecting small micro-embolic signals having lower intensities than the surrounding background blood mainly at the systolic peak.

As a purpose to detect the smallest micro-emboli, many research works have been carried out. We list some of the most punctual methods. Frequency filtering methods were introduced in [START_REF] Markus | Improved automated detection of embolic signals using a novel frequency filtering approach[END_REF] and [START_REF] Hugh | Frequency filtering improves ultrasonic embolic signal detection[END_REF]. The study reported high detection sensitivity and specificity rates. Subsequently, an online automated embolic signal detection algorithm based on frequency filtering was developed in [START_REF] Cullinane | Evaluation of new online automated embolic signal detection algorithm, including comparison with panel of international experts[END_REF] and [START_REF] Cullinane | Online automated detection of cerebral embolic signals from a variety of embolic sources[END_REF]. The latter system showed high performances in terms of sensitivity and specificity for particular cases (post carotid endarterectomy). However, in other conditions (Arterial Fibrilation) the system's sensitivity and specificity severly decreased. Moreover, the system's performance in the detection of low energy micro-embolic signals was arguably less efficient with much lower sensitivity and specificity. Methods based on detection of sudden changes were introduced in [START_REF] Girault | Micro-emboli detection: an ultrasound doppler signal processing viewpoint[END_REF]. Non-parametric detection methods mainly the Fourier, WignerVille and wavelet approaches were compared to parametric auto-regressive methods. The new parametric methods were proven to be highly performant and efficient in the detection of small micro-emboli. However, the methods were tested on synthetic simulated Doppler signals and never on a set of real signals. Another highly productive wavelet-based system was established in [START_REF] Marvasti | Online automated detection of cerebral embolic signals using a wavelet-based system[END_REF]. The system achieved a high combination of sensitivity and specificity. However, the system's rates decreased in the case of low energy micro-embolic signals. A remarkable offline detection was proposed in [START_REF] Fan | Automated embolus identification using a rule-based expert system[END_REF]. The system had excellent performance for emboli having high intensities relative to background blood clutter. However, to be noticed that the study did not take into consideration the detection of weak embolic signals. The authors in [START_REF] Aydin | Embolic doppler ultrasound signal detection using discrete wavelet transform[END_REF] introduced another highly achieving detection procedure based on the discrete wavelet transform (DWT). DWT allowed major increases in specificity and sensitivity. Nonetheless, a major deficiency of the DWT implementation was the reduced frequency resolution at low frequency scales, in which embolic signals are mostly found. In [START_REF] Chen | Doppler embolic signal detection using the adaptive wavelet packet basis and neurofuzzy classification[END_REF], the authors proposed embolic detection using the adaptive wavelet packet basis and neurofuzzy classification. The ad-aptive wavelet packet basis was used to make a sparse representation of Doppler ultrasound blood flow signals. The method produced highly accurate and robust performances. However when compared to other methods only the sensitivity was taken into account and the correlated specificity was not calculated. The study submitted in [START_REF] Genc ¸er | Embolic doppler ultrasound signal detection via fractional fourier transform[END_REF] requested the use of Fractional Fourier Transform rather than the Short Time Fourier Transform; the standard method of detection in TCD systems. The results showed that discriminating parameters based on the Fractional Fourier Transform help easier analysis and detection of embolic signals. Despite of its simplicity and acceptable results, this method was not proven reliably decent for the detection of the smallest micro-emboli. The method proposed in [START_REF] Lueang-On | Processing time improvement for automatic embolic signal detection using fuzzy c-mean[END_REF], achieved very high sensitivity and specificity but large detection errors occurred due to small gaseous emboli exhibiting small reflected signals.

In most articles previously introduced, the main limitation lies in the fact that the information on which the detection takes place is time-varying while the threshold used is constant. To match between the time-varying information and the threshold, two solutions can be proposed. The first is proposing a time-varying threshold as in [START_REF] Girault | Synchronous detector as a new paradigm for automatic microembolus detection[END_REF][START_REF] Ménigot | Automatic detection of microemboli by means of a synchronous linear prediction technique[END_REF] that matches with the time-varying trend of the decision information. Second is proposing a constant threshold that matches with the decision information for which the time-varying trend is removed.

In this work, the methods we proposed of matching between a constant threshold and an energy free of its time varying trend are based on the use of high order statistic (HOS) of windowed Doppler energy signal. We tend to prove the skewness and kurtosis as two solid means to detect micro-embolic signals when asymptomatic caroid artery patients are monitored with a Holter TCD.

The Offline Micro-Embolic Detection Unit

As previously mentioned, our objective is to perceive a micro-emboli detector more sensitive and robust regarding most standard detectors.

In this study, the typical off-line signal processing unit is decomposed into 3 units:

• Unit A, allocated for loading the wave file, 10-second signal segmentation, Short Time Fourier Transform (STFT) calculation and instantaneous energy calculation from the STFT;

• Unit B, allocated for standard energy detection on the energy signal obtained in Unit A;

• Unit C, allocated for the new energy detection techniques based on skewness and kurtosis calculation of the energy signal obtained in Unit A ;

h!][h!]

Unit A: Doppler signal extraction, STFT and instantaneous energy calculation

The different systems that we want to test, depicted in Figure ??, share a common structure. From the SD card plugged out from the Holter system and plugged into the personal computer, the Doppler signal is picked up and put in memory. From this Doppler digital signal, the short time Fourier transform is calculated, first to display the spectrogram and second to estimate instantaneously the Doppler energy. Calculations of the STFT and the instantaneous energy are carried out repetitively on 10 second segments extracted from the Doppler signal. Most commercial TCD ultrasound systems are based on the Short Time Fourier Transform. The Short Time Fourier Transform is an adapted form of the Fourier transform that analyzes only a small segment of the signal at a time; a technique called windowing of the signal or also Windowed Fourier Transform (WFT). Short Time Fourier Transform is used when the Doppler signal within the analyzing window is stationary. In reality, transforming data into the frequency domain results in loss of time information. By applying the Fourier transform of a signal, it is impossible to identify when a particular event takes place. The STFT was thus proposed to correct this deficiency. The STFT maps a signal into a two-dimensional function of time and frequency. This representation is known as the spectrogram.

The STFT frequency estimator with a sliding window can be formally written as:

S(t, f ) = x(τ)w * (t -τ) exp -j2π f t dτ 2 , (1)
where x(t) is the analyzed Doppler signal, w(t) is a sliding window and * stands for complex conjugation. When using the STFT to process embolic signals, it is of great importance that the STFT parameters are optimized. The three processing parameters are the window size, the window type and the overlap ratio. Despite the fact that setting the parameters significantly affects the embolus detection system based on STFT calculations, little work on the effect of the different parameters has been reported. A fundamental work was reported in [START_REF] Aydin | Optimization of processing parameters for the analysis and detection of embolic signals[END_REF]. The authors evaluated the effect of varying the three parameters on embolic signal temporal and frequency resolutions, time of embolic signal onset and on the power of the embolus at the frequency with maximum power relative to the average power of the background intensity. Based on [START_REF] Aydin | Optimization of processing parameters for the analysis and detection of embolic signals[END_REF] and after a preliminary stage of experimental optimization of the STFT parameters, the STFT in this study is performed using a 14.6 milliseconds Hamming window with an overlap of 65%.

The instantaneous energy at a fixed time t can be obtained from STFT frequency estimators in equation ( 1) by:

e(t) = S(t, f )d f , (2)
Note that the energy returned by a microembolus would be greater than that returned by billions of red blood cells (RBCs), since a microembolus is often larger than RBCs. Hence, the backscattered energy would function as a solid indicator from which the presence of embolic and micro-embolic signatures could be detected. This justifies why most detectors are chosen to be mainly based on energy criteria.

Unit B: Standard micro-embolic detection

The standard detection methods, to which we compare the new proposed methods, are based on a direct detection of the embolic signatures in the energy signal. An empirical threshold is commonly used. This constant threshold can be fixed empirically by the trained user for the entire examination. It is patient-, operator-, and device-dependent. This threshold is set above the maximal background energy of the Doppler signal when no embolus is present [START_REF] Bernd Ringelstein | Consensus on microembolus detection by tcd[END_REF] ; i.e. the systolic peak. The micro-embolic standard detection based on a constant threshold is represented in Figure 1 a).

The main limitation of using such method resides in comparing the energy which is timevarying, to a constant threshold. To match between the time-varying trend of the energy and the threshold, two solutions can be proposed: either a time-varying threshold as in [START_REF] Ménigot | Automatic detection of microemboli by means of a synchronous linear prediction technique[END_REF][START_REF] Girault | Cerebral Microembolism Synchronous Detection with Wavelet Packets, chapter 4[END_REF][START_REF] Girault | Synchronous detector as a new paradigm for automatic microembolus detection[END_REF] that matches with the time-varying trend of the decision information or a constant threshold that matches with the energy while removing the time-varying trend.

Unit C: Skewness and kurtosis-based micro-embolic detection

As previously mentioned, it is a threshold-oriented detection. As shown in Fig. 1 weak embolic events are impossible to detect with a constant threshold. One way to overcome this issue is to remove the time-varying trend in the instantaneous Doppler energy. To prove that high order statistic such as the skewness and the kurtosis are suitable candidates to overcome this limitation, consider a Doppler signal free of micro-embolic events and assume that the statistical distribution remains unchanged whatever the time position is even if the mean µ i (t) and the variance σ i 2 (t) vary with time. Suppose there exists two Gaussian random variables X(t 2 ) = N(µ 1 (t 2 ), σ 1 (t 2 )) and X(t 3 ) = N(µ 2 (t 3 ), σ 2 (t 3 )). It can be shown for the skewness S that S(t 2 ) = S(X(t 2 )) = S(X(t 3 )) = 0 and for the kurtosis K that K(t 2 ) = K(X(t 2 )) = K(X(t 3 )) = 3. In this example the skewness and the kurtosis are stationary since S(t) = 0 and K(t) = 3 for all t. This outcome can be verified whatever the distribution form while it remains unchanged over all time values. The only change occurs in the value of the skewness and the kurtosis but not in their stationarity. Consequently, when a micro-embolic event occurs at a time position t 1 , the distribution changes. The direct consequence is S(t 1 ) = S(t 2 ) and K(t 1 ) = K(t 2 ).

Therefore, we can propose a new detector based on calculating the skewness and kurtosis from the energy signal. The calculations are performed using a sliding window g(t) where the optimal window length and overlap ratio are set during a training phase (see Results section).

The skewness is the third order standardized moment. When calculated instantaneously (by the sliding window) on the energy it is given by the following equation:

S(t) = E[e(t) -µ e (t)] 3 σ e (t) 3 . ( 3
)
The kurtosis is the fourth order standardized moment. When calculated instantaneously on the energy it is given by the following equation:

K(t) = E[e(t) -µ e (t)] 4 σ e (t) 4 , (4)
where µ e (t) and σ e (t) are the instantaneous mean and standard deviation of the energy while E[] denotes the expected value.

The micro-embolic detection based on the skewness and kurtosis signals is represented in Figure 1 b) and c).

In order to complete the detection on the skewness and kurtosis signals, a threshold has to be set in order to pick up the peak signals. We decided to establish a data-based threshold for the skewness and kurtosis signals from their respective means µ s and µ k and respective standard deviations σ s and σ k . This threshold is defined as λ s = µ s + mσ s for skewness and λ k = µ k + mσ k for kurtosis, where m is a parameter whose value is adjusted using an optimization training phase in a manner that increases the system's sensitivity and specificity (refer to Results section). The thresholds are represented in Figure 1 b) and c).

Figure 1: a) The Doppler energy signal. An empirical threshold is applied to obtain the microembolic standard detection. b) Skewness signal calculated from the windowed energy signal. A data-based threshold is applied to complete the micro-embolic detection. The mean value of the skewness signal is 0.7 c) Kurtosis signal calculated from the windowed energy signal. A databased threshold is applied to complete the micro-embolic detection. The mean value of the kurtosis signal is 3.2. Moreover, we choose in b) and c) three time positions: t 1 = 0.72s during which an embolus is present, and t 2 = 4.7s and t 3 = 8.8s when no embolus is present. We detect in the case of absence of embolus: S(t 2 ) ≈ S(t 3 ) ≈ 0.7 and K(t 2 ) ≈ K(t 3 ) ≈ 3.2 while in the presence of embolus: S(t 1 ) = 2.8 = S(t 3 ) ≈ 0.7 and K(t 1 ) = 11 = K(t 3 ) ≈ 3.2 3 The Holter system and the Protocol TCD is a non-invasive, non-ionizing, inexpensive, portable and safe technique, which renders it as a convenient tool for the detection of cerebral micro-emboli. Long time probe positioning and the short effective examination duration are the main limitations of traditional TCD systems. The Transcranial Holter (TCD-X, Atys Medical, Soucieu en Jarrest, France) shown in Figure 2 allows prolonged patient monitoring (higher than 5 hours) with the patient no longer attached to a TCD and does not need to be laying on a bed, but rather can be monitored under naturalistic conditions. The Holter is equipped with a robotized automatic probe that helps find the best TCD signal and tracks it automatically during the whole recording.

A database obtained from the Centre Hospitalier Régionale Universitaire (CHRU) de Lille (2 Avenue Oscar Lambret, 59000 Lille, France) is used. Informed consent for Holter monitoring was obtained from all monitored patients. The recordings were acquired from the middle cerebral artery of the patients. The ultrasonic wave frequency was 1.5 MHz, the pulse repetition frequency (PRF) was 6.4 kHz and the ultrasound power was 50 mW /cm 2 .

After the clinical examination, an analogous conversion is performed on the Doppler digital signal and then the Doppler signal is sent to a loudspeaker. From the audible Doppler signal and from the spectrogram displayed on a screen, we detect and count manually the number of micro-embolic events in order to constitute our gold standard of detection. The gold standard is subject to inter agreement between three experts of our laboratory. Then, the positions in time of audibly and visually agreed-on micro-embolic events are noted. This gold standard is used to assess the results of the different detectors used and validate their performances. Although, the gold standard detections obtained from experts and non-experts might be the same as stated in [START_REF] Chung | Detection of doppler embolic signals: psychoacoustic considerations[END_REF], the experience of the latter experts was useful to distinguish between micro-embolic signals and artifact signals discussed next. We should also point out that listening to the audio files is made at the normal playing speed and another time at half the normal speed which allows us to detect micro-emboli previously inaudible due to the well-known temporal and frequency masking effects in audio files.

Results

The different detectors are tested through algorithms we developed using the numerical calculation software Matlab (Mathworks, Natick, MA, USA). Our database is composed of 18 recorded signals divided into two categories. The first is the training phase (8 signals) dedicated to determine the best settings of the detectors used. The second is the testing phase (10 signals) dedicated to assess the performances of the detectors used under the optimal settings determined in the training phase.

Two parameters are used to evaluate the detectors:

• Sensitivity or (Detection Rate) calculated as the number of true positive detections / the number of gold standard detections. True positive detection refers to the detection of an embolus recorded in the gold standard.

• Specificity calculated as 1 -False Alarm Rate (FAR) the latter FAR being the number of false positive detections / the total number of detections. False positive detection refers to the detection of an embolus not recorded in the gold standard or in other words an embolus which has not crossed the sample volume.

Training phase results

Since the threshold applied on the energy signal to achieve the standard detection, is empirically set through the choice of the user, different micro-embolic detections could be obtained. To overcome this we initialize a training phase to pre-set the best empirical threshold to be used in the testing phase. 3 to 9 dB values are used. Table 1 shows the empirical threshold that best maximizes the sensitivity and specificity. Moreover, since the skewness and kurtosis calculations are performed using a sliding window g(t) on the energy signal, an experimental test on the training phase signals is initialized to determine the optimal length of the window g(t) and the optimal overlap ratio. The optimal temporal window length is 7.3 milliseconds and the optimal overlap used is 95%. Also, using these settings we test in the training phase the best data-based threshold λ s = µ s + mσ s and λ k = µ k + mσ k for the skewness and kurtosis signals respectively. Values of m ranging between 3 and 7 are tested. Table 1 shows the data-based threshold for the skewness and kurtosis signals that best maximizes the sensitivity and specificity.

Testing phase results

Table 2 represents the testing phase results for the three different energy detectors. For the standard energy detector with empirical threshold, the sensitivity is 65% and the specificity is 60%. For the energy detector based on skewness calculation the sensitivity is 78% and the specificity is 91%.

For the energy detector based on kurtosis calculation the sensitivity is 80% and the specificity is 90%.

The results presented, show that the new detectors are able to significantly increase the specificity compared to standard detection (more than 30%). Moreover, the sensitivity achieved by the new detectors is increased by 13 % for the skewness detector and 15% for the kurtosis detector compared to that achieved by standard detectors. These results assert the accuracy and superiority of the detection based on skewness and kurtosis calculation of the Doppler energy signal over the standard detection applied directly on the Doppler energy signal.

Discussion

The results obtained were clear. The methods based on HOS over-passed by far the standard method based on the second order statitics. The reason explaining such superiority lies in the HOS sensitivity in modifying the distribution form. Knowing, that the occurrence of a microembolus superimposed on the Doppler energy signal imposes changes in the distribution of this signal, we propose to use the skewness and kurtosis as new tools for micro-embolus detection. During embolus-free periods the Doppler energy signals' distribution is fixed and its skewness and kurtosis are never altered. They do not show any variations. However, in the presence of a microembolus superimposed on the energy signal, the skewness and kurtosis signals are altered and the embolus is attributed with a peak whose peakedness level is higher than all the other points of the signal. This detection can outperform standard methods. After being tested on a set of real signals, the skewness and kurtosis-based detection offered significant improvements including very high specificity reaching up to 91% and 90% respectively compared to 60% achieved by the standard method. In addition, the sensitivity is increased from 65% for standard methods to 78% and 80% for skewness and kurtosis-based detectors respectively. Consequently, we can affirm that skewness and kurtosis can offer a robust and more reliable detection than standard detection methods and thus can be considered as new techniques for enhancing micro-embolic detection systems.

In view of the fact that we have proposed 2 detectors, one based on skewness detection and the other on kurtosis detection, it is convenient to give note that the two detectors perform very similarly and yield very close results. The only difference that could be observed is that the kurtosis signal displays small fluctuations around the embolic peak detected while the skewness signal fluctuates more strongly around the embolic peaks. This provides the kurtosis detection with a small advantage in terms of the detection threshold which can be more easily and robustly set.

Conclusion

In this research study, we propose two detectors based on the calculation of the skewness and kurtosis of the Doppler energy signal, as a tool for an enhanced cerebral micro-embolus detection. Compared to the standard detector where the detection is performed directly on the energy signal, the skewness and kurtosis-based detectors allow increasing both the sensitivity and the specificity.

This study emphasizes that standard micro-embolic energy detectors with empirical threshold still pose serious difficulties for the robust detection of micro-emboli. It also shows that detectors incorporating detection based on skewness and kurtosis calculation from the energy allow a much advanced detection of micro-emboli, precursors of coming large emboli with strong stroke risks. Thus using these simple and straightforward detectors would be an additional facility boosting the efforts to reduce the occurrence of strokes.

The upcoming step would be attempting to increase the overall performance of the techniques particularly in terms of sensitivity and validating the developed algorithms on a larger database. Moreover, we are on course of including in the whole detection system, automatic artifact rejection techniques rather than using manual techniques.

Figure 2 :

 2 Figure 2: a) Robot probe and b) Holter Transcranial Doppler System (TCD-X, Atys Medical, Soucieu en Jarrest, France)

Table 1 :

 1 Training phase results of the optimal thresholds that best maximize the sensitivity and specificity for the standard energy detector, and skewness and kurtosis based detectors.

		Optimal Threshold that max-	Sensitivity	Specificity
		imizes the sensitivity and spe-	(%)	(%)
		cificity
	Standard Energy Detector	5 dB	67%	58%
	Skewness Detector	λ s = µ s + 4σ s	76%	91%
	Kurtosis Detector	λ k = µ k + 5σ k	77%	91%

Table 2 :

 2 Results (Sensitivity and Specificity) for the standard energy detector and the new detectors based on skewness and kurtosis calculations of the Doppler energy signal.

	Detector Type	True Positive	False Positive	Sensitivity	Specificity
				(%)	(%)
	Gold Standard Detections=136
	Standard Detection	88	58	65	60
	Skewness Detection	106	10	78	91
	Kurtosis Detection	109	12	80	90

Article published in Computational and Mathematical Methods in Medicine Volume

(2016), Article ID 3243290, 8 pages. DOI: 10.1155/2016/3243290

Acknowledgments

This research was financially supported by the Doctoral School of Sciences and Technology, Lebanese University, Lebanon, the National Council for Scientific Research CNRS, Lebanon and the French Institute of Health and Medical Research INSERM, France.

The authors would like to sincerely thank Marilys Almar and Benoit Guibert for the Holter TCD equipment. They also acknowledge Corinne Gautier for the Holter Doppler recordings.

Conflict of interest

The authors declare that there is no conflict of interest regarding the publication of this paper.


Hélène Urien

Irène Buvat

Nicolas Rougon

Isabelle Bloch

† Ltci

A 3D hierarchical multimodal detection and segmentation method for multiple sclerosis lesions in MRI

Keywords: Max-tree, multiple sclerosis, MRI multimodal segmentation

In this paper, we propose a novel 3D method for multiple sclerosis segmentation on FLAIR Magnetic Resonance images (MRI), based on a lesion context-based criterion performed on a max-tree representation. The detection criterion is refined using prior information from other available MRI acquisitions (T2, T1, T1 enhanced with Gadolinium and DP). The method has been tested on fifteen patients su↵ering from multiple sclerosis. The results show the ability of the method to detect almost all lesions. However, the algorithm also provides false detections.

Introduction

In this paper, we present a new method to detect and segment lesions from MRI images of patients su↵ering from multiple sclerosis. The method is based on a hierarchical approach, where the image is represented by a tree depicting the relationship between all the connected components of all the thresholded versions of the image. The nodes of the tree represent the potential lesions, and are selected only if they satisfy a criterion based on the di↵erence between the lesion and the surrounding intensities. Our method was tested on the fifteen training datasets given by the MICCAI MSSEG challenge, providing di↵erent MRI acquisitions for each patient (FLAIR, T2, T1, T1 enhanced with Gadolinium and DP). The detection is first performed on FLAIR, and then refined using the other available modalities. Parameter setting is given and results are discussed.

A 3D multiple sclerosis lesion detection method using a hierarchical approach

The lesion detection is based on the hypothesis that the FLAIR intensity of a lesion is higher in a lesion than in the surrounding region. This assumption was verified on the lesions extracted from the manual consensus segmentations performed using the LOP STAPLE algorithm [START_REF] Akhondi-Asl | A Logarithmic Opinion Pool Base STAPLE Algorithm for the Fusion of Segmentations With Associated Reliability Weights[END_REF], considering the average FLAIR intensity in the segmented region and in a neighborhood. The detection relies on a max-tree representation of the image [START_REF] Salembier | Antiextensive connected operators for image and sequence processing[END_REF], which highlights regions of high intensities. This method, based on the study of inclusion relationships between connected components obtained by thresholding an image at all its intensity values, has several advantages. It allows searching for potential lesions in the whole image, without any prior information about the number or localizations of lesions. Connected components are selected according to a given criterion. An example is depicted in Figure 1, where homogeneous regions, called flat zones, are illustrated by a letter identifiying a specific region, and a number corresponding to the signal intensity in each voxel of the region. The tree is oriented from the root corresponding to the flat zone of lowest intensity, to the leaves, which correspond to the flat zones of highest intensities in the image. A node N is said to be a descendant of a node M if it is higher in the tree. As an example, D is a descendant of C in Figure 1. The first step is the selection of relevant nodes according to a given criterion, composed of two terms and applied to each current node N :

I (N ) = X1 I (N ) X2(N ) (1)
The first term X1 I follows our hypothesis of di↵erence in intensities between the lesion and its surroundings:

X1 I (N ) = x N I(x) n N x C N I(x) n C N (2)
where I(x) = I FLAIR (x) is the pre-processed FLAIR intensity in a voxel x, n N the number of voxels within the region N , representing the current node N and all its descendants, and n C N the number of voxels within a contextual volume surrounding node N and all its descendants. The maximal Euclidian distance from a voxel of the contextual volume to the nearest voxel to N is set to ↵ voxels. If a node N is representative of a lesion, the criterion value X I (N ) is superior to 1.

The second term X2 depends on the location of current node N compared to the z axis. If the node is located in slices of the FLAIR image containing ventricles, we assume that the lesion tends to be near the ventricles:

X2(N ) = min x2 N,v2V d(x, v) max b2B,v2V d(b, v) (3)
where x is a voxel from the volume N composed of the current node N and all its descendants, v a voxel from the binary mask of the ventricles V , d the Euclidian distance and b a voxel from the binary mask of the brain provided in the unprocessed dataset B. Otsu's thresholding [START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF] is applied on the preprocessed T1 image segment the ventricles. If the node is not located in slices containing ventricles, we penalize small nodes:

X2(N ) = 1 n N ( 4
)
where n N is the number of voxels within region N , representing the current node N and all its descendants. The last step is the reconstruction of the image. Only the nodes with criterion value superior to 1 are taken into account. The first node to be selected is the one with the highest criterion value. All its descendants and ancestors with criterion value superior to 1 are removed from the searching list. The remaining node with the highest criterion value superior to 1 is then selected. This process is repeated until there is no node with criterion value superior to 1 in the searching list. The final image is the union of all the selected nodes filled with their descendants.

To improve the detection performance, additional constraints are used, depending on the location of the lesions with respect to brain structures, and with adaptative ranges of admissible values. These ranges are defined in a supervised way. The position of a lesion compared to brain structures is assigned to one of three categories: near the ventricles, inside the white matter, and near the cortex. Otsu's thresholding [START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF] is applied on the pre-processed FLAIR image to segment the white matter. Using an automatic thresholding is enough to roughly localize the structures of interest. The manually segmented lesions were also assigned to these three regions, according to their position. For each region, and for each available modality I, the maximal and minimal values of the criterion I were computed, as illustrated in Table 1. Moreover, the maximal and minimal values of the volume of each lesion were computed according to their position, as illustrated in Table 2. Finally, a node N is selected only if the value of the criterion I computed for all the modalities I and depending on the position of the node with respect to the brain structures falls within the intervals defined in Tables 1 and2. If so, the criterion FLAIR is assigned to this node N , which is taken into account in the image reconstruction step only if its value is superior to 1.

Results and discussion

The algorithm uses images from both pre-processed (FLAIR, T1 enhanced with Gadolinium, T2, T1, DP) and unprocessed (FLAIR and brain binary mask) datasets.

Parameter setting

In order to limit the size of the tree, while preserving contour information, the input image is first quantified on k levels. Here we used k = 20 for FLAIR images. Then the tree is created using Salembier's algorithm [START_REF] Salembier | Antiextensive connected operators for image and sequence processing[END_REF] on the quantized FLAIR image.

The maximal Euclidian distance from a voxel of the contextual volume to the nearest voxel to node N filled with all its descendants is set to ↵ = 1 voxel.

The connectivity was set to 26 to compute the max-tree. Tables 1 and2 show the minimal and maximal values of the criterion and of the volumes of manually segmented lesions according to the position of the lesion.

Preliminary results

A preliminary result is shown for one of the patients in Figure 2. The algorithm manages to detect almost all lesions, but leads to an over-detection in areas of the brain which do not contain ventricles.

Conclusion

We proposed a 3D method for multiple sclerosis detection embedded in a hierarchical approach. The results show that the lesions from the manual segmentation are well included in the segmentation, but at the price of a number of false detections. The method could be improved using other contextual criteria, such as the one from [START_REF] Xu | Context-based energy estimator: Application to object segmentation on the tree of shapes[END_REF], based on the di↵erence of variance between the object of interest and its surroundings.

Fig. 1 .

 1 Fig. 1. Example of a synthetic image (a) and its corresponding max-tree (b). The root node is depicted in red, while the leaves are represented in green. Regions are identified by a letter and a number corresponding to the grey level in the region.

Fig. 2 .

 2 Fig. 2. Visual results. (a) Pre-processed FLAIR image requantized to 20 grey levels. (b) Contours of manual (in green) and automatic (in red) segmentations.

Table 1 .

 1 Ranges of values for criterion for a node, depending on the modality and the position of the node.

		Lesion near the ventricles	Lesion inside the white matter Other lesion
		Minimal value Maximal value Minimal value Maximal value Minimal value Maximal value
	Original FLAIR	1.00	1.50		1.00	1.50	1.00	1.50
	Pre-processed FLAIR 1.00	1.50		1.00	1.50	1.00	1.50
	Pre-processed T2	0.90	2.00		0.90	2.00	1.00	2.00
	Pre-processed T1	0.50	1.50		0.80	1.50	0.70	1.00
	Pre-processed T1 Gado 0.50	1.50		0.80	1.50	0.70	1.00
	Pre-processed DP	0.90	1.50		0.90	1.50	1.00	1.50
	Lesions near the ventricles	Lesions inside the white matter Other lesions
	Minimal value Maximal value Minimal value Maximal value Minimal value Maximal value
	Volume (mm 3 ) 3.85		6.44 10 4	3.02		2.28 10 3	9.07	807

Table 2 .

 2 Ranges of values of node volume (mm 3 ) depending on the position of the node.