Serge Abiteboul

Émilien Antoine

Julia Stoyanovich
email: stoyanovich@drexel.edu

The Webdamlog System Managing Distributed Knowledge on the Web *

We study the use of WebdamLog, a declarative high-level language in the style of datalog, to support the distribution of both data and knowledge (i.e., programs) over a network of autonomous peers. The main novelty of WebdamLog compared to datalog is its use of delegation, that is, the ability for a peer to communicate a program to another peer.

We present results of a user study, showing that users can write WebdamLog programs quickly and correctly, and with a minimal amount of training. We present an implementation of the WebdamLog inference engine relying on the Bud datalog engine. We describe an experimental evaluation of the WebdamLog engine, demonstrating that WebdamLog can be implemented efficiently. We conclude with a discussion of ongoing and future work.

Introduction

A number of works have argued for developing a holistic approach to distributed content management, e.g. P2P Content Warehouse [START_REF] Abiteboul | Managing an XML warehouse in a P2P context[END_REF], Dataspaces [START_REF] Franklin | From databases to dataspaces: a new abstraction for information management[END_REF] and Data rings [START_REF] Abiteboul | The data ring: Community content sharing[END_REF]. The goal is to facilitate the collaboration of autonomous peers towards solving content management tasks. Such situations arise for instance in personal information management (PIM), which is often given as an important motivating example [START_REF] Franklin | From databases to dataspaces: a new abstraction for information management[END_REF]. In [START_REF] Abiteboul | The data ring: Community content sharing[END_REF], the authors argued for founding such data exchange on declarative languages, to facilitate the design of applications, notably by non-technical users.

In the present work, we propose an approach for managing data and knowledge (i.e., programs) over a network of autonomous peers. From a system viewpoint, the different actors are autonomous and heterogeneous in the style of P2P [START_REF] Abiteboul | The data ring: Community content sharing[END_REF][START_REF] Franklin | From databases to dataspaces: a new abstraction for information management[END_REF]. However, we do not see the system we developed as an alternative to existing network services such as Facebook or Flickr. Rather, we view our system as the means of seamlessly managing distributed knowledge residing in any of these services, as well as in a wide variety of systems managing personal or social data.

Our system uses the WebdamLog language [START_REF] Abiteboul | A rule-based language for Web data management[END_REF], a declarative high-level language in the style of datalog, to support the distribution of both data and knowledge (i.e., programs) over a network of autonomous peers. In recent years, there has been renewed interest in using languages in the datalog family in a large range of applications, from program analysis, to security and privacy protocols, to natural language processing, to multi-player games. The arguments in favor of datalog-style languages are familiar ones: a declarative approach alleviates the conceptual complexity on the user, while at the same time allowing for powerful performance optimizations on the part of the system.

WebdamLog is a datalog-style language that emphasizes cooperation between autonomous peers communicating in an asynchronous manner. The WebdamLog language extends datalog in a number of ways, supporting updates [9], distribution [3], negation [START_REF] Abiteboul | Diagnosis of asynchronous discrete event systems: datalog to the rescue! In PODS[END_REF], and, importantly, a novel feature called delegation [START_REF] Abiteboul | A rule-based language for Web data management[END_REF]. As a result, WebdamLog is neither as simple nor as beautiful as datalog. It is also more procedural, which is needed to capture real Web applications with the peers' knowledge evolving over time.

We illustrate by example (Section 2) that the language (formally recalled in Section 3) is indeed well adapted to specifying realistic distributed content management tasks, notably in PIM. Our technical contributions are described in the following sections:

• We present results of a user study, showing that users can write WebdamLog programs quickly and correctly, and with a minimal amount of training (Section 4).

• We present an implementation of the WebdamLog engine relying on the Bud datalog engine (Section 5). Our implementation supports novel linguistic features such as peer and predicate variables and rule delegation.

• We describe an experimental evaluation of the WebdamLog engine (Section 6).

We discuss related work in Section 7, outline future research directions and conclude in Section 8.

Running example

Suppose that Alice and Bob are getting married, and their friends want to offer them an album of photos in which the bride and groom appear together. Such photos may be owned by friends and family members of Alice and Bob. Owners of the photos may store them on a variety of services and devices, including, e.g., desktop computers, smartphones, Picasa, and Flickr.

Making a photo album for Alice and Bob involves the following steps: (1) Identify friends of Alice and Bob using Facebook and Google+; (2) Find out where each friend keeps his/her photos and how to access them; (3) From among all photos that are obtained, select those that feature both Alice and Bob, using, e.g., tags or face recognition software; and (4) Ask Sue, a friend of Alice, to verify that the selected photos are appropriate for the photo album and to possibly exclude some from this album.

As should be clear from the example, such a task would be much more manageable if it were executed automatically. Its execution involves a certain amount of simple reasoning on the part of the system, which can be naturally specified with declarative rules. For example, for Step (1), the following WebdamLog rule computes the union of Alice's and Bob's Facebook contacts in a relation allFriends on Sue's peer:

[rule at sue] allFriends@sue($name) :-friends@aliceFB($name) allFriends@sue($name) :-friends@bobFB($name) using wrappers to Facebook for Alice and Bob.

In general, a peer name such as aliceFB or sueIPhone denotes a system or a device associated to a particular URL. Also a relation name such as friends or contacts denotes the name of a relation or a service on the corresponding system/device.

For simplicity, we assume that a person's name, e.g. alice, corresponds to the name of the peer that the particular friend uses as entry point to the Webdam system. (This name is thus associated to a particular URL.) We assume that each such peer keeps localization data for the corresponding person. For instance, relation photoLocation in that peer tells where (i.e., at which peers) this person keeps her photos. The following rule, at peer sue, delegates Steps (2) and (3) of the photo album task to the peers corresponding to the peers corresponding to her friends:

[rule at sue] album@sue($photo,$name) :-allFriends@sue($name), photoLocation@$name($peer), photos@$peer($photo), features@$peer($photo,alice), features@$peer($photo,bob)

The key feature of this rule is the use of the WebdamLog language to share the work. Let Dan be a friend, and so a possible source. Then Sue's peer will delegate the following rule to Dan's peer:

[rule at dan] album@sue($photo,dan) :-photoLocation@dan($peer), photos@$peer($photo), features@$peer($photo,alice), features@$peer($photo,bob)

Now suppose that Dan uses both Picasa and Flickr. Then, Dan's peer will delegate to danPicasa (a wrapper for Dan's account on Picasa) the following rule:

[rule at danPicasa] album@sue($photo,dan) :photos@danPicasa($photo), features@danPicasa($photo,alice), features@danPicasa($photo,bob)

and similarly for Flickr. Note how the tasks are automatically shared by many peers. Observe that when new friends of Alice or Bob are discovered (e.g., proposed by some known friends), Sue's album, which is defined intentionally, is automatically updated. Observe also that, to simplify, we assume here that all peers use a similar organization (ontology). This constraint may easily be removed at the cost of slightly more complicated rules. Now consider Step (4) in the photo album task. Sue may decide, for instance, that photos of the couple from Dave's Flickr stream are inappropriate, and that Dave should be excluded from the set of sources. Such manual curation by Sue may be accomplished by modifying the definition of allFriends:

[rule at sue] allFriends@sue($name) :-friends@aliceFB($name), not blocked@sue($name) allFriends@sue($name) :-friends@bobFB($name) not blocked@sue($name)

By inserting/removing facts in blocked@sue, Sue now controls who can participate. A similar control can also be added at the photo or photo location level.

Observe that updates result in modifying the programs running at the participating peers. For instance, the sets of rules at the various peers evolve, controlled by Sue's updates as well as by the discovery of new friends of Alice or Bob, and of new sources of photos. Consequently, the album evolves as well. We will use the example of this section throughout the paper to demonstrate the salient features of our approach.

The WebdamLog Language

[at p] $R@$P($U):-(¬) $R1@$P1($U1),. . . , (¬) $Rn@$Pn($Un)

where $R, $Ri are relation terms, $P, $Pi are peer terms, $U, $Ui are vectors of terms. The following safety condition is imposed: that $R and $P must appear positively bound in the body and each variable occurring in a negative literal must also appear positively bound in the body. In addition, rules are required from left to right and it is also required that each peer name $Pi must be positively bound in a previous atom. Semantics. At a particular point in time, each peer p has a state consisting of some facts, some rules specified locally, and possibly of some rules that have been delegated to p by other peers. Peers evolve by updating their base of facts, by sending facts to other peers, and by updating their delegations to other peers. So, both the set of facts and the set of delegated rules evolve over time. (To simplify, we follow [START_REF] Abiteboul | A rule-based language for Web data management[END_REF] in assuming that the set of rules specified locally is fixed.)

The semantics of a rule with head m@p(u) in a peer p ′ depends on the nature of the relation in its head: whether it is extensional (m@p in E) or intentional (m@p in I), and whether it is local (p=p ′ ) or not. We first consider rules in which all relations occurring in the body are local; we call such rules local rules. A subtlety lies in the use of variables for peer names. The nature of a rule may depend on the instantiation of its variables, i.e., one instantiation of a particular rule may be local, whereas another may not be.

We distinguish 5 cases identified by a letter in which we classify the rules.

A. Local rule with local intentional head (datalog)

These rules define local intentional predicates, as in classic datalog.

B. Local rule with local extensional head (local database updates

) Facts derived by this kind of rules are inserted into the local database. Note that, by default, like in Dedalus[9], facts are not persistent. To have them persist, we use rules of the form m@p(U) :m@p(U). Deletion can be captured by controlling the persistence of facts.

The two previous kinds of rules, containing only predicates of the local peer, do not require network communication, and are not affected by problems due to asynchronicity of the network.

C. Local rule with non-local extensional head (messaging)

Facts derived by rules of this kind are sent to other peers. For example, the rule:

[at mi] $m@$p($name, ""Happy birthday! ′′ ") :today@mi($date), birthday@mi($name, $m, $p, $date)

where mi stands for my iPhone, results in sending a Happy Birthday message to a contact on the day of his birthday. Observe that the name $p of the peer and the name $m of the message varies depending on the person.

D.

Local rule with non-local intentional head (view delegation) Such a rule results in installing a view remotely. For instance, the rule [at mi] boyMeetsGirl@gossipsite($girl, $boy) :girls@mi($girl, $loc), boys@mi($boy, $loc) installs a join of two mi relations at gossipsite. Finally we consider non-local rules.

E. Non-local (general delegation) Consider the rule

[at mi] boyMeetsGirl@gossipsite($girl, $boy) :girls@mi($girl, $loc), boys@ai($boy, $loc)

where ai stands for Alice's iPhone. This results in installing, at gossipsite, a view t r@mi and a rule, defined as follows:

[at mi] t r@mi @ai($girl, $loc) :girls@mi($girl, $loc) [at ai] boyMeetsGirl@gossipsite($girl, $boy) :t r@mi @ai($girl, $loc), boys@ai($boy, $loc)

Note that both rules are now local. Note also that, when girls@mi changes, this modifies the view at Alice's iPhone, possibly changing the semantics of boyMeetsGirl@gossipsite.

In [START_REF] Abiteboul | A rule-based language for Web data management[END_REF], we formally define the semantics of WebdamLog. We show that, unless all peers and programs are known in advance, delegation strictly increases the expressive power of the model. If they are known in advance, delegation does not bring any extra power. Of course, delegation is also useful in practice, because it enables obtaining logic (rules) from other sites, and deploying logic (rules) to other sites. Conditions for systems to be deterministic are shown in [START_REF] Abiteboul | A rule-based language for Web data management[END_REF], and are extremely restrictive. Even in the absence of negation, a WebdamLog system will typically not be deterministic because of asynchronicity.

Usability of WebdamLog

We argued in the introduction that WebdamLog can be used to declaratively specify distributed tasks in a variety of applications, including personal data management. We conducted a user study to demonstrate the usability of WebdamLog in this particular domain.

Participants. We recruited 27 participants for the user study. We present a break-down of results by two groups.

Group 1 consisted of 16 participants with training in Computer Science. Among them, 5 had basic database background, and 4 were familiar with advanced database concepts, including datalog. The group had the following break-down by highest completed education level: 2 high school, 3 BS, 9 MS, and 2 PhD.

Group 2 consisted of 11 participants with no CS training, and with the following break-down by highest completed education level: 3 vocational school, 6 BS, 2 MS.

Study design. All participants were given a brief tutorial in which basic features of WebdamLog were explained informally, and demonstrated through examples. The tutorial took 15-20 minutes for Group 1 and 25 minutes for Group 2. Following the tutorial, all participants were asked to take a written test. The test consisted of three problems that tested comprehension of different features of WebdamLog, including local and non-local rules, rules with variable relation and peer names, and delegation. In the tutorial and the test, we did not make an explicit distinction between intentional and extensional relations, and we ignored recursion.

The user study test had the following contents, reproduced here literally, apart from formatting.

Problem 1. Consider the following relations and facts.

schema: songs(fileName,content) // the same at all peers songs@lastFM("song1.mp3", "...") songs@lastFM("song2.mp3", "...") songs@lastFM("song3.mp3", "...") songs@pandora("song4.mp3", "...") songs@pandora("song5.mp3", "...")

1. Write one or several rules that copy all songs from lastFM and Pandora into relation songs at peer myLaptop.

2. Suppose now that relation peers@myLaptop contains names of peers on which to look for music. You can assume that each peer stores songs in a relation called songs, with the same schema as above. Write a WebdamLog program that copies songs from all peers into songs@myLaptop.

3. Write a rule that copies songs from songs@myLaptop into the songs relation on each peer whose name is listed in peers@myLaptop.

Problem 2. Consider the following relations and facts.

schema: friends(friendName) photos(fileName,content) inPhoto(fileName, friendName) friends@facebook("ann") friends@facebook("sue") friends@facebook("zoe")

Assume that photos and inPhoto relations at all peers have the same schema. Consider now the following WebdamLog rule. photos@myLaptop($X,$Z) :-friends@facebook($Y), photos@$Y($X,$Z), inPhoto@$Y($X,"jane")

1. Explain in words what this rule computes.

2. List the facts in that are in photos@myLaptop after the rule above is executed.

3. List the facts that are in photos@myLaptop if the following rule is executed instead:

photos@myLaptop($X,$Z) :-friends@facebook($Y), photos@$Y($X,$Z), inPhoto@$Y($X,"jane"), inPhoto@$Y($X,"sue")

Problem 3. Recall the example from the tutorial, in which we looked at subscribing the peer myLaptop to CNN news. This example is reproduced below.

schema: news@cnn(text) news@myLaptop(source, text) subscribers@cnn(peer) news@cnn("US Olympic gold") news@cnn("Higgs boson seen in action") subscribers@cnn("myLaptop") [at cnn] news@$X("cnn", $Y) :-subscribers@cnn($X), news@cnn($Y)

Suppose that you would now like to receive CNN news on peer myPhone, and to store them in relation news, with the schema source,text. Describe at least 1 method for doing this. You may assume that you can add rules at peers cnn, myLaptop and myPhone, and that you can insert facts into relations on any of these peers.

Results. The results of the study were very encouraging. Group 1. On Problem 1, 3 participants received a score of 2.5 out of 3, while 13 participants received a perfect score. All participants received a perfect score on Problem 2. Problem 3 was open-ended, and all participants gave at least one correct answer. 4 participants gave 3 correct answers, 4 gave 2 correct answers (2 of these also gave 1 incorrect answer each), and the remaining 8 participants each gave 1 correct answer.

We also asked participants to record how long it took them to answer each problem, in minutes. Problem 1 took between 2.5 and 6 minutes, Problem 2 between 2 and 9 minutes, and Problem 3 between 1 and 8 minutes. We did not observe any correlation between the time it took to answer questions and the participant background in data management or even datalog.

Group 2. On Problem 1, the average score was 2.3, with the following break-down: 6 participants received a perfect score, 3 received 2 out of 3, 1 had a score of 1, and 2 were not able to solve the problem. On Problem 2, 10 participants received a perfect score and 1 got a score of 2 out of 3. On Problem 3, 1 gave 5 good answers, 6 gave 3 good answers, 3 gave 2 good answers, and 2 gave no correct answer. The same two participants failed to answer Problems 1 and 3.

The test took longer for the participants without CS training. Problem 1 took between 6 and 8 minutes to solve in this group, Problem 2 took between 5 and 8 minutes, and Problem 3 took between 4 and 12 minutes. Remark. We considered alternative ways in which a user can interact with a WebdamLog system. We are currently developing an interface in which users will be able to write Web-damLog programs, but will also have access to customizable canned queries implementing common functionality. A SQLbased approach is not a natural choice, since SQL does not accommodate distribution, which is central to WebdamLog.

In summary, all technical and the majority of non-technical participants of our study were able to both understand and write WebdamLog programs correctly, with a minimal amount of training. We observed a difference between the technical and non-technical groups in terms of both correctness and time to solution. Two members of the non-technical group were able to understand WebdamLog programs but were not able to write programs on their own. We believe that this issue will be alleviated once an appropriate user interface becomes available.

The WebdamLog System

In this section, we describe the architecture of the WebdamLog system. We describe the implementation of the system, stressing the novel features compared to standard datalog engines.

System architecture

Figure 1 shows the architecture of a WebdamLog peer. Facts and rules are stored in a persistent store. The WebdamLog engine, described in greater detail in the remainder of this section, retrieves these facts and rules to process updates and answer queries coming from the top layers. The Security module provides facilities for standard access control mechanisms such as encryption, signatures and other authentication protocols. The Communication module is responsible for exchanging facts and rules with other peers.

Datalog evaluation has been intensively studied, and several open-source implementations are available. We chose not to implement yet another datalog engine, but instead to extend an existing one. In particular, we considered two open-source systems that are currently being supported, namely, Bud [START_REF] Project | Bloom programming language[END_REF] from Berkeley University and IRIS [19] from Innsbruck University. The IRIS system is implemented in Java and supports the main strategies for efficient evaluation of standard local datalog. The Bud system is implemented in the Ruby scripting language, and initially seemed less promising from a performance viewpoint. However, Bud provides mechanisms for asynchronous communication between peers, an essential feature for WebdamLog.

In absence of a real performance comparison, the choice was not easy. We finally decided in favor of Bud, both because of its support for asynchronous communication, and because its scalability has been demonstrated in real-life scenarios such as Internet routing.

WebdamLog computation in Bud

The Bud system supports a powerful datalog-like language introduced in [8]. Indeed, we see Bud (and use it) as a distributed datalog engine with updates and asynchronous communications.

A WebdamLog computation consists semantically of a sequence of stages, with each stage involving a single peer. Each stage of a WebdamLog peer computation is in turn performed by a three-step Bud computation, described next. Note that we use the word stage for WebdamLog and step for Bud: The 3 steps of a WebdamLog stage are as follows:

1. Inputs are collected including input messages from other peers, clock interrupts and host language calls.

2. Time is frozen; the union of the local store and of the batch of events received since the last stage is taken as an extensional database, and a Bud program is run to fixpoint.

3. Outputs are obtained as side effects of the program, including output messages to other peers, updates to the local store, and host language callbacks.

Observe that a fixpoint computation is performed at Step 2 by the local datalog engine (namely the Bud engine). This computation is based on a fixed program with no deletion over a fixed set of extensional relations. In Step 3, deletion messages may be produced, along with updates to the set of rules and to the set of extensional relations (for different reasons, which we will explain further). Note that all this occurs outside the datalog fixpoint computation.

Relations appearing in the rules are implemented as Bud collections. Bud distinguishes between three kinds of key-value sets:

1. A table keeps a fact until an explicit delete order is received.

We use tables to support WebdamLog extensional relations.

2. A scratch is used for storing results of intermediate computation. We use scratch collections to implement Web-damLog local intentional relations. It is emptied at Step 1 and receives facts during fixpoint computation at Step 2.

3. A channel provides support for asynchronous communications. It records facts that have to be sent to other peers. We use channels for that and in particular for messages related to installing or removing delegations.

As in WebdamLog, facts in a peer are consumed by the engine at each firing of the peer (each stage). To make facts persistent, they have to be re-derived by the peer at each stage. This is captured in our implementation by assuming that rules rederive extensional facts implicitly, unless a deletion message has been received.

We observe a subtle point that lead us to not fully adopt the original semantics of WebdamLog, as described in [START_REF] Abiteboul | A rule-based language for Web data management[END_REF]. There, we assumed for simplicity that messages are transmitted instantaneously. This assumption is not realistic in practice, and does not hold in our implementation. Since communications are asynchronous, there is no guarantee in WebdamLog as to when a fact written to a channel will be received by a remote peer.

Implementing WebdamLog rules

We now describe how WebdamLog rules are implemented on top of Bud. We distinguish between 4 cases. This brings us to revisit the semantics of WebdamLog (from Section 3) with a focus on implementation. As in Section 3, whether a rule in a peer p is local (i.e., all relations occurring in the rule body are p-relations) plays an important role. We consider 4 cases. The last case (Case F) focuses on the use of variables for relation and peer names. For the first 3 cases, we ignore such variables.

A-B-C. Simple local rules. In this cases, i.e., local rules with either an extensional relation or a local intentional relation in the head, WebdamLog rules can be directly supported by identical Bud rules. (This takes care of local deduction as in datalog (A), messages for local updates (B) and messages to other peers (C).)

D. Local with non-local intentional head.

From an implementation viewpoint, this case is more tricky. We illustrate it with an example. Consider an intentional relation s0@q defined in the distributed setting by the following two rules:

[at p1] s0@q(X, Y) :-r1@p1(X, Y) [at p2] s0@q(X, Y) :-r1@p2(X, Y)

Intuitively, the two rules specify a view relation s0@q at q that is the union of two relations r1@p1 and r1@p2 from peers p1 and p2, respectively. Consider a possible naive implementation that would consist in materializing relation s0 at q, and having p1 and p2 send update messages to q. Now suppose that a tuple 0, 1 is in both r1@p1 and r1@p2. Then it is correctly in s0@q. Now suppose that this tuple is deleted from r1@p1. Then a deletion message is sent to q, resulting in wrongly deleting the fact from s0@q.

The problem arises because the tuple 0, 1 originally had two reasons to be in s0, and only one of the reasons disappeared. To avoid this problem, we could use the provenance of the fact 0, 1 in s0@q.

A general approach for tracking provenance in our setting, and to using it as basis for performance optimizations, is part of ongoing work, and is outlined in Section 5.5. For now, we can implement the following Bud rules at p1, p2 to correctly support the two rules:

[at p1] s0p1@q(X, Y):-r1@p1(X, Y) [at p2] s0p2@q(X, Y):-r1@p2(X, Y) [at q] s0@q(X, Y):-s0p1@q(X, Y) [at q] s0@q(X, Y):-s0p2@q(X, Y) Note that relations s0p1 and s0p2 may be either intentional, in which case the view is computed on demand, or extensional, in which case the view is materialized.

E. Non-local rules.

We consider non-local rules with extensional head. (Non-local rules with intentional head are treated similarly.) An example of such a rule is:

[at p] r0@q(X0):-r1@q1(X1),. . . ,ri@qi(Xi),. . . with q1= . . . = qi-1 = p, qi = q = p, and with each Xj denoting a tuple of terms. If we consider atoms in the body from left to right, we can process at p the rule until we reach ri@q(Xi). Peer p does not know how to evaluate this atom, but it knows that the atom is in the realm of q. Therefore, peer p rewrites the rule into two rules, as specified by the formal definition of delegation in WebdamLog:

[at p] mid@q(X mid ) :-r1@p(X1),. . . ,ri-1@p(Xi-1) [at q] r0@q(X0) :mid@q(X mid ), ri@q(Xi),. . . where mid identifies the message, and notably encodes, (i) the identifier of the original rule, (ii) that the rule was delegated by p to q, and (iii) the split position in the original rule. The tuple X mid includes the variables that are needed for the evaluation of the second part of the rule, or for the head. Observe that the first rule (at p) is now local. If the second rule, installed at q, is also local, no further rewriting is needed. Otherwise, a new rewriting happens, again splitting the rule at q, delegating the second part of the rule as appropriate, and so on.

Observe that an evolution of the state of p may result in installing new rules at q, or in removing some delegations. Deletion of a delegation is simply captured by updating the predicate guarding the rule. Insertion of a new delegation modifies the program at q. Note that in Bud the program of a peer is fixed, and so adding and removing delegations is a novel feature in WebdamLog. Implementing this feature requires us to modify the Bud program of a peer. This happens during Step 1 of the WebdamLog stage.

F. Relation and peer variables. Finally, we consider relation and peer variables. In all cases presented so far, Web-damLog rules could be compiled statically into Bud rules. This is no longer possible in this last case. To see this, consider an atom in the body of a rule. Observe that, if the peer name in this atom is a variable, then the system cannot tell before the variable is instantiated whether the rule is local or not. Also, observe that, if the relation name in this atom is a variable, then the system cannot know whether that relation already exists or not. In general, we cannot compile a WebdamLog rule into Bud until all peer and relation variables are instantiated.

To illustrate this situation more precisely, consider a rule of the form: r0@p(X0):-r1@p($X), . . . ,$X@p(Xi),. . . , where r0@p is extensional and $X is a variable. This particular rule is relatively simple since, no matter how the variable is instantiated, the rule falls into the simple case B. However, it is not a Bud rule because of the variable relation name $X.

Note that WebdamLog rules are evaluated from left to right, and a constraint is that each relation and peer variable must be bound in a previous atom. (This constraint is imposed by the language.) Therefore, when we reach the atom $X@p(Xi), the variable $X has been instantiated.

To evaluate this rule, we use two WebdamLog stages of the peer. In the first stage, we bind $X with values found by instantiating r1@p($X). Suppose that we find two values for $X, say t1 and t2. We always wait for the next stage to introduce new rules (there are two new rules in this case). More precisely, new rules are introduced during Step 1 of the WebdamLog computation of the next stage. In the example, the following rules are added to the Bud program at p: r0@p(X0):-t1@p(Xi),. . . , r0@p(X0):-t2@p(Xi),. . . , Observe that, even in the absence of delegation, having variable relation and peer names allows the WebdamLog engine to produce new rules at run time, possibly leading to the creation of new relations. This is a distinguishing feature of our approach, and is novel to WebdamLog and to our implementation.

This example uses a relation name variable. Peer name variables are treated similarly. Observe that having a peer name variable, and instantiating it to thousands of peer names, allows us delegating a rule to thousands of peers. This makes distributing computation very easy from the point of view of the user, but also underscores the need for powerful security mechanisms. Developing such mechanisms is in our immediate plans for future work.

Running the fixpoint

The Bud engine evaluates the fixpoint using the semi-naive algorithm, i.e., Bud saturates one stratum after another according to a stratification given by the dependency graph. The dependency graph is a directed hyper-graph with relations as nodes, and with a hyper-edge from relations si to relation r if there is a rule in which all si appear in the body and r appears in the head. Since this is classic material, we omit the details but observe that, since WebdamLog rules may be added or removed at run-time, the program evolves, leading to changes in the dependency graph. Therefore, the dependency graph is recomputed at step 1 of a WebdamLog stage when receiving new rules, and remains fixed for the following step 2. The Web-damLog engine pushes further the differentiation technique that serves as basis of the semi-naive algorithm.

Although, according to WebdamLog semantics, facts are consumed and possibly re-derived, it would be inefficient to recompute the proof of existence of all facts at each stage. Between two consecutive stages, each relation keeps a cache of its previous contents. This cache may be invalidated by WebdamLog if a newly installed rule creates a new dependency for this relation. Note that Bud already performs cache invalidation propagation for facts, which we adapt to fit WebdamLog semantics. This incremental optimization across stages allows us to run the fixpoint computation only on the relations that may have changed since the previous stage.

Maintaining dynamic peer state

A WebdamLog system executes in a highly dynamic environment, where peer state frequently changes, in terms of both data and program, and where peers may come and go. This is a strong departure from datalog-based systems such as Bud that assume the set of peers and rules to be fixed. As part of our ongoing work, we are focusing on efficiently supporting dynamic changes in peer state, with the help of a novel kind of a provenance graph.

We use provenance graphs to record the derivations of Web-damLog facts and rules, and to capture fine-grained dependencies between facts, rules, and peers. We build on the formalism proposed in [START_REF] Green | Provenance semirings[END_REF], where each tuple in the database is annotated with an element of a provenance semiring, and annotations are propagated through query evaluation. Provenance can be used for a number of purposes such as explaining query results or system behavior, and for debugging. Our primary use of provenance is to optimize performance of WebdamLog evaluation in presence of deletions. We are also currently investigating the use of provenance for enforcing access control and for detecting access control violations.

Experimental Evaluation

The goal of the experimental evaluation is to verify that Web-damLog programs can be executed efficiently. We show here that rewriting and delegation can be implemented efficiently.

In the experiments, we used synthetically generated data. All experiments were conducted on up to 50 Amazon EC2 micro instances, with 2 WebdamLog peers per instance. Micro-instances are virtual machines with two process units, Intel(R) Xeon(R) CPU E5507 @2.27GHz with 613 MB of RAM, running Ubuntu server 12.04 (64-bit). All experiments were executed 4 times with a warm start. We report averages over 4 executions.

The cost of delegation. We now focus is on measuring WebdamLog overhead in dealing with delegations. Recall the Bud steps performed by each peer at each WebdamLog stage, described in Section 5.2. We can break down each step into WebdamLog-specific and Bud-specific tasks as follows: We report the running time of WebdamLog as the sum of Steps 1b, 2b and 3a, and the running time of Bud as the sum of Steps 1a, 2a, 2c and 3b. All running times are expressed in percentage of the total running time, which is measured in seconds. For each experiment, we will see that the running time of WebdamLog-specific phases is reasonable compared to the overall running time.

Non-local rules. In the first experiment, we evaluate the running time of a non-local rule with an extensional head. Rules of this kind lead to delegations. We use the following rule:

[at alice] join@sue($Z) :-rel1@alice($X,$Y), rel2@bob($Y,$Z) This rule computes the join of two relations at distinct peers (rel1@alice and rel2@bob), and then installs the result, projected on the last column, at the third peer (join@sue). Relations rel1@alice and rel2@bob each contain 1 000 tuples that are pairs of integers, with values drawn uniformly at random from the 1 to 100 range. In the next The portion of the overall time spent on WebdamLog computation on alice is fairly high: 10.8%. This is because that peer's work is essentially to delegate the join to bob. Peer bob spends most of its time computing the join, a Bud computation. Peer sue has little to do. As can be seen from these numbers, the overhead of delegation is small.

Relation and peer variables. In the second experiment, we evaluate the execution time of a WebdamLog program for the distributed computation of a union. The following rule uses relation and peer variables and executes at peer sue: [at sue] union@sue($X) :-peers@sue($Y,$Z), $Y@$Z($X)

The relation peers@sue contains 12 tuples corresponding to 3 peers (including sue) with 4 relations per peer. Thus, the rule specifies a union of 12 relations. Each relation participating in the union contains 1 000 tuples, each with a single integer column, and with values for the attribute drawn independently at random between 1 and 10 000. Observe that sue does most of the work, both delegating rules and also computing the union. The WebdamLog overhead is 9.9%, which is still reasonable. The running time on remote peers is very small, and the WebdamLog portion of the computation is negligible.

WebdamLog

QSQ-style optimization. In this experiment, we measure the effectiveness of an optimization that can be viewed as a distributed version of query subquery (QSQ) [START_REF] Vieille | Recursive Axioms in Deductive Databases: The Query/Sub-query Approach[END_REF], where only the relevant data are communicated at query time. More precisely, we consider the following view union2 on peer sue, defined as the union of two relations.

[at sue] union2@sue($name,$X) :-friendPhotos@alice($name,$X) union2@sue($name,$X) :-friendPhotos@bob($name,$X) Suppose we want to obtain the photos of Charlie, i.e. the tuples in union2 that have the value "Charlie" for first attribute. We vary the number of facts in friendPhotos@alice and friendPhoto@bob that match the query. We compare the cost of materializing the entire view to answer the query to that of installing only the necessary delegations computed at query time to compute the answer.

Results of this experiment are presented in Figure 2. We report the waiting time at sue. As expected, QSQ-style optimization brings important performance improvements (except when almost all facts are selected). This shows its usefulness in such a distributed setting.

Related work

The WebdamLog language is motivated by previous work on the WebdamExchange system [START_REF] Abiteboul | A model for web information management with access control[END_REF]. The system described there could automatically adapt to a variety of protocols and access methods found on the Web, notably for localizing data and for access control [START_REF] Antoine | Demo] Social Networking on top of the Web-damExchange System[END_REF]. In developing toy applications with Web-damExchange [START_REF] Antoine | Demo] Social Networking on top of the Web-damExchange System[END_REF], we realized the need for a logic that could be used (i) to declaratively specify applications and (ii) to exchange application logic between peers. This motivated the introduction of WebdamLog [START_REF] Abiteboul | A rule-based language for Web data management[END_REF], a language based on rules that can run locally and be exchanged between peers.

Distributed data management has been studied since the earliest days of databases [START_REF] Özsu | Principles of Distributed Database Systems[END_REF]. The fact that it is possible to access data from several data sources has been studied under various names, notably multi-databases or federated databases. The setting we consider is in the spirit of peer-to-peer databases with autonomous and heterogeneous data sources. Of course, standard query optimization techniques developed for distributed database systems are relevant here. We insist in particular on the techniques that are more relevant to our setting, which is based on datalog. One should mention that there have been a number of works on parallel or distributed evaluation of datalog, e.g., [2,[START_REF] Houtsma | Distributed transitive closure computations: The disconnection set approach[END_REF].

The use of declarative languages, in particular datalog extensions, for distributed data management has already been advocated, e.g., in [3,[START_REF] Abiteboul | The data ring: Community content sharing[END_REF]. There has recently been renewed interest in this approach [START_REF] Hellerstein | The declarative imperative: experiences and conjectures in distributed logic[END_REF]. Several systems have been developed based on the declarative paradigm [14, [START_REF] Loo | Implementing declarative overlays[END_REF][START_REF] Loo | Declarative networking: language, execution and optimization[END_REF], with performance comparable to that of systems based on imperative languages. Our implementation uses the Bud system [START_REF] Project | Bloom programming language[END_REF]. The language Dedalus [9] has been proposed as a formal foundation for Bud. We prefer here to use the language WebdamLog, in particular because it features delegation.

Most classic optimization techniques for datalog are relevant to our work, in particular, semi-naive evaluation that is supported by Bud. We also considered the query-subquery optimization [START_REF] Vieille | Recursive Axioms in Deductive Databases: The Query/Sub-query Approach[END_REF] as adapted to the distributed context in [2].

Conclusion

This paper presents an implementation of the WebdamLog language, introduced in [START_REF] Abiteboul | A rule-based language for Web data management[END_REF]. The two main challenges for such an approach are (i) the difficulty of writing rules for non-technical users and (ii) the difficulty to offer good performance:

• With respect to (i), we present a user study that very promisingly shows that the participants (many of them not computer scientists) are able to understand and write simple rules.

• With respect to (ii), we benefit from previous datalog optimization techniques and efficient network communication by relying on the Bud system to support the basic functionality of distributed datalog. We show that the higher level features of WebdamLog, notably delegation, can be supported efficiently using logical rule rewriting.

All this demonstrates the feasibility of an approach based on WebdamLog to support exchanges of data and rules between rapidly evolving peers in a distributed and dynamic environment.

In the future, we are considering the following directions:

Access control One of the bases of WebdamLog is that a peer can locally install rules that are specified by another peer. Clearly, this is potentially very risky. Access control is therefore of paramount importance. We plan to work on access control, and in particular investigate the use of provenance for enforcing access control and for detecting access control violations.

Interface Our user study demonstrated that WebdamLog is appropriate for specifying distributed data management tasks. We are in the process of developing a user interface for the WebdamLog system. We also plan to conduct a follow-up user study (i) drawing from a larger pool of participants, (ii) including more participants without any CS training, and (iii) testing the usability of other aspects of the language, notably intentional vs. extensional predicates.

Application We intend to demonstrate the use of our system with complete applications, e.g., for social networks and personal data management.

Optimization We are currently developing a provenance-based approach for efficiently supporting changes in program state. Also, an optimization technique based on mapreduce and intense parallelism has been proposed for datalog [START_REF] Afrati | Map-reduce extensions and recursive queries[END_REF]. It would be interesting to consider such an approach in our distributed setting.

Figure 1 :

 1 Figure 1: WebdamLog engine in a full Webdam peer

1 .

 1 Inputs are collected a) Bud reads the input from the network and populates its channels. b) WebdamLog parses the input in channels and updates the dependency graph with new rules. The dependency graph is used to control the rules that are used in the semi-naive evaluation (see Section 5.4). 2. Time is frozen a) Bud invalidates each ∆ (used by the semi-naive evaluation) that has to be reevaluated because it corresponds to a relation that may have changed. b) WebdamLog invalidates ∆ according to program updates. Moreover, WebdamLog propagates deletions. (Recall that the semi-naive evaluation deals only with tuple additions.) c) Bud performs semi-naive fixpoint evaluation for all invalidated relations, taking the last ∆ for differentiation. 3. Outputs are obtained a) WebdamLog builds packets of rules and updates to send. b) Bud sends packets.

Figure 2 :

 2 Figure 2: Distributed QSQ optimization

  table, we report the total running time of the program at each peer, as well as the break-down of the time into Bud and WebdamLog.

		WebdamLog	Bud	total
	alice	10.8%	89.2% 0.10s
	bob	4.0%	96.0% 0.87s
	sue	0.7%	99.3% 0.02s

* This work has been partially funded by the European Research Council under the European Community's Seventh Framework Programme (FP7/2007-2013); ERC grantWebdam, agreement 226513. http:// webdam.inria.fr/


Matthieu Toutain

Olivier Lezoray

Fabrice Audigié

Valeria Busoni

Giacomo Rossi

Francesco Parillo

Abderrahim Elmoataz

O Lézoray

Analysis of whole slide images of equine tendinopathy

Introduction

Tendons are dense bands of fibrous connective tissue that act as intermediary in the attachment of muscle to bone. During locomotion, they act as viscoelastic structures submitted to great tensile strength [START_REF] Mcilwraith | Diseases of joints, tendons, ligaments and related structures[END_REF]. These biomechanical properties arise from a specific spatial architecture reflecting the requirements of this tissue. The main constituents of tendons are thick, closely packed parallel bundles of longitudinally oriented collagen fibers. Cells, mainly fibroblasts and vessels, are arranged in a healthy tendon in long parallel rows in the spaces between the collagenous bundles [START_REF] Bloom | A textbook of histology[END_REF]. In sport and racing horses, the two flexor tendons of the equine hand (the superficial digital flexor tendon and the deep digital flexor one) are submitted to high forces during the stance phase of the stride. Intense and repeated stresses on these tendons can lead to overstress injuries, from simple tendonitis to rupture. Tendinopathies in sport and racing horses are a major cause of reduced performance and temporary or permanent breakdown of the athletic horse career. Up to 10 to 15% of the horse population is affected by tendinopathies, which represents a major impact of several millions euros a year. Diagnostic imaging (high resolution ultrasonography and magnetic resonance imaging) of these diseases [START_REF] Denoix | Imaging of the musculoskeletal system in horses[END_REF] has enabled major diagnosis advances during the last 15 years. Meanwhile, experimental studies have been conducted to validate the efficacy of new therapeutic approaches to improve the healing of injured tendons [START_REF] Crovace | Histological and immunohistochemical evaluation of autologous cultured bone marrow mesenchymal stem cells and bone marrow mononucleated cells in collagenase-induced tendinitis of equine superficial digital flexor tendon[END_REF].In such studies, assessment of positive effects of new treatments on the tendon healing process is frequently demonstrated using detailed histological analysis on tendon samples. However these histological analysis are based on either subjective or semi-quantitative analysis performed by an expert operator. Moreover the analysis of the entire slide of the tendon sample is particularly difficult in such an expert-based approach. Consequently, the purpose of our study is to develop an objective and quantitative method using criteria close to those used by expert operators for analyzing whole histological slides of equine tendon samples. Such an approach may be extremely useful for assessing objectively, with a non-operator dependent method, the efficacy of new tendon treatments.

Unsupervised analysis of equine tendon samples

Whole slides of Hematoxylin-Eosin (HE) stained equine tendon samples were scanned at 40× magnification using a ScanScope CS TM (Aperio R , San Diego, CA) digital microscopical scanner. To facilitate visualization and processing, scanned samples are directly stored as a multi-resolution image [START_REF] Roullier | Multi-resolution graph-based analysis of histopathological whole slide images: application to mitotic cell extraction and visualization[END_REF] where each level of resolution is an under-resolved version of the highest resolution image. The image being very large (40000 × 30000 at the highest resolution), each resolution level is split into image tiles (of size 512 × 512) in a non-overlapping layout. We take advantage of this tiled multi-resolution organization in our approach to analyzing the tendon samples. First, the lowest resolution image is processed to discriminate tissue versus background. The corresponding partition enables to retain, at the highest resolution, only tiles that contain tissue. Second, on the retained tiles, cells are extracted according to their color. Third, for each high-resolution tile, three different feature vectors are computed to reproduce visual histological criteria used to quantify tendon injury (texture, arrangement and alignment of the cells). Fourth, having tiles described by three different sets of features, a tensor-based multi-view spectral clustering is considered to discriminate the different tissue areas.

Tissue segmentation

Scanned samples contain two main elements at the lowest resolution: tendon tissue and slide background. The tendon tissue can be easily discriminated from background on the lowest resolution picture (Figure 1). Following the strategy developed in our previous works [START_REF] Roullier | Multi-resolution graph-based analysis of histopathological whole slide images: application to mitotic cell extraction and visualization[END_REF], the tiles of the lowest resolution image are processed in the following way. Each tile is simplified by weighted Laplacian regularization and a 3D color histogram is constructed from the RGB color vectors of all the tiles. This histogram is clustered with a 2-means classification (see in [START_REF] Roullier | Multi-resolution graph-based analysis of histopathological whole slide images: application to mitotic cell extraction and visualization[END_REF] for details and motivations on this whole strategy). This extraction of the tissue performs extremely fast and well, but some small tissue regions as well as holes in the segmented tissue still remain (both artifacts being due to the tendon cutting). To cope with this, we use a morphological hole filling followed by an opening by reconstruction. Figure 1 presents two results of tissue extraction on healthy and injured tendon samples. The detection of the tissue is projected on the highest level of resolution and this enables to determine the high-resolution tiles containing tissue. Only these tiles are further considered for analysis.

Extraction of cells

Several histological visual criteria assessment of equine tendinopathy rely on the shape, the arrangement, and the alignment of cells. Therefore, to be able to derive quantita- tive measures for these visual criteria, cells have to be extracted in the retained highresolution tiles inside the tissue region. To extract cells, since the coloration of slides is known (Hematoxylin-Eosin), we can separate the individual dyes. According to the Beer-Lambert law, the transmission of incident light I 0 through a specimen can be modeled as I = I 0 e -SX where I is the incident light after passing through the specimen, S the absorption factors of the dyes and X their concentrations. This can be reformulated in terms of optical density: Od = -log( I I0 ) = SX. The optical density of each RGB channel is linear with the amount of dye and can be used, given the absorption factors S, to extract the amounts of dyes X in a specimen. To achieve correct balancing of the absorption factors for separate dyes, the columns of S are normalized to unit length. Then, we obtain X = S -1 Od. This whole process is often called color deconvolution [START_REF] Ruifrok | Quantification of histochemical staining by color deconvolution[END_REF]. To summarize, we convert vectors f from the RGB color space to vectors h in a new color space comprising hematoxylin, eosin, and background channels with h = S -1 × -log( f f ). For the absorption factors, we used values from [START_REF] Ruifrok | Quantification of histochemical staining by color deconvolution[END_REF] and retain only the hematoxylin channel since this dye stains cells in blue (in our preparation of the samples, the dye is applied longer than necessary to saturate the staining). The extracted hematoxylin channel is then binarized using an automated thresholding. Figure 2 shows the segmentation of cells superimposed an initial sample image corresponding to four adjacent high-resolution tiles.

Feature Extraction

Once cells have been extracted in all the high-resolution tiles, we are in position of extracting features to describe the content of each tile with respect to histological visual criteria assessment of equine tendinopathy. Many visual criteria are used by pathologists to quantify tendinopathy, one can quote, e.g., alignment, arrangement and crimp of collagen fibers, density and shape of cells, neovascularization intensity, etc. In this paper, we have chosen to extract textural, arrangement and alignment features to quantify the different areas in the tendon tissue.

Textural features Texture is more regular when the tissue is healthy than when the tissue is injured. We chose here to describe texture with uniform gray-scale and rotation invariant Local Binary Patterns [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF] in 3 × 3 squares. From this LBP pattern, an LBP histogram is constructed for each tile of the highest resolution image. From these histograms, an N × N distance matrix denoted W (1) is computed between all the tiles of the image (N being the number of tiles) with the χ 2 distance measure :

d H (h 1 , h 2 ) = N i=1 [h1(i)-h2(i)] 2
h1(i)+h2(i) with h 1 and h 2 two histograms to compare.

Arrangement features From the extracted cells, it is important to quantify their architecture as well as density and shape. These visual features relate to neighboring properties of the cells and can be quantified using graph based techniques [START_REF] Doyle | Automated grading of breast cancer histopathology using spectral clustering with textural and architectural image features[END_REF]. To use graphs, the m cell centroids c 1 , c 2 , ..., c m in the whole slide are considered as graph vertices. From this set of vertices, specific graphs are computed on the whole slide. Figure 2 illustrates the graphs we consider. Then, for each tile, a normalized arrangement feature vector is computed from the corresponding sub-graphs. With these arrangement feature vectors, an N × N distance matrix denoted W (2) is computed between the tiles with the Euclidean distance. Features are computed as detailed below.

Voronoi Diagram -The Voronoi diagram V is composed of a set of polygons

P = {P 1 , P 2 , • • • , P m }. Any centroid c is included in polygon P a if d(c, c a ) = min j { c - c j }
where a, j ∈ {1, 2, ..., m} and cd is the Euclidean distance between any two centroids c, d. We calculate the areas of all P ∈ V , and the average and disorder are calculated for areas of all P , giving two feature values.

Delaunay Triangulation -The Delaunay graph D is constructed such that any two unique centroids c a and c b , where a, b ∈ {1, 2, ..., m}, are connected by an edge E a,b if P a and P b share a side in V . We calculate the sides lengths for all triangles in D, and take the average, disorder, and maximum of these to obtain three feature values.

Minimum spanning tree -Given a connected, undirected graph, a spanning tree S of that graph is a subgraph that connects all its m vertices with m -1 edges. Weights w E S are assigned to each edge E in each S based on the length of E in S. The sum of all weights w E S in each S is determined to give the weight ŵS assigned to each S. The minimum spanning tree (MST) denoted by S ′ has a weight ŵ′ S less than or equal to ŵS for every other spanning tree S. We calculate the average and disorder of the branch lengths in S ′ to obtain two features values.

Nuclear features -The shape of cells is also a criterion of arrangement. The shape descriptor we consider is the elongation of cells. This criteria is a major parameter in the analysis of the cell type and of its functional activity (active versus quiescent fibroblasts particularly). We calculate average and disorder of elongation values to obtain two feature values.

Alignment features Cell alignment is also a very important histological feature that describes properties of collagen fibers. To detect alignments of cells, we adapted the approach proposed in [START_REF] Vanegas | Searching aligned groups of objects with fuzzy criteria[END_REF]. Let A = {a 1 , ..., a n } be a group of points in R 2 . A is aligned iff there exists an angle θ ∈ [0, π) where for all pairs of points a i and a j (i = j), a j is in the direction θ or θ + π of a i , relatively to the horizontal axis. From the set of cell centroids on the whole slide, a nearest neighbor graph G is constructed, and weighted with the angle between two points and the horizontal axis. The dual graph G is then obtained and weighted with the difference between two edges of G. The dual graph G represents all the alignment distances (in the chosen neighborhood) between two pairs of points (a i , a j ) and (a j , a k ). The dual graph is pruned in order to keep only locally aligned sets of vertices. Therefore, only edges with a weight lower than an alignment detection threshold β are preserved:

GT H = ( Ṽ , ẼT H ) with ẼT H = {(i, j) ∈ E|ẽ ij < β}.
The connected components C k of GT H correspond to locally aligned groups of vertices (Figure 2(c)) that are a possible candidates for being globally aligned groups of vertices. To detect this, if the maximum weight (representing the degree of global alignment) of C k is higher than β, the vertex of maximum degree (the less aligned one) is suppressed and we repeat this until C k is globally aligned (under the constraint of containing at least 3 vertices). With the result of the algorithm (Figure 2(d)), we create an histogram of the angles of the detected alignments for each tile in the highest resolution image. As previously, with these histograms, an N × N distance matrix denoted W (3) is computed between all the tiles with the χ 2 distance measure.

Tensor-based multi-view spectral clustering

In the feature extraction step, textural, arrangement, and alignment feature vectors were extracted to describe tiles of the tendon tissue region. These feature vectors represent different views of the data that provide complimentary informations to each-other. In this paper, we consider a spectral clustering of the data based on some similarity measure between the data. With multiple views, we have multiple similarity matrices, and we want to perform a (spectral) clustering based on the combined representation of similarities. This is known as a multiple-view approach to clustering [START_REF]Learning with multiple views[END_REF]. Multi-view spectral clustering can be formalized as the following optimization problem:

max U K i=1 ||U T S (i) N U|| 2 F , s.t. U T U = I. ( 1
)
where K is the number of different views of the data (i.e., the number of similarity matrices), S

N is a normalized similarity matrix for the i th view constructed from the W (i) distance matrices, and U is the common factor matrix shared by the different views. Since the similarity of each view is computed in different spaces, the normalization of each similarity matrix is required. Classical single view spectral clustering is recovered for K = 1. A tensor X ∈ R N ×N ×3 is build from these three similarity matrices {S (1)

N , S (2)
N , S

N }. Multi-linear singular value decomposition (MLSVD) [START_REF] Delathauwer | A multilinear singular value decomposition[END_REF], is a form of higher-order extension of matrix singular value decomposition. It decomposes a tensor X into a tensor C multiplied by a matrix along each mode. Tensor C, known as the core tensor, is analogous to the diagonal singular value matrix in conventional matrix SVD. The matrices of each mode are called factor matrices and can be considered as a PCA of the tensor along each mode. This leads to the following (Tucker) decomposition:

X = C × 1 U 1 × 2 U 2 × U 3 where U 1 , U 2 ∈ R N ×N
and U 3 ∈ R K×K and × n is the mode-n product [START_REF] Delathauwer | A multilinear singular value decomposition[END_REF]. Given a tensor X , its matrix factors U 1 , U 2 and U 3 can be computed as the left singular vectors of its matrix unfoldings [START_REF] Delathauwer | A multilinear singular value decomposition[END_REF]. Then, we can rewrite Eq. (1) as

max U K i=1 ||U T S (i) N U|| 2 F = max U ||C × 1 U T 1 × 2 U T 2 × 3 U T 3 || 2 F , s.t. U T i U i = I ∀i. (2)
A truncated version of this formulation consists in considering [START_REF] Liu | Learning from multi-view data: clustering algorithm and text mining application[END_REF] max

U K i=1 ||U T S (i) N U|| 2 F = max U ||C × 1 U T × 2 U T × 3 I|| 2 F , s.t. U T U = I. (3)
This truncated MLSVD obtained by truncating the decomposition on the M dominant higher-order singular vectors gives in practice a good approximation of the given tensor [START_REF] Delathauwer | A multilinear singular value decomposition[END_REF]. Consequently, we take the columns of U to be the dominant 1-mode singular vectors that are equal to the dominant left M singular vectors of X (1) . The truncated MLSVD obtained does not minimize exactly Eq. ( 1) but is easier to implement and much faster. The principle of the whole algorithm is presented in Algorithm 1.

Algorithm 1 Multi-View Clustering(S (1) , S (2) , ..., S (K) , M )

1: Build a similarity tensor X from {S

N , S

N , S

N } 2: Obtain the unfolding matrix X (1) 3: Compute U from the subspace spanned by the dominant left M singular vectors of X (1) 4: Normalize the rows (ui)i=1,...,N of U to unit length 5: Cluster the points (ui) ∈ R M with the k-means algorithm into k clusters

Results

Figure 3 presents the obtained classification on two equine tendons (healthy and injured). The number of final classes is fixed to 4. Each tile is surrounded by a colored square that shows the class this tile belongs to. One tile of each class is highlighted in details on the right of each tendon slide. One can see that the classification, even fully unsupervised, performs well. Indeed, the different classes contain tiles that exhibit similar visual histological criteria in terms of cell repartition and texture. For the healthy tendon, most of the tiles are classified into only one class, assessing the fact that the tissue is almost the same everywhere. For the injured tendon, one can see a concentration of tiles (colored in magenta) that distinguish a specific area of lesion (confirmed by the experts) from the rest of the slide.

Conclusion

This work has shown that an automatic analysis of whole slide images of equine tendinopathy is possible and can be very effective as a tool for treatment quality assessment. Indeed our method is able to identify the different similar zones and can be used to monitor the lesion regression. The system can however be further enhanced. First, we plan to incorporate other visual histological criteria such as fiber crimp. It is important to note that the incorporation of new feature views of the data can be easily performed by simply adding a new similarity matrix to the tensor-based spectral clustering. Second, we plan to replace the k-means clustering by a supervised classification with the help of a ground truth classification of tiles from several images.

Fig. 1 .

 1 Fig. 1. (a) Transverse healthy superficial digital flexor tendon sample, (b) Transverse injured deep digital flexor tendon sample, (c)-(d) Segmented tissues of samples (a)-(b).

  (a) Initial sample. (b) Extracted cells. (c) Local cell alignments. (d) Global cell alignments. (e) Delaunay triangulation. (f) Minimum Spanning Tree.

Fig. 2 .

 2 Fig. 2. (a) a longitudinal healthy superficial flexor tendon sample, (b) extracted cells, (c) locally detected alignments, (d) globally detected alignments, (e)-(f) Delaunay triangulation and MST.

Fig. 3 .

 3 Fig. 3. Classification result with k = 4 on healthy (top) and injured (bottom) equine tendons with, on the right, one typical tile of each class. The color around each tile corresponds to one extracted class.


Feng Yan
email: fyan@telecom-paristech.fr

Philippe Martins
email: martins@telecom-paristech.fr

Laurent Decreusefond

Accuracy of Homology based Approaches for Coverage Hole Detection in Wireless Sensor Networks

Homology theory provides new and powerful solutions to address the coverage problems in wireless sensor networks (WSNs). They are based on algebraic objects, such as Čech complex and Rips complex. Čech complex gives accurate information about coverage quality but requires a precise knowledge of the relative locations of nodes. This assumption is rather strong and hard to implement in practical deployments. Rips complex provides an approximation of Čech complex. It is easier to build and does not require knowledge of nodes location. This simplicity is at the expense of accuracy. Rips complex can not always detect all coverage holes. It is then necessary to evaluate its accuracy. This work proposes to use the area of undiscovered coverage holes per unit of surface as performance criteria. Investigations show that it depends on the ratio of communication and sensing ranges of each sensor. Closed form expressions for lower and upper bounds of the accuracy are also derived. Simulation results are consistent with the proposed analytical lower bound, with a maximum difference of 0.4%. Upper bound performance depends on the ratio of communication and sensing ranges.

I. INTRODUCTION

Wireless sensor networks (WSNs) have attracted a great deal of research attention due to their wide potential applications such as battlefield surveillance, environmental monitoring and intrusion detection. Many of these applications require a reliable detection of specified events. Such requirement can be guaranteed only if the target field monitored by a WSN contains no coverage holes, that is to say regions of the domain not monitored by any sensor. Coverage holes can be formed for many reasons, such as random deployment, energy depletion or destruction of sensors. Consequently, it is essential to detect and localize coverage holes in order to ensure the full operability of a WSN.

There is already an extensive literature about the coverage problems in WSNs. Several approaches are based on computational geometry with tools such as Voronoi diagram and Delaunay triangulations, to discover coverage holes [START_REF] Fang | Locating and bypassing routing holes in sensor networks[END_REF]- [START_REF] Zhang | Localized algorithms for coverage boundary detection in wireless sensor networks[END_REF]. These methods require precise information about sensor locations. This substantially limits their applicability since acquiring accurate location information is either expensive or impractical in many settings. Some other approaches attempt to discover coverage holes by using only relative distances between neighboring sensors [START_REF]Detecting coverage boundary nodes in wireless sensor networks[END_REF], [START_REF] Bejerano | Simple and efficient k-coverage verification without location information[END_REF]. Similarly, obtaining precise range between neighbor nodes is costly.

More recently, homology is utilized in [START_REF] Silva | Blind swarms for coverage in 2-d[END_REF]- [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF] to address the coverage problems in WSNs. Ghrist and his collaborators introduced a combinatorial object, Čech complex (also known as nerve complex), which fully characterizes coverage properties of a WSN (existence and locations of holes). Unfortunately, this object is very difficult to construct as it requires rather precise informations about the relative locations of sensors. Thus, they introduced a more easily computable complex, Rips complex (also known as Vietoris-Rips complex). This complex is constructed with the sole knowledge of the connectivity graph of the network and gives an approximate coverage by simple algebraic calculations. As regards implementation in real WSN, these homology based methods are necessarily centralized, which makes them impractical in large scale sensor networks. Some algorithms have been proposed to implement the above mentioned ideas in a distributed context, see [START_REF] Muhammad | Control using higher order laplacians in network topologies[END_REF]- [START_REF] Dlotko | Distributed computation of coverage in sensor networks by homological methods[END_REF].

As alluded above, Rips complex can not always detect all coverage holes. For instance, in Figure 2, there exists a hole inside the triangle [START_REF] Fang | Locating and bypassing routing holes in sensor networks[END_REF][START_REF] Wang | Movement-assisted sensor deployment[END_REF][START_REF] Silva | Blind swarms for coverage in 2-d[END_REF] of the Čech complex though there is no hole in the same triangle of the Rips complex. It is thus of paramount importance to determine the proportion of missed coverage holes to assess the accuracy of Rips complex based coverage detection. In this paper, it is indicated that such proportion is related to the ratio between communication and sensing ranges of each sensor. In addition, closed form expressions for lower and upper bounds of the proportion are derived. A few papers [START_REF] Liu | A study of the coverage of large-scale sensor networks[END_REF]- [START_REF] Li | Coverage properties of the target area in wireless sensor networks[END_REF] provide some results on coverage probability but with a different point of view. This paper is organized as follows. Section II introduces the network model and the formal definition of triangular holes. Upper and lower bounds of the area of triangular holes per unit of surface for different values of the ratio of communication radius by sensing radius are computed in Section III. Simulation results are compared with theoretical computation in Section IV. Finally, Section V concludes the paper.

II. MODELS AND DEFINITIONS

A brief introduction to the tools used in the paper is given. For further readings, see [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF] and references therein. Given a set of points V , a k-simplex is an unordered set [v 0 , v 1 , ..., v k ] ⊆ V where v i = v j for all i = j. So a 0-simplex is a vertex, a 1simplex is an edge and a 2-simplex is a triangle with its interior included, see Figure 1. The faces of this k-simplex consist of all (k-1)-simplex of the form [v 0 , ..., v i-1 , v i+1 , ..., v k ] for 0 ≤ i ≤ k. A simplicial complex is a collection of simplices which is closed with respect to inclusion of faces.

Fig. 1: 0-, 1-and 2-simplex Čech complex and Rips complex are two simplicial complexes defined as follows [START_REF] Ghrist | Coverage and hole-detection in sensor networks via homology[END_REF].

Definition 1 ( Čech complex). Given a collection of sets U , Čech complex of U , Č(U ), is the abstract simplicial complex whose k-simplices correspond to nonempty intersections of k + 1 distinct elements of U . Definition 2 (Rips complex). Given a set of points X in R n and a fixed radius ǫ, the Rips complex of X , R ǫ (X ), is the abstract simplicial complex whose k-simplices correspond to unordered (k + 1)-tuples of points in X which are pairwise within Euclidean distance ǫ of each other.

Consider a collection of stationary sensors (also called nodes) deployed randomly in a planar target field. As usual, isotropic radio propagation is assumed. Each sensor monitors a region within a circle of radius R s and may communicate with other sensors within a circle of radius R c . Let V denote the set of sensor locations in a WSN and S = {s v , v ∈ V} the collection of sensing ranges of these sensors: For a location v,

s v = {x ∈ R 2 : x -v ≤ R s }.
Then, according to the definition, the Čech complex and Rips complex of the WSN, respectively denoted by ČRs (V) and R Rc (V), can be constructed as follows:

[v 1 , • • • , v k ] belongs to ČRs (V) whenever ∩ k l=1 s v l = ∅ and [v 1 , • • • , v k ] belongs to R Rc (V) whenever v l -v m ≤ R c for all 1 ≤ l < m ≤ k.
Figure 2 shows a WSN, its Čech complex and two Rips complexes for two different values of R c . Depending on the ratio R c over R s , the Rips complex and the Čech complex may be close or rather different. In this example, for R c = 2R s , the Rips complex sees the hole surrounded by [START_REF] Wang | Movement-assisted sensor deployment[END_REF][START_REF] Zhang | Localized algorithms for coverage boundary detection in wireless sensor networks[END_REF][START_REF] Bejerano | Simple and efficient k-coverage verification without location information[END_REF][START_REF] Silva | Blind swarms for coverage in 2-d[END_REF] as in the Čech complex whereas it is missed in the Rips complex for R c = 2.5R s . At the same time, the true coverage hole surrounded by [START_REF] Fang | Locating and bypassing routing holes in sensor networks[END_REF][START_REF] Wang | Movement-assisted sensor deployment[END_REF][START_REF] Silva | Blind swarms for coverage in 2-d[END_REF] is missed in both Rips complexes.

As a consequence of Rips complex definition, a hole in a Čech complex not seen in a Rips complex is bounded by a triangle. Based on this observation, a formal definition of 'triangular holes' is given as follows. It can easily be seen that there is one triangular hole in the Rips complex in Figure 2(c) and there are three triangular holes in the Rips complex in Figure 2(d). We are interested in the proportion of the area of triangular holes in a target field. Assume sensor nodes are distributed in the planar target field according to a homogeneous Poisson process with intensity λ. Because of homogeneity property, each point in the target field has an equal probability of belonging to a triangular hole. This probability in a homogeneous setting is equal to the proportion of the area of triangular holes. So we only need to compute the probability that any point belongs to a triangular hole.

III. BOUNDS ON PROPORTION OF THE AREA OF TRIANGULAR HOLES

In this section, the conditions under which any point in the target field belongs to a triangular hole are first given. From the discussion in Section II, it is found that the probability that any point belongs to a triangular hole is related to the ratio R c /R s . Three different cases are considered for the probability computation. For each case, the upper and lower bounds of the probability are derived. Let define γ = R c /R s .

A. Preliminary

Lemma 1. For any point in the target field, it belongs to a triangular hole if the following two conditions are satisfied:

1) the distance between the point and its nearest sensor is larger than R s . 2) the point is inside a triangle: the convex hull of three nodes, two by two less that R c apart.

Lemma 2.

If there exists a point O which belongs to a triangular hole, then R s < R c / √ 3. Furthermore, if l denotes the distance between O and its closest neighbor, we have

R s < l ≤ R c / √ 3.
Proof: R s < l is a direct corollary from Lemma 1. We only need to prove l ≤ R c / √ 3. If point O belongs to a triangular hole, it must be surrounded by a triangle formed by sensor with pairwise distance less than R c . Assume it is surrounded by a triangle N 0 N 1 N 2 , as in Figure 3. The closest neighbor of O is not necessarily in the set

{N 0 , N 1 , N 2 }. If l > R c / √ 3, then d 0 ≥ l > R c / √ 3, d 1 ≥ l > R c / √ 3 and d 2 ≥ l > R c / √ 3.
In addition, since ∠N 0 ON 1 + ∠N 1 ON 2 + ∠N 0 ON 2 = 2π, there must be one angle no smaller than 2π/3. Assume ∠N 0 ON 2 ≥ 2π/3 and denote it as α. Then according to the law of cosines,

d 2 02 = d 2 0 +d 2 2 -2d 0 d 2 cos α > R 2 c /3+R 2 c /3-2/3R c R c cos(2π/3) = R 2 c . So d 02 > R c . Since N 0 and N 2 are neighbors, d 02 ≤ R c . There is a contradiction. Therefore l ≤ R c / √ 3.

Fig. 3: triangular point

A Poisson point process whose intensity is proportional to the Lebesgue measure is stationary in the sense that any translation of its atoms by a fixed vector does not change its law. Thus any point has the same probability to belong to a triangular hole as the origin O. This probability in a homogeneous setting is also equal to the area of triangular holes per unit of surface. We borrow the line of proof from [START_REF] Li | Coverage properties of the target area in wireless sensor networks[END_REF] where a similar problem was analyzed.

We consider the probability that the origin O belongs to a triangular hole. Since the length of each edge in the Rips complex must be at most R c , only the nodes within R c from the origin can contribute to the triangle bounding a triangular hole to which the origin belongs. Therefore, we only need to consider the Poisson process constrained in the closed ball B(O, R c ) which is also a homogeneous Poisson process with intensity λ. We denote this process as Φ. In addition, T (x, y, z) denotes the property that three points x, y, z are within pairwise Euclidean distance R c from each other, and the origin O belongs to the triangular hole bounded by the triangle with these points as vertices. When n 0 , n 1 , n 2 are points of the process Φ, T (n 0 , n 1 , n 2 ) is also used to denote the event that the triangle constructed by the nodes n 0 , n 1 , n 2 bounds a triangular hole to which the origin belongs.

Let τ 0 = τ 0 (Φ) be the node in the process Φ which is nearest to the origin. Assume node τ 0 always contributes to the triangle bounding the triangular hole to which the origin belongs. Although it is possible that the node τ 0 does not contribute to the triangle bounding the triangular hole to which the origin belongs, this probability is very low (Simulation results show that this probability is less than 0.2% at any γ with any intensity λ), so we can neglect it. Then the probability that the origin belongs to a triangular hole can be defined as p(λ, γ) =P{O belongs to a triangular hole} =P{ {n0,n1,n2}⊆Φ

T (n 0 , n 1 , n 2 )} ≈P{ {n1,n2}⊆Φ\{τ0(Φ)} T (τ 0 , n 1 , n 2 )}
Using polar coordinates, we assume the closest node τ 0 lies on (d 0 , π). It is well known that the distance d 0 is a random variable with distribution

F d0 (r 0 ) = P{d 0 ≤ r 0 } = 1 -e -λπr 2 0 (1)
Therefore the above probability can be written as

P{ {n1,n2}⊆Φ\{τ0(Φ)} T (τ 0 , n 1 , n 2 )} = P{ {n1,n2}⊆Φ ′ r 0 T ((r 0 , π), n 1 , n 2 )}F d0 (dr 0 ) (2)
where Φ ′ r0 is the restriction of Φ in B(0, R c )\B(0, r 0 ).

B. Case 0 < γ ≤ √ 3 Theorem 1. When 0 < γ ≤ √ 3, p(λ, γ) = 0.
Proof: According to Lemma 2, if the origin O belongs to a triangular hole, then

R s < R c / √ 3. Since γ ≤ √ 3, then R s = R c /γ ≥ R c / √ 3.
There is a contradiction. So the origin O can not belong to a triangular hole.

C. Case

and

R 1 (r 0 , θ 1 ) = min( R 2 c -r 2 0 sin 2 θ 1 -r 0 cos θ 1 , R c ) Proof:
As we have assumed that the node τ 0 must contribute to the triangle bounding the triangular hole to which the origin belongs, the other two nodes must lie in the different half spaces: one in H + = R + × (0, π) and the other in H -= R + × (-π, 0). Since the distance to τ 0 is within R c , they must also lie in the ball B(τ 0 , R c ). Furthermore, the distance to the origin is less than R c and larger than d 0 , they both lie in the area B(0, R c )\B(0, d 0 ). Therefore, one node must lie in H + B(τ 0 , R c ) B(0, R c )\B(0, d 0 ) and the other node lie in H -B(τ 0 , R c ) B(0, R c )\B(0, d 0 ).

Ordering the nodes in H + B(τ 0 , R c ) B(0, R c )\B(0, d 0 ) by increasing polar angle so that τ 1 = (d 1 , θ 1 ) has the smallest angle θ 1 . Other nodes such as τ ′ 1 , τ ′′ 1 in the same region have polar angle larger than θ 1 , as illustrated in Figure 4. Assume the node τ 1 contributes to the triangle bounding the triangular hole to which the origin belongs, then the third node τ 2 ∈ H -B(τ 0 , R c ) B(0, R c )\B(0, d 0 ) must lie to the right of the line passing through τ 1 and O, denoted by H + (θ 1 ). In addition, the distance to τ 1 is less than R c . So the node τ 2 must lie in the region Fig. 4: illustration of case

√ 3 < γ ≤ 2 S -(τ 0 , τ 1 ) = S -(d 0 , d 1 , θ 1 ) = H -B(τ 0 , R c ) B(0, R c )\B(0, d 0 ) H + (θ 1 ) B(τ 1 , R c )
Here we need to obtain the density of node τ 1 . Considering the way τ 1 was defined, there should be no nodes with a polar angle less than θ 1 , that is to say no nodes are in the region

S + (τ 0 , τ 1 ) = S + (d 0 , θ 1 ) = H + B(τ 0 , R c ) B(0, R c )\B(0, d 0 ) H + (θ 1 )
Since the intensity measure of the Poisson process in polar coordinates is λrdrdθ, the density F τ1 of τ 1 can be expressed as

F τ1 (dr 1 , dθ 1 ) = λr 1 e -λ|S + (d0,θ1)| dr 1 dθ 1 (5)
The integration domain D(d 0 ) with respect to parameters (d 1 , θ 1 ) can be easily obtained. According to Lemma 2,

R s < d 0 ≤ R c / √ 3.
Thus in this case, R c = γR s ≤ 2R s < 2d 0 . It means the ball B(τ 0 , R c ) must intersect with the ball B(0, d 0 ), as illustrated in Figure 4. Furthermore,

θ 0 = 2 arccos(R c /(2d 0 )). So 2 arccos(R c /(2d 0 )) ≤ θ 1 ≤ π and d 0 < d 1 ≤ R 1 (d 0 , θ 1 ), where R 1 (d 0 , θ 1 ) = min( R 2 c -d 2 0 sin 2 θ 1 -d 0 cos θ 1 , R c
) Assume only τ 0 , τ 1 and nodes in S -(τ 0 , τ 1 ) can contribute to the triangle bounding the triangular hole to which the origin belongs, we can get a lower bound of the probability that the origin belongs to a triangular hole. It is a lower bound because it is possible that other nodes such as τ ′ 1 , τ ′′ 1 in H + B(τ 0 , R c ) B(0, R c )\B(0, d 0 ) can also contribute to the triangle bounding the triangular hole to which the origin belongs. Based on the assumption, we have

P{ {n1,n2}⊆Φ ′ r 0 T ((r 0 , π), n 1 , n 2 )} > D(r0) P{ n 2 ⊆Φ ′ r 0 S -(r 0 ,r 1 ,θ 1 ) T ((r 0 , π), (r 1 , θ 1 ), n 2 )}F τ1 (dr 1 , dθ 1 ) = D(r0) P{Φ ′ r0 (S -(r 0 , r 1 , θ 1 )) > 0}F τ1 (dr 1 , dθ 1 ) (6)
Therefore, from ( 1), ( 2), ( 5) and ( 6), the lower bound shown in (3) can be derived.

Still consider the nodes in

H + B(τ 0 , R c ) B(0, R c )\B(0, d 0 ), each node (r, θ) corresponds to an area |S -(r 0 , r, θ)|.
Maybe the corresponding area of some nodes is 0. Among all such areas, there must exist one maximum value. From Figure 4 , we can see that the closer to r 0 is r and the closer to θ 1 is θ, the larger is the area of S -(r 0 , r, θ). So we have (r 0 , θ 1 ) = arg max

r 0 ≤r≤R 1 θ 1 ≤θ≤π |S -(r 0 , r, θ)|
Then the upper bound shown in (4) can be obtained. Here we need to compute the area of S + (r 0 , θ 1 ) and S -(r 0 , r 1 , θ 1 ). In fact, the area |S + (r 0 , θ 1 )| and the area |S -(r 0 , r 1 , θ 1 )| have very similar expressions. For example, the area |S + (r 0 , θ 1 )| can be expressed as

|S + (r 0 , θ 1 )| = θ1 2 arccos Rc 2r 0 dθ R1(r0,θ1) r0 rdr = 1 2 θ1 2 arccos Rc 2r 0 R 2 1 (r 0 , θ 1 )dθ - r 2 0 2 (θ 1 -2 arccos R c 2r 0 ) When θ 1 ≤ π -arccos(r 0 /(2R c )) 1 2 θ1 2 arccos Rc 2r 0 R 2 1 (r 0 , θ 1 )dθ = I(θ 1 ) -I(2 arccos R c 2r 0 )
where

I(θ) = r 2 0 2 sin θ cos θ + R 2 c 2 θ - R 2 c 2 arcsin r 0 sin θ R c - r 0 2 sin θ R 2 c -r 2 0 sin 2 θ When π -arccos(r 0 /(2R c )) < θ 1 ≤ π 1 2 θ1 2 arccos(Rc/(2r0)) R 2
In this case, we can use the same method as in section III.C to get the upper and lower bounds. But we need to consider two situations R s < d 0 ≤ R c /2 and R c /2 < d 0 ≤ R c / √ 3. In the first situation, d 0 ≤ R c /2 means that the ball B(0, d 0 ) is included in the ball B(d 0 , R c ), see Figure 5. Then the lower limit of integration for θ 1 is 0. This is the only difference. The areas |S + (r 0 , θ 1 )| and |S -(r 0 , r 1 , θ 1 )| can be computed in the same way as presented in Section III.C. The second situation is the same as that in section III.C. So we can directly obtain the lower and upper bounds as shown in ( 7) and ( 8) respectively.

IV. SIMULATIONS AND PERFORMANCE EVALUATION

This section first introduces simulation settings. Simulation results are then presented and compared with closed form expressions for upper and lower bounds.

A. Simulation settings

A disk centered at the origin with radius R c is considered in the simulations. The probability that the origin belongs to a triangular hole is computed. Sensors are randomly distributed in the disk according to a Poisson process with intensity λ. The sensing radius R s of each node is set to be 10 meters and γ is Fig. 5: illustration of case γ > 2 chosen from 2 to 3 with interval of 0.2. So the communication radius R c ranges from 20 to 30 meters with interval of 2 meters. λ is selected from 0.001 to 0.020 with interval of 0.001. For each γ, 10 6 simulations are run under each λ to check whether the origin belongs to a triangular hole.

B. Performance evaluation

The probability p(λ, γ) obtained by simulation is presented with the lower bound and upper bound in Figure 6(a) and 6(b) respectively. It can be seen that for any value of γ, p(λ, γ) has a maximum at a threshold value λ c of the intensity.

As a matter of fact, for λ ≤ λ c , the number of nodes is small. Consequently the probability that the origin belongs to a triangular hole is relatively small too. With the increase of λ, the connectivity between nodes becomes stronger. As a result, the probability that the origin belongs to a triangular hole increases. However, when the intensity reaches the threshold value, the origin is covered with maximum probability. p(λ, γ) decreases for λ ≥ λ c . The simulations also show that λ c decreases with the increase of γ.

On the other hand, it can be seen from Figure 6(a) and 6(b) that for a fixed intensity λ, p(λ, γ) increases with the increases of γ. That is because R s is fixed. Then the larger R c is, the higher is the probability of each triangle containing a coverage hole.

Furthermore, the maximum probability increases quickly with γ ranging from 2.0 to 3.0. It is shown that when R c = 2R s the maximum probability from simulation is about 0.03% and thus it is acceptable to use Rips complex based algorithms to discover coverage holes. While the ratio R c /R s is high to a certain extent, it is unacceptable to use connectivity information only to discover coverage holes.

Finally, it can be found in Figure 6(a) that the probability obtained by simulation is very well consistent with the lower bound. The maximum difference between them is about 0.4%. Figure 6(b) shows that probability obtained by simulation is also consistent with the upper bound. The maximum difference between them is about 4%. In this paper, the proportion of the area of triangular holes in a WSN is analyzed under different ratios between communication radius and sensing radius of each sensor. Both the lower and upper bounds of the proportion are derived. When the ratio is no larger than √ 3, there is no triangular hole. When the ratio is between √ 3 and 2, both the theoretical analysis and simulation results show that the proportion is lower than 0.06% under any intensity. It means that the triangular holes can nearly be neglected and homology based coverage hole detection algorithms can work well if they can discover all non-triangular holes. When the ratio is larger than 2, the proportion of the area of triangular holes increases with γ. It becomes unacceptable for γ larger than a threshold. In that case triangular holes can not be neglected anymore.

Fig. 2 :

 2 Fig. 2: (a) a WSN, (b) Čech complex, (c) Rips Complex under R c = 2R s , (d) Rips Complex under R c = 2.5R s

√ 3 < γ ≤ 2 Theorem 2 .e -λπr 2 0e -λπr 2 0

 32222 When √ 3 < γ ≤ 2, p l (λ, γ) < p(λ, γ) < p u (λ, γ), where p l (λ, γ) × e -λ|S + (r0,θ1)| (1e -λ|S -(r0,r1,θ1)| )r 1 dr 1 × e -λ|S + (r0,θ1)| (1e -λ|S -(r0,r0,θ1)| )r 1 dr 1

2 c 2 (θ 1 - 2 Theorem 3 .×e -λπr 2 0×

 221232 1 (r 0 , θ 1 )dθ = I(πarccos(r 0 /(2R c ))) -I(2 arccos(R c /(2r 0 ))) + R π + arccos(r 0 /(2R c ))) In this way, |S + (r 0 , θ 1 )| can be derived. Similarly, |S -(r 0 , r 1 , θ 1 )| can be obtained. The detailed process is neglected due to space limitation. D. Case γ > When γ > 2, p l (λ, γ) < p(λ, γ) < p u (λ, γ), where p l (λ, γ) = 2πλ 2 2 0 × e -λ|S + (r0,θ1)| (1e -λ|S -(r0,r1,θ1)| )r 1 dr 1 e -λ|S + (r0,θ1)| (1e -λ|S -(r0,r1,θ1)| )r 1 dr 1 × e -λ|S + (r0,θ1)| (1e -λ|S -(r0,r0,θ1)| )r 1 dr 1 e -λ|S + (r0,θ1)| (1e -λ|S -(r0,r0,θ1)| )r 1 dr 1

Fig. 6 :

 6 Fig. 6: proportion of the area of triangular holes (a) simulation results and lower bounds ; (b) simulation results and upper bounds