Lamine Diop
email: diop.lamine3@ugb.edu.sn

Talibouya Diop
email: cheikh-talibouya.diop@ugb.edu.sn

Arnaud Giacometti
email: arnaud.giacometti@univ-tours.fr

Arnaud Soulet
email: arnaud.soulet@univ-tours.fr

Pattern On Demand in Transactional Distributed Databases

Keywords: Pattern mining, Knowledge base, Pattern on Demand, Pattern sampling, Outlier detection

Many applications rely on distributed databases like sensor networks or the Semantic Web. However, only few methods exist to extract patterns without centralizing the data by following the exhaustive extraction paradigm. Their principle is to extract a unique large collection of frequent patterns that will be used for all downstream applications. Unfortunately, the communication of this large collection from the different nodes is often more expensive than the database centralization. Furthermore, this rigid principle is not suited to modern data analysis where data and analyst needs change daily. It is both too expensive to repeat the exhaustive extraction for each change and it is not possible to build the ideal collection of patterns to meet all the needs.

To circumvent this difficulty, this paper revisits the problem of pattern mining in distributed databases by adopting the Pattern-On-Demand

Introduction

Context and motivation. Many applications require storage and manipulation of distributed databases [START_REF] Özsu | Principles of distributed database systems[END_REF] like large-scale wireless sensor networks [START_REF] Shen | A distributed spatial-temporal similarity data storage scheme in wireless sensor networks[END_REF] or the Semantic Web [START_REF] Berners-Lee | The semantic web[END_REF]. In most cases, the centralization of data is very costly, in particular when the databases evolve continuously since each update on a node must be reflected in the centralized database. Sometimes legal constraints also prevent this centralization [START_REF] Domadiya | Privacy preserving distributed association rule mining approach on vertically partitioned healthcare data[END_REF]. Thus, some studies including [START_REF] Zhang | Mining multiple data sources: local pattern analysis[END_REF] underline the importance of extending knowledge discovery to distributed databases. In the context of the Semantic Web, Table 1 illustrates an example of Resource Description Framework (RDF) [START_REF] Miller | An introduction to the resource description framework[END_REF] data distributed over four triplestores P = {D 1 , D 2 , D 3 , D 4 } accessible via SPARQL queries. In this context, the properties describing the entity identified by TId 1 (e.g., the singer "Youssou N'Dour") are spread over several fragments (i.e., DBpedia D 1 with the property A, and Wikidata D 2 with the properties B and C).

There exist federated systems to execute SPARQL queries on multiple triplestores [START_REF] Gombos | Federated query evaluation supported by sparql recommendation[END_REF]. Unfortunately, SPARQL is not expressive enough to directly extract patterns like frequent itemsets. By relying on a basic communication model, this paper aims at extracting patterns from a distributed database P (including RDF data) as if the data were centralized in a single dataset (see 1).

P * in Table
Pattern-On-Demand (POD). To the best of our knowledge, all the existing pattern mining methods in distributed databases [START_REF] Cheung | Efficient mining of association rules in distributed databases[END_REF][START_REF] Otey | Mining frequent itemsets in distributed and dynamic databases[END_REF][START_REF] Jin | Systematic approach for optimizing complex mining tasks on multiple databases[END_REF][START_REF] Kum | Sequential pattern mining in multidatabases via multiple alignment[END_REF] follow the exhaustive extraction paradigm. Its principle is to extract just once, a unique collection of frequent patterns that will then be used for all subsequent patternbased analyses. This rigid vision of pattern mining is hampered by : • Data change issue: In many contexts, distributed databases are constantly evolving. The pattern collection extracted today will no longer be up to date the next day. For instance, in the Semantic Web, the Wikidata knowledge base changes hourly [START_REF] Vrandečić | Wikidata: a free collaborative knowledgebase[END_REF]. Of course, it is far too costly to repeat frequent pattern extraction in a distributed database hourly.

• Needs change issue: The needs of the end user are rarely fixed. The minimum frequency threshold initially chosen risks being too large. In this case, it will be necessary to restart the extraction of frequent patterns with a lower threshold. Obviously, these repeated extractions are expensive. Of course, it would be possible to set an extremely low threshold from the first extraction, resulting in an insane communication cost and taking the risk of extracting a large quantity of patterns that will never be used.

Beyond these issues, the aforementioned methods suffer from three major technical limitations. First, they exclusively address horizontally partitioned data meaning that unlike P in Table 1, a transaction cannot be split into two fragments (see Section 3.1 for a formal definition). Second, as these proposals focused on an exhaustive extraction of patterns, the volume of data exchanged between the different fragments can be very high. In most cases, the volume of the patterns is greater than the volume of the distributed databases (especially when the minimum support threshold is low). Finally, these proposals need computing capacity on each fragment for locally mining patterns, which is often impossible. For example, in the Semantic Web, the SPARQL endpoints cannot perform routines.

To cope with these limitations, we propose to adopt the Pattern-On-Demand (POD) paradigm. Its principle is to instantly extract only the patterns that the analyst needs when he needs them. In this way, for each demand, the patterns are mined from the most recent data and according to the latest needs. For this puprpose, we benefit from pattern sampling [START_REF] Hasan | Output space sampling for graph patterns[END_REF][START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF]. Pattern sampling consists in randomly drawing a collection of patterns with a probability proportional to their interest. This technique has a low computational cost and at the same time, it is also useful in many tasks such as classification [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF], outlier detection [START_REF] Giacometti | Anytime algorithm for frequent pattern outlier detection[END_REF] or interactive data mining [START_REF] Bhuiyan | Interactive pattern mining on hidden data: a sampling-based solution[END_REF][START_REF] Dzyuba | Learning what matters-sampling interesting patterns[END_REF][START_REF] Giacometti | Interactive pattern sampling for characterizing unlabeled data[END_REF].

Contributions. In this paper, we show how to sample patterns from a transactional distributed database that can be partitioned both horizontally and vertically, without using the computing capacity of the different fragments.

Our main contributions are as follows:

• We propose a generic algorithm called Distributed Database Sampling (DDSampling) which randomly draws a pattern from a distributed database proportionally to an interestingness measure combining frequency and length-based utility functions (including length constraints). Following the pattern-on-demand paradigm, we show that the preprocessing can be quickly updated to take into account both data and needs changes.

• We demonstrate that DDSampling performs an exact sampling and analyze its complexity on average. Experiments show that DDSampling is very fast and that the communication cost of our proposal is much lower than that of data centralization for drawing a few thousand patterns. We also show that in the context of distributed databases,

DDSampling is a fault-resistant algorithm against network and node failures.

• We illustrate the interest of DDSampling on a use case by detecting outliers in two real-world triplestores: DBpedia [START_REF] Bizer | Hellmann, DBpedia -a crystallization point for the web of data[END_REF] and Wikidata [START_REF] Vrandečić | Wikidata: a free collaborative knowledgebase[END_REF].

For a given class, most of the entities with a high anomaly score should have been attached to another class. These experiments also show the importance of using a maximum length constraint and that output space sampling is more efficient than input space sampling.

This paper is an extended version of [START_REF] Diop | Pattern sampling in distributed databases[END_REF] that carries out a comprehensive experimental study of DDSampling and that integrates data and needs changes. In particular, we detail our communication model by adding a third primitive query.

This paper is structured as follows. After the related work in Section 2, Section 3 introduces basic definitions and formalizes the problem of pattern sampling in distributed databases. We detail the algorithm DDSampling in Section 4 that exactly draws patterns as if the transactional distributed database was centralized. Section 5 evaluates its performance on benchmarks datasets and Section 6 illustrates the interest of pattern sampling to detect outliers in the Semantic Web. Finally, Section 7 concludes this paper.

Related Work

This paper aims at discovering patterns in distributed databases. This problem differs significantly from the parallelization of mining algorithms [START_REF] Zaki | Parallel and distributed association mining: A survey[END_REF] where the distributed computations are operated on a single database or deliberately distributed to accelerate computation. Indeed, the pattern mining approaches based on parallel programming frameworks [START_REF] Fan | Mining big data: current status, and forecast to the future[END_REF] not only require a computing capacity on each node (where the data is available), but these nodes are inside the same local network. In such a local environment, exchanges are much less penalizing. Unfortunately, this is not the case in many application contexts where the user only has access to data from Web services (e.g., data as a service [START_REF] Hacigumus | Providing database as a service[END_REF]). For instance, in our use case on the Semantic Web (see Section 6), SPARQL access endpoints do not allow executing procedural program and are distributed on the World Wide Web.

Pattern mining in distributed databases

Several approaches in the literature focused on frequent pattern mining in distributed databases (not necessarily in the same local network). This task is complex because whatever the minimum frequency threshold userspecified on the distributed database (global frequency), it is not possible to constrain the local frequency on each fragment without communicating information between sites. In this context, [START_REF] Cheung | Efficient mining of association rules in distributed databases[END_REF] proposes the first method to extract all the globally frequent patterns by identifying the sites where the patterns are the most frequent and thus, reducing communication costs.

More drastically, [START_REF] Otey | Mining frequent itemsets in distributed and dynamic databases[END_REF] proposes to save communication costs by limiting themselves to the collection of the maximal frequent patterns. To prevent each fragment from enumerating all its patterns, [START_REF] Jin | Systematic approach for optimizing complex mining tasks on multiple databases[END_REF] imposes a minimum local frequency threshold on each fragment. From the different local extractions, [START_REF] Kum | Sequential pattern mining in multidatabases via multiple alignment[END_REF] builds an approximate global collection of frequent patterns. A centralized pruning proposed by [START_REF] Zhu | Discovering relational patterns across multiple databases[END_REF] is based on the construction of a tree containing for each pattern all its occurrences (i.e., fragment/transaction pairs), which still requires a considerable volume of communications. More recently, [START_REF] Zhu | CLAP: Collaborative pattern mining for distributed information systems[END_REF] implements a decentralized pruning technique within the extraction on each fragment by exchanging Bloom filters. This approach significantly reduces computation time but the cost of communications remains too large. Indeed, for low support threshold, the volume of extracted patterns invariably generates an enormous communication cost much higher than that of data centralization. In addition, all these frequent pattern mining approaches are limited to horizontal partitioning of data, i.e. the same transaction cannot be distributed on two separate fragments. Finally, as said above, all the existing proposals require a computation capacity on each fragment, which is not always possible. For instance, the Semantic Web provides access to distributed data via SPARQL endpoints, but it is not possible to execute a pattern mining routine on these endpoints. For all these reasons, we propose to revisit the discovery of patterns in distributed databases in the light of pattern sampling. We will see that our approach does not require computation capacity on the fragments and reduces the communication costs because all the patterns are not extracted.

Pattern sampling

The principle of on-demand pattern mining consists in extracting a pattern in a very short time without having previously preprocessed a huge collection of patterns. For instance, many heuristic methods [START_REF] Dietterich | A comparative review of selected methods for learning from examples[END_REF] allow to quickly induce rules in a supervised context. More recently, [START_REF] Hasan | Output space sampling for graph patterns[END_REF][START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF] have proposed pattern sampling methods that instantly extract patterns. These methods aim to derive patterns with a probability distribution proportional to their interest. As we consider an unsupervised context (e.g., see the use case in Section 6), this paper continues in this direction.

Output space sampling methods [START_REF] Hasan | Output space sampling for graph patterns[END_REF][START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF] aim at drawing patterns with a probability distribution proportional to their interest. Most sampling techniques fall into two broad categories: stochastic methods [START_REF] Hasan | Output space sampling for graph patterns[END_REF][START_REF] Bhuiyan | Interactive pattern mining on hidden data: a sampling-based solution[END_REF][START_REF] Boley | Formal concept sampling for counting and threshold-free local pattern mining[END_REF] and multi-step methods [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF][START_REF] Moens | Instant exceptional model mining using weighted controlled pattern sampling[END_REF][START_REF] Diop | Sequential pattern sampling with norm constraints[END_REF][START_REF] Giacometti | Dense neighborhood pattern sampling in numerical data[END_REF]. In order to randomly walk from a pattern X to another, stochastic methods require to consider the global interest of all the neighboring patterns of X. For example, in the case of frequency, it would be necessary to know the global frequency of all the subsets and supersets of X, which would generate many communications. For this reason, we prefer to adopt a multi-step random method. This type of method has already been used for several interestingness measures (e.g., support or area [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF] or exceptional measure [START_REF] Moens | Instant exceptional model mining using weighted controlled pattern sampling[END_REF]) and several data types like transactional data [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF][START_REF] Moens | Instant exceptional model mining using weighted controlled pattern sampling[END_REF], sequential data [START_REF] Diop | Sequential pattern sampling with norm constraints[END_REF] or numerical data [START_REF] Giacometti | Dense neighborhood pattern sampling in numerical data[END_REF]. Nevertheless, the context of distributed databases is an orthogonal challenge. In particular, we determine minimal information that the fragments must communicate to make an unbiased draw of patterns.

Maintenance of discovered patterns

Many works in the literature focused on data change and user needs change in pattern mining. But these approaches fall within the framework of constraint-based pattern mining where the constraint q models the needs of the user. The goal is then to extract each pattern X from the database D satisfying the constraint q i.e., the collection C = {X such that q(X, D) = true}. First, incremental pattern mining consists in extracting the collection C still satisfying the constraint q, but in an updated dabase D benefiting from C. Pioneering work began with an interest in the maintenance of association rules [START_REF] Cheung | Maintenance of discovered association rules in large databases: An incremental updating technique[END_REF]. Since, significant efforts have been made for different kinds of patterns including sequential patterns [START_REF] Cheng | IncSpan: incremental mining of sequential patterns in large database[END_REF] and high-utility itemsets [START_REF] Gan | A survey of incremental high-utility itemset mining[END_REF]. To the best of our knowledge, all these works require to centralize the data or the search space, and it is not straightforward to adapt them to distributed data. Second, inductive databases [START_REF] Imielinski | A database perspective on knowledge discovery[END_REF][START_REF] Raedt | A perspective on inductive databases[END_REF] were also interested in updating a collection of patterns extracted from the same data D, but with a new constraint q . Most of the approaches have cache mechanisms [START_REF] Calders | A survey on condensed representations for frequent sets[END_REF] to avoid having to recalculate everything. Even if these approaches accelerate the updating of the collection in certain cases, these mechanisms based on the exhaustive extraction paradigm remain time demanding.

For this reason, in recent years, there has been a new drive to make extraction pattern mining approaches user-centric [START_REF] Van Leeuwen | Interactive data exploration using pattern mining[END_REF]. In this context, it was necessary to resort to algorithms with much shorter response times giving rise to interactive methods based on pattern sampling [START_REF] Bhuiyan | Interactive pattern mining on hidden data: a sampling-based solution[END_REF][START_REF] Giacometti | Interactive pattern sampling for characterizing unlabeled data[END_REF][START_REF] Dzyuba | Interactive learning of pattern rankings[END_REF]. Even if our work is in this research direction, it is important to remember that none of these proposals work for distributed data as we explained in the previous paragraph.

Problem Formulation

In this section, we first introduce the definitions relating to itemsets and transactional distributed databases (see Section 3.1) and the communication model (see section 3.2). Next, Section 3.3 defines the class of interestingness measures that we address. Finally, we formalize the pattern sampling problem in transactional distributed databases.

Pattern language and transactional distributed databases

This paper benefits from the formal framework of transactional databases [START_REF] Agarwal | Fast algorithms for mining association rules[END_REF]. This framework is close to the key-value data model [START_REF] Han | Survey on NoSQL database[END_REF] where the identifier of a transaction is a key and the items of a transaction are values. Given a set I of distinct literals called items, an itemset (or pattern) is a subset of I. The language of itemsets corresponds to L = 2 I , and the size or length of an itemset X ∈ L, denoted by |X|, is its cardinality. In our approach, a transactional database D is a set of pairs (j, X) where j is the unique identifier of a transaction and X is an itemset in L, i.e. D ⊆ N×L. In Intuitively, a transactional distributed database (or a distributed database in short) is a set of transactional databases, also called fragments, where transactions do not overlap. More formally, a distributed database is defined as follows:

Definition 1 (Transactional distributed and centralized databases).

A (transactional) distributed database P = {D 1 , . . . , D K } is a set of transactional databases D k (k ∈ [1.
.K]) such that for each j ∈ N,

we have D k [j] ∩ D l [j] = ∅ if k = l.
Then, the centralized version of P, denoted by P * , is the transactional database defined by:

P * = {(j, X) : X = K k=1 D k [j] ∧ X = ∅}.
For example, in Table 1, it is easy to see that P * is the centralized version of the distributed database P = {D 1 , . . . , D 4 }. In the following, we also say that P is a partitioning of the centralized database P * . In general, different types of partitioning are distinguished:

• Horizontal partitioning: a distributed database is a horizontal partitioning if every transaction is described in only one fragment, i.e. if

for every j ∈ N, D k [j] = ∅ and D l [j] = ∅ implies that k = l.
• Vertical partitioning: a distributed database is a vertical partitioning if every item is present in only one fragment, i.e. if for every x ∈ I,

x ∈ j∈N D k [j] and x ∈ j∈N D l [j] implies that k = l.
• Hybrid partitioning: a partitioning is said to be hybrid if it is neither horizontal nor vertical.

For example, in Table 1, P is a hybrid partitioning of P * . Indeed, the transaction 2 is described both in the fragments D 2 , D 3 and D 4 , and the item A is both present in fragments D 1 and D 4 .

Communication model

We consider that only three forms of primitive query can be sent to the fragment:

1. lengthOf primitive: Given a transaction identifier j and a fragment D k , the query lengthOf(j, D k ) returns the length of the transaction j

in fragment k, i.e. lengthOf(j, D k ) = |D k [j]|.
In our example, we have

lengthOf(4, D 1 ) = 2 since |D 1 [4]| = |BE| = 2.
2. itemAt primitive: Given a position i, a transaction j and a fragment D k , the query itemAt(i, j, D k ) returns the i-th item of the transaction j in fragment D k (assuming an arbitrary order over the set of items I).

In our example, considering the lexicographic order over I, we have

itemAt(2, 4, D 1 ) = E.

Class of interestingness measures

Pattern discovery is based on interestingness measures that evaluate the quality of a pattern. One of the most popular interestingness measure is the frequency which is intuitive for experts and is an atomic element to build many other interestingness measures (like area or discriminative measures [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF]). The frequency of an itemset X ∈ L in the transactional database D, denoted by freq(X, D), is defined by: freq(X, D) = |{(j, T ) ∈ D : X ⊆ T }|. In Table 1, we have freq(DF, P * ) = 2 since the itemset DF is included in transactions 2 and 3.

It is also common to associate a utility to an itemset, and to combine the frequency of an itemset with its utility [START_REF] Geng | Interestingness measures for data mining: A survey[END_REF]. For example, if we consider the utility function u(X) = |X|, we obtain the area measure freq(X, D) × |X|, which is used to discover correlations in genomic data [START_REF] Besson | Constraint-based concept mining and its application to microarray data analysis[END_REF][START_REF] Henriques | A structured view on pattern mining-based biclustering[END_REF]. More generally, we consider the class of interestingness measures of the form freq(X, D) × u(X) where u exclusively depends on the length of itemsets:

Definition 2 (Length-based utilities and measures). A utility u defined from L to R is called a length-based utility if there exists a function

f u from N to R such that u(X) = f u (|X|) for each X ∈ L. Given the set U of length-based utilities, M U is the set of interestingness measures m u such that for every pattern X and database D, m u (X, D) = freq(X, D) × u(X)
with u ∈ U.

We already see that the utility function defined for every pattern X ∈ L by u area (X) = |X| allows us to consider the area measure freq(X, D) × |X|

(because f uarea (l) = l defined for every l ∈ N gives u area (X) = f uarea (|X|)).
Obviously, let us notice that the utility function defined by u freq (X) = 1 enables us to consider the frequency as interestingness measure. Besides, the utility function defined by u ≤M (X) = 1 iff |X| ≤ M (0 otherwise) simulates a maximum length constraint. Indeed, with the induced interestingness measure freq(X, D)×u ≤M (X), an itemset with a cardinality strictly greater than M is judged useless (whatever its frequency). Dually, the utility function defined by u ≥m (X) = 1 iff |X| ≥ m (0 otherwise) simulates a minimum length constraint. Finally, the utility function defined by u decay (X) = α |X| with α ∈]0, 1[, named exponential decay, is useful for penalizing large itemsets but in a smooth way in comparison with u ≤M .

Interestingly, it is possible to combine length-based utility functions with arithmetical operations:

Property 1 (Arithmetical closure). The set U of length-based utilities is closed under arithmetical operations i.e., if u 1 ∈ U, u 2 ∈ U and ∈ {+, -, ×, /}, then u 1 u 2 is a also a lengh-based utility .

Proof 1. Let u 1 and u 2 be two length-based utilities, i.e, there are two functions f u 1 and f u 2 defined from N to R such that for every pattern X ∈ L,

u 1 (X) = f u 1 (|X|) and u 2 (X) = f u 2 (|X|). For all ∈ {+, -, ×, /}, we know that u 1 u 2 (X) = f u 1 (|X|) f u 2 (|X|). Yet for all ∈ {+, -, ×, /}, there exists a function f : N → R such that f u 1 (|X|) f u 2 (|X|) = f (|X|).
This implies that for every length-based utilities u 1 and u 2 , and an operator ∈ {+, -, ×, /}, there is a function f :

N → R such that u 1 u 2 (X) = f (|X|).
Then u 1 u 2 is a length-based utility according to the definition. 2

Property 1 is important for the end user who can thus combine several interestingness measures. For instance, if q 1 and q 2 are two length-based utility constraints (i.e., length-based utilities with {0, 1} as range), then q 1 ∧q 2 and q 1 ∨ q 2 are also length-based utility constraints because q 1 ∧ q 2 = q 1 × q 2 and q 1 ∨ q 2 = q 1 + q 2q 1 × q 2 . For instance, in the following, we consider the length-based utility u ∈[m..M ] = u ≥m × u ≤M for focusing the discovery on patterns having a cardinality between m and M .

Pattern sampling in a distributed database

A pattern sampling method aims at randomly drawing a pattern X from a language L according to an interestingness measure f . X ∼ π(L) denotes such a pattern where π(.) = f (.)/Z is a probability distribution over L (with Z as normalizing constant). In this paper, our goal is to randomly draw patterns in a distributed database according to an interestingness measure in M U :

Given a transactional distributed database P, an interestingness measure m ∈ M U , we aim at randomly drawing a pattern X ∈ L with a probability distribution π proportional to its interestingness measure m i.e., π(X) = m(X,P * ) Z where P * is the centralized database of P and Z = X∈L m(X, P * ) is a normalizing constant.

In a pattern-on-demand context, it is clear that the sampled patterns must be returned instantly. A naive approach could apply the classical twostep random procedure [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF] after having centralized all the fragments of the distributed database P for building P * (using itemAt queries). The communication cost of this preliminary centralization would be very high. Indeed, it would be proportional to the size of P * , i.e.

||P * || = K k=1 ||D k ||.
Next section shows that it is only necessary to centralize the lengths of the transaction parts stored in the different fragments of P in order to draw an exact sample of patterns.

Decentralized Pattern Sampling

We present in this section our algorithm (Section 4.1) and we proceed to its theoretical analysis (Section 4.2).

DDSampling algorithm

This section presents our algorithm called DDSampling (for Distributed Database Sampling), which randomly draws a pattern from a distributed database P proportionally to an interestingness measure m ∈ M U .

The key idea of our proposal is first to centralize only the lengths of the transaction parts contained in the different fragments. Indeed, this information requires a low communication cost and it enables us to draw a transaction identifier j according to its weight ω(j) and an itemset length proportionally to ω (j).

and k ∈ [1..K] by M jk = lengthOf(j, D k ).
In practice, it is important to note that the matrix M is computed offline before the drawing phase where the pattern-on-demand paradigm requires speed. The number of rows in the matrix M is not known in advance because it depends on the transactions present in each fragments. For this reason, line 1 requests all transactions modified since timestamp 0 with a query transUpdt(0, D k ) for each fragment k. In the following, M j• denotes the 1. We can also check that

sum M j• = K k=1 M jk . It is easy to see that M j• represents the length of the j M M j• M j• =0 ω freq (j) = ω freq (j) ω area (j) ω 2 (j) ω decay (j) 1 1 2 0 0 3 1 + 3 + 3 + 1 = 8 12 7
M 1• = 1 + 2 = |P * [1]|.
Given a distributed database P and its associated weight matrix M , Property 2 shows how the weights ω(j) and ω (j) can be computed for each transaction j and length for any length-based utility function u ∈ U:

ω (j) = X⊆P * [j]∧|X|= u(X) = M j• × f u ( ) Moreover, we have ω(j) = M j• =0 ω (j).
i ∼ u([1..M j• ] \ ϑ) 9: k := min{p ∈ [1..K] : i ≤ p m=1 M jm } 10: i := k m=1 M jm -i + 1 and x := itemAt(i , j, D k ) 11:
X := X ∪ {x} 12:

ϑ := ϑ ∪ {i} 13: od 14: return X Therefore, we have ω

(j) = |P * [j]| × f u ( ) because u(X) = f u (|X|) = f u ( ).
According to Definition 3, we have

|P * [j]| = K k=1 M jk = M j• . So, we finally have ω (j) = M j• × f u ( ). Hence the result. 2
Intuitively, this property is valid because all the itemsets of length in a transaction j have the same utility. In Algorithm 1, this property is used during the preprocessing phase to compute the weights of all the transactions. This preprocessing phase is illustrated in Table 2 with four length-based utility functions: u freq , u area , u ≤2 and u decay (with α = 0.1). For example, because u freq (X) = 1 for every X ∈ L, we have ω freq (1) =

3 =0 3 = 1 + 3 + 3 + 1 = 8 = 2 3
. Considering the area utility function u area , we have

ω area (1) = 3 =0 3 × = (1 • 0) + (3 • 1) + (3 • 2) + (1 • 3) = 3 + 6 + 3 = 12
since u area (X) = for every pattern X of length . With the maximum length constraint, it is easy to see that ω 2 (1) = 2 Drawing phase. In this phase, we can apply a direct generalization of the two-step random procedure proposed in [START_REF] Boley | Direct local pattern sampling by efficient two-step random procedures[END_REF] to draw itemsets with a probability proportional to their interest in the manner of the area measure.

We start by drawing in Step 1 a transaction identifier j with a probability proportional to its weight ω(j) (see line 3 of Algorithm 1). The only difference is that the weights ω(j) are computed during the preprocessing phase using the weight matrix M and Property 2.

In Step 2, as the weights ω (j) of the transaction j are not stored during the preprocessing phase to reduce the storage cost, line 4 computes them for any length . After drawing the length of the itemset that will be returned (lines 4-5), DDSampling draws an itemset of length from the different fragments of P. At each iteration of the while loop (lines 7-13), the key idea is to draw without replacement the position i of an item in the transaction j (line 8) and to search the fragment D k that contains this item (line 9).

Then, we compute the position i of this item in the fragment D k before querying the corresponding item x (see line 10). Finally, the item x is added to the itemset X (line 11) that will be returned (line 14) and the position i is added to the set ϑ (line 12) in order to avoid sampling the same position (and item) twice (see line 8). This process is repeated times in order to return an itemset X of length . For example, considering the toy example in and ω(j). Note that for a new transaction j, old is zero and a new row has to be added to the weight matrix.

As a result, the cost of maintaining the preprocessing to take into account a data change is exactly 2 (1 cost with transUpdt plus 1 cost with lengthOf). As the overall cost is linear with the number of data changes regardless of the database and its type of distribution, we have not carried out an experimental cost analysis. Of course, this cost is much lower than that required for exhaustive methods where pattern mining is redone from scratch.

• Needs change: The user may want to change the utility function. For example, he could increase/decrease the maximum length constraint or he could use exponential decay. On the one hand, this change of utility function does not entail any communication cost because there is no length to update in the weight matrix M . On the other hand, it is necessary to recalculate the sets of weights for all the transactions.

Consequently, a change of interestingness measure is not prohibitive because it does not involve any communication cost. Section 5.3 em-pirically evaluates this running time showing its efficiency.

Theoretical analysis of the method

The following property states that DDSampling returns an exact sample of itemsets without centralizing the distributed database:

Property 3 (Correction). Given a distributed database P = {D 1 , ..., D K } and a length-based utility function u ∈ U, Algorithm 1 draws an itemset X according to a distribution proportional to m u (X, D) = freq(X, D) × u(X)

where D = P * .

Proof 3. Let Z be a constant defined by Z = j≥1 ω u (j), X an itemset of I and P (X) the probability to draw X with Algorithm 1. Then we obtain: P (X) = X⊆T j ∧|X|= P (X, T j ) = X⊆T j ∧|X|= P (T j ) × P (X/T j ). Besides, P (T j ) = ωu (j) Z and P (X/T j ) = u(X) ωu (j) . So, P (X) =

X⊆T j ∧|X|= u(X) Z = f req(X,D) Z × u(X)=supp(X, D) × u(X). Consequently, Property 3 is correct. 2
This follows from the fact that the three different draws (i.e., transaction j, length and the sampled itemset) take into account the number of itemsets occurring in each transaction weighted by the utility function. We now study the complexity of our method by distinguishing the two main phases: the preprocessing phase (where the matrix M is computed) and the drawing phase of itemsets. For each phase, we evaluate the complexity in time and in communication. Then, the drawing of an itemset from this transaction is done in time O(|I|).

Therefore, the drawing complexity of an itemset is in O(log(|P * |) + |I|). Besides, the space complexity only depends on the weight matrix dimension and it is in O(|P * | • |P|). As this storage cost is really low in practice, we store the matrix in memory. In an extreme case, the matrix could be stored in a database with a B-tree index [START_REF] Comer | Ubiquitous B-tree[END_REF] to have quick access to the rows.

Communication complexity. In order to evaluate the communication cost, we simply sum the cost of queries lengthOf, itemAt and transUpdt required for the two main phases. First, it is easy to see that for the preprocessing phase, the construction of the weight matrix M requires

O(|D 1 | + • • • + |D K |)
exchanges (using 1 transUpdt query per fragment with |D k | as cost, and 1 lengthOf query per transaction), which is in general significantly lower than the cost of a complete centralization of P in failure). These phenomena induce a bias in the performed drawings because we have to reject a pattern X as soon as an itemAt query fails during its drawing. In the case of network failure, let net be the probability that an itemAt query failed. Assuming that the failures are independent, we can Therefore, it follows that the rejection rates are negligible.

O(|D 1 | + • • • + |D K | + ||D 1 || + • • • + ||D K ||) = O(
show that P(reject) = P ( )• 1 -(1 -net ) . Thus,

Experimental Evaluation

In this section, we evaluate the efficiency of our approach compared to a centralized solution. Note that our prototype is implemented in Java and is available at https://github.com/DDSamplingRDF/ddsampling.git. All experiments are conducted on a 3.5 GHz 2 core processor with the Windows 10 operating system and 16 GB of RAM. Communication costs are evaluated as primitive query cost to be independent of exchange protocol and server load. We use 10 UCI benchmark datasets with varied features 1 that we uniformly partition into K = 10 fragments to simulate distributed databases. In the case of horizontal partitioning (resp. vertical partitioning), each transaction (reps. each item) is randomly placed to a fragment with the same probability 1/K; in the case of hybrid partitioning, all the items of a

1 Iris is a very small dataset but useful for measuring the degradation of the accuray of sampling (see Section 5.2).

transaction are randomly placed to a fragment (with the same probability 1/K). Table 3 shows statistical information about all datasets. In all experiments, we use length constraints u ≥1 and u ≤M (with M = {1, . . . , 10}).

This choice avoids drawing too much infrequent patterns, in particular for datasets containing long transactions. In addition, we consider three kinds of length-based utility functions: frequency, area and exponential decay. In Figure 1, we observe that the execution time of the primitive

Execution times and communication costs

transUpdt in a fragment D k , k ∈ [1.
.10], is lower than 6 milliseconds in average for all the contexts (whatever the database and the partitioning type).

The cost of this primitive depends on the sum of each fragment size when T = 0 (i.e., 10 k=1 |D k |). For this reason, transUpdt is more parsimonious in horizontal partitioning. Figure 2 shows that the execution time of lengthOf is generally very small, lower than 0.5 × 10 -6 milliseconds. With the same database, lengthOf is generally more expensive in horizontal partitioning than in vertical or hybrid partitioning (except Iris which is a small database with few items per transaction). This result can be explained by the length of transactions that is smaller for the vertical and hybrid partitionings.

Figures 3 indicates the execution times of the preprocessing of our method

that is only dependent on the length constraint (e.g., using frequency instead of area has no impact). As expected, the preprocessing time (which can be prepared offline) increases with the size of the dataset and with the maximum length M .

In all cases, this preprocessing time is very low (less than 150 ms) whatever the kind of partitioning. Figures 456report the execution times of the drawing phase respectively for frequency, area and exponential decay (with M = 10). The sampling time depends on the length-based utility measure because the latter greatly influences the average number of items to be drawn. In particular, the larger the parameter M (or α), the longer the patterns. As a result, the execution time is longer. Nevertheless, whatever the dataset and the utility measure, it is always under 0.010 ms (per pattern). This shows that our approach is very effective in delivering patterns on demand to the end user.

For the communication costs, we also consider the three types of partitioning.

In the preprocessing phase, the communication cost corresponds to the number of lengthOf calls for constructing the weight matrix. This cost is naturally higher for hybrid and vertical partitioning schemes since the items of a transaction may not be in the same fragment. In the drawing phase, the communication cost corresponds to the number of itemAt calls, and Table 4 shows the mean number of calls for drawing a pattern. This cost does not depend on the type of partitioning, but on the maximum length (M ∈ {3, 5}).

Finally, the last column of Table 4 compares the communication cost between distributed and centralized approaches. Its goal is to measure if the communication remains proportional to the support. Furthermore, for vertical partitioning, the sampling remains exact for available patterns (all their items are on working nodes).

Obviously, the more nodes are down, the fewer patterns are available. Hence, the remained patterns are much frequently drawn, which increases the slope of the curve.

Execution times for reprocessing for utility changes

Use Case: Outlier Detection in Transactional Distributed

Databases

This section aims at detecting outliers in knowledge bases of the Semantic Web by approximating Frequent Pattern Outlier Factor (FPOF) [START_REF] He | FP-outlier: Frequent pattern based outlier detection[END_REF] with sampled patterns. More precisely, we use this measure for identifying misclassified entities from two classes (Person and Organisation) described in DBpedia [START_REF] Bizer | Hellmann, DBpedia -a crystallization point for the web of data[END_REF] and

Wikidata [START_REF] Vrandečić | Wikidata: a free collaborative knowledgebase[END_REF]. In this context, each entity of a class C is a transaction distributed over DBpedia and Wikidata where each property p from a RDF triple (x, p, y) is an item. Table 5 provides some statistics about the two classes. Execution times are longer than that for UCI benchmarks because we use public SPARQL endpoints.

Long tail problem and length constraints

The exact FPOF of a transaction can be approximated using pattern sampling [START_REF] Giacometti | Anytime algorithm for frequent pattern outlier detection[END_REF]. More precisely, given a database D and a sample S, the approximated FPOF of a transaction t ∈ D is defined by fpof S (t, D) = |{X∈S : X⊆t}| max u∈D (|{X∈S : X⊆u}|) . Given a maximum length constraint M , we can prove that fpof S (t, D) tends to the exact FPOF fpof ≤M (t, D) = X⊆t,|X|≤M freq(X,D) max u∈D ( X⊆u,|X|≤M freq(X,D)) when the size of S tends to infinity and S is sampled according to m(X, D) = freq(X, D) × u ≤M (X). Figure 10 depicts the FPOF distributions of all entities for Person and Organisation without constraint (M = ∞) or with a maximum length constraint M ∈ {1, 2, 3, 4, 5, 10}. We see that without constraint or with a large value for M (≥ 5), a large majority of FPOF values are equal to zero, which implies that it is impossible to distinguish outliers from normal entities. Indeed, without constraint, FPOF suffers from the long tail problem [START_REF] Diop | Sequential pattern sampling with norm constraints[END_REF]. Therefore, the use of a maximum length constraint is crucial for detecting outliers by means of FPOF. Consequently, we use M = 3 in the following experiments.

Output space vs. input space sampling

This experiment compares input and output space sampling to determine which method is the best for the same budget (same number of patterns, same communication cost). For a pattern budget k, we start by drawing a sample S out of is the arithmetic mean of 100 repeated samples with its standard deviation). Of course, both errors tend to zero when the sample size tends to infinity. But, it is clear that the convergence is faster and more stable with output space sampling (e.g., the FPOF quality of S out with 10k patterns equals that of S in with 100k patterns). This experience shows that output space sampling is more efficient at equal budget.

Qualitative evaluation

We manually analyze the 50 best and worse entities of Person according to the FPOF. As illustration, note that Tables 6 and7 provide respectively the 20 worse and best persons according to the FPOF. It is interesting to note that all entities with the highest FPOF are real persons, and not outliers. Moreover, these people are all extremely famous, which explains why their description in the knowledge bases of the Semantic Web is so good [START_REF] Galárraga | Predicting completeness in knowledge bases[END_REF]. On the contrary, only 36% of the entities with the lowest FPOF are real persons, and 64% of them can be considered as outliers. Even the entities of Table 6 that are real people, may be anomalous data. Indeed, they are little known and they should perhaps not be informed in these two encyclopedic knowledge bases. For the other entities, 44% of entities are fictional characters. More importantly, 8% of the worst entities should be classified in Organisation (a sibling class of Person) like "Thurso Academicals Football club", and 12% of them should be classified in another class (e.g., Event).

Conclusion and Future Work

This paper proposes the first Pattern-On-Demand approach for extracting patterns in a transactional distributed database. In practice, our output space sam- In future work, we plan to replace the exact drawing of transactions with a stochastic method so that we do not have to centralize the lengths of all transactions for each fragment. It would also be interesting to propose a correction mechanism of the weights in order to counterbalance the bias introduced by node failures.

Finally, we would like to benefit from the Pattern-On-Demand paradigm to address other downstream applications. In particular, we could directly build associative classifiers.

  the following, given a transactional database D, for every integer j ∈ N, D[j] represents the itemset of transaction j, i.e. D[j] = X if (j, X) ∈ D (otherwise, we consider that D[j] = ∅). Moreover, |D| is the number of transactions in D and ||D|| = j∈N |D[j]| defines the size of the transactional database D. For example, in Table 1, the transactional database D 1 contains 3 transactions of identifiers 1, 4 and 5. Besides, we have D 1 [1] = A, D 1 [4] = BE and D 1 [5] = BC. Thus, we have ||D 1 || = 1 + 2 + 2 = 5.

3 .

 3 transUpdt primitive: Given a timestamp T and a fragment D k , the query transUpdt(T, D k ) returns the set of transaction identifiers of modified transactions since the timestamp T in fragment k (i.e., transUpdt(T, D k ) = {j ∈ N : time(D k [j]) ≥ T }) and its communication cost is |transUpdt(T, D k )|. In our example, we have transUpdt(0, D 3 ) = {2, 4} and its cost is 2.Our communication model is generic since more complex queries can be reduced to these three basic primitives for describing the exchanges. For instance, advanced queries may directly obtain a transaction of items from a fragment corresponding to itemAt primitives. For the Semantic Web, for the primitive lengthOf, the SPARQL query SELECT (COUNT(DISTINCT ?p) AS ?length) WHERE {wd:Q210734 ?p ?o} returns the length of Youssou N'Dour's transaction (wd:Q210734) from Wikidata SPARQL endpoint (here, the length is 143 items). In the same way, the query SELECT DISTINCT ?p WHERE {wd:Q210734 ?p ?o} OFFSET 2 LIMIT 1 gives the second item of the transaction. Of course, it is possible to use the query SELECT DISTINCT ?p WHERE {wd:Q210734 ?p ?o} for having the entire transaction instead of using 143 itemAt queries. Unlike the primitives lengthOf and itemAt that have 1 as communication cost, the communication cost of this query is 143.

  Finally, we show how to emulate a decentralized sampling of a subset of D[j] of length without centralizing all the items of D[j]. Preprocessing phase. In this phase (see lines 1-2 of Algorithm 1), we first compute and store locally a matrix M that contains for every transaction j and every fragment D k of P, the length of the transaction j in D k . Definition 3 (Weight matrix). Given a distributed database P = {D 1 , . . . , D K }, let M ∈ R |P * |×|P| be the matrix defined for every j ∈ [1..|P * |]

Property 2 .

 2 Let P = {D 1 , . . . , D K } be a distributed database and u ∈ U be a length-based utility. Given the weight matrix M associated with P, for each transaction j ∈ [1..|P * |] and ∈ [1..M j• ], we have:

Proof 2 .Algorithm 1 2 : 3 : 4 : 5 :

 212345 According to a length-based utility measure u, we know by definition that the weight of the patterns of length into a transaction of identifier j in the database P * is exactly equal to ω (j) = X⊆P * [j]∧|X|= u(X). DDSampling (Distributed Database Sampling)Input: A distributed database P = {D 1 , • • • , D K }and a length-based utility u ∈ U Output: An itemset X ∈ L randomly drawn w.r.t. freq(X, P * ) × u(X) // Preprocessing Phase 1: Compute M defined by M jk := lengthOf(j, D k ) for k ∈ [1..K] and j ∈ transUpdt(0, D k ) Compute the weights ω defined by ω(j) := M j• =0 M j• × f u ( ) for j ∈ [1..|P * |] // Drawing Phase -Step 1: sampling of a transaction Draw a transaction identifier j ∈ [1..|P * |] proportionally to ω: j ∼ ω(P * ) // Drawing Phase -Step 2: decentralized sampling of an itemset Compute the weights defined by ω (j) := M j• × f u ( ) for every ∈ [0..M j• ] Draw a length proportionally to ω (j): ∼ ω [0..M j• ] (j) 6: ϑ := ∅ and X := ∅ 7: while |X| < do 8:

=0 3 = 1 + 3 + 3 = 7 . 3 =0 3 ×

 3133733 Finally, with the decay utility function u decay and α = 0.1, we have ω decay (1) = 0.1 = (1 • 0.1 0 ) + (3 • 0.1 1 ) + (3 • 0.1 2 ) + (1 • 0.1 3 ) = 1 + 0.3 + 0.03 + 0.001 = 1.331.

Table 2 , 1 .

 21 if we draw the position i = 2 in the transaction j = 1, we find that the involved fragment is D 2 since 2 > M 11 = 1 whereas 2 ≤ M 11 + M 12 = 3. Then, we compute i = 2 -1 = 1 and the item itemAt(1, 1, D 2 ) = B is added to the itemset X. Interest of Pattern On Demand. Before finely analyzing the algorithm DDSampling, it is important to underline the flexibility offered by the pattern-on-demand paradigm through our sampling method: • Data change: The consideration of a change is based on a protocol with two steps for each fragment D k (k ∈ [1..K]): On the server side, the fragment D k is queried with transUpdt(T prev , D k ) to know its modifications since the last update T prev . In particular, if a new transaction is added to the k-th fragment, it appears in the set transUpdt(T prev , D k ).

2 .

 2 There are 3 types of data operations on a transaction j ∈ transUpdt(T prev , D k ) of a fragment k: insertion, deletion and update. The update operation (i.e., item replacement) has no impact on the length of a transaction. In contrast, the first two operations change the length of transaction j of fragment k (from the length old to the length new ). Thus, they require an update in the weight matrix M jk by using the lengthOf(j, D k ). It is also necessary to update the corresponding weights: ω old (j), ω new (j)

  Time and space complexity. In the preprocessing phase, the weight matrix M is first computed with a complexity in time O(|P * | • |P|). Then, the weight ω(j) of all transactions j ∈ [1..|P * |] is computed in time O(|P * | • |I|) due to the use of the binomial function. Thus, the preprocessing phase is performed in time O(|P * | • (|P| + |I|)). The draw of an itemset is less expensive. First, the draw of a transaction identifier can be achieved in O(log(|P * |)).

First, we evaluate

  the execution time of each primitive used by DDSampling for the preprocessing phase (transUpdt and lengthOf) and the sampling phase (itemAt) in our local environment. For the primitive transUpdt, we give the execution time needed to get the transaction identifiers of each fragment at the initialization (i.e., for the timestamp T = 0). Figures 1 and 2 compare the execution times of transUpdt and lengthOf and according to the partitioning type for each transactional database. Contrary to these primitives, itemAt does not depend on any type partitioning and any database. The execution time of the primitive itemAt is 0.97 × 10 -6 milliseconds in average. All these results are obtained averaging 100 repetitions and the standard deviations are omitted because they are very small.

Figure 2 :

 2 Figure 2: Execution time of the primitive lengthOf

Figure 3 :Figure 4 :Figure 5 :Figure 6 :

 3456 Figure 3: DDSampling preprocessing times

Figure 7 :

 7 Figure 7: Average rejection rates with failures

Figure 8 Figure 8 :

 88 Figure 8 reports the number of occurrences by varying the probability p ∈ {0.00, 0.10, 0.20} that the network fails or the number of random down nodes z ∈ {0, 2, 5}. First, we see that whatever the type of partitioning, the network or node failures do not significantly change the accuracy of the method if the fault level is low (i.e., p ≤ 10% and z < 2). For network failures, the most frequent patterns are those mostly drawn because they often are the shortest ones and their rejection is less likely. Consequently, such patterns are over-represented in the sampled set.For node failures, we observe that in general the probability of drawing a pattern

Figure 9

 9 Figure 9 reports the execution times of the reprocessing of DDSampling when the utility measure changes. Indeed, as it only requires the weight matrix, the reprocessing time do not depend on the partitioning type of the transactional database (vertical, hybrid or horizontal). This execution time is done very quickly (i.e., < 25ms) for the different benchmark datasets but also for all the synthetic datasets used in this paper with a maximum length constraint M ∈ [2..10]. Note that the standard deviations (obtained with 100 repeated experiments) remain very low showing the stability of the computation. The reprocessing is less costly than processing because it does not consider each fragment and it reuses binomial factors computed during the preprocessing time. Of course, there are slight time variations depending of the complexity of the utility measure, but in all cases, the reprocessing operation is done efficiently enough to allow the user to instantly change their needs at any time.

Figure 9 :

 9 Figure 9: Reprocessing execution time according to the utility change

Figure 10 :

 10 Figure 10: Long tail problem of the FPOF distributions

Figure 11 :

 11 Figure 11: Evolution of the Euclidean norm error for input/output space sampling

  pling method allows to consider a large class of interestingness measures and it addresses hybrid or vertical partitioning. As only transaction lengths are centralized, the communication costs of DDSampling are low because the exchange of items is done on demand, when the patterns are drawn. The experimental study emphasizes this low communication cost on several benchmark datasets whatever the partitioning. It also shows that our method is particularly robust to network or node failures. A use case also illustrates the interest of the sampled patterns in RDF data for detecting abnormal entities among persons and organizations without centralizing all the data. It is clear that this approach identifies the outlier entities present in a class with a very low communication cost.

Table 1 :

 1 Example of a transactional distributed database P = {D 1 , D 2 , D 3 , D 4 } and its corresponding centralized database P *

Table 2 :

 2 Weight matrix M and transaction drawing weights

transaction j in P * , i.e. M j• = |P * [j]|. For example, Table

2

presents the weight matrix M of the transactional distributed database of Table

Table 3 :

 3 Characteristics of 5 partitioned datasets from UCI

				Centralized databases
	D Adult	|I| 97 48,842 |D|	||P || D 726,165 Mushroom	|I| 119	|D| 8,124	||P || 186,852
	Chess	75	3,196	118,252 Pumsb	2,113 49,096 3,629,404
	Connect	129 67,557 2,904,951 Soybean	99	683	22,251
	Iris	15	150	750 USCensus	396 13,369	909,049
	LetRecog 20,000	102	340,000 Waveform	67	5,000	110,000

Table 4 :

 4 Communication cost For this purpose, we evaluate the number N max of drawn patterns in the worst case (when M = 5 for vertical partitioning) that are necessary for the sampling approach to be as costly as the data centralization. For instance, for Adult, DDSampling can extract more than 68k patterns before reaching the communication cost of the data centralization. Note that the higher N max is, the better DDSampling is. For all datasets (except Iris, which is very small), we can

		Number of lengthOf/transUpdt calls #itemAt with u freq	N max
			Distributed data	POD	vertical
	D Adult	Horizontal Hybrid 48,842 386,326	Vertical 424,553 2.77 M=3	M=5 4.41	with u [1..5] 68,393
	Chess	3,196	31,312	31,427 2.91	4.83	17,976
	Connect	67,557 668,296	668,547 2.92	4.86	460,165
	Iris	150	614	618 2.19	2.58	132
	LetRecog	20,000 166,729	166,880 2.81	4.51	38,386
	Mushroom	8,124	74,036	74,180 2.85	4.70	23,973
	Pumsb	49,046 490,261	490,460 2.95	4.92	637,997
	Soybean	683	6,430	6,461 2.80	4.90	3,222
	USCensus	13,369 133,580	133,686 2.97	4.92	157,594
	Waveform	5,000	45,081	45,324 2.84	4.68	13,820
	cost of DDSampling (preprocessing and sampling) is interesting compared to the
	data centralization. see that DDSampling can draw a few thousand patterns with a communication
	cost lower than that of the data centralization. In addition to instantly returns
	patterns (once the preprocessing is done), our approach is much more parsimonious
	in terms of communication costs.

  DBpedia |I| Wiki. |t| min |t| max |t| avg Prep. Sampl.

							Time (s)
	D |I| Person 772,432 |D|	13,142	6,213	8	552	50.02 8,401	0.34
	Org.	338,402	19,022	5,504	8	328	36.22 1,848	0.27

Table 5 :

 5 Statistics and execution times for classes Person and Organisation

Table 6 :

 6 Ranking of the 20 worst entities of the person class in the top-100

	Rank Entity		FPOF	Current class
	1	Go Grizzly		0.001	Person
	2 ex	Delphi (comics)	0.002	Fictional Character
	2 ex	Bubsy Bobcat		0.002	Fictional Character
	2 ex	Flygirl (comics)	0.002	Fictional Character
	5	Thurso Academicals Football Club	0.003	Organisation
	6 ex	Annie Porter (character)	0.004	Fictional Character
	6 ex	Inferno (demon)	0.004	Fictional Character
	6 ex	Talking April		0.004	Fictional Character
	6 ex	Mahmoud	Magomedovich	0.004	Person
		Sheikh-Ali
	6 ex	The Night Sea		0.004	Organisation
	6 ex	Phurbu T Namgyal	0.004	Person
	6 ex	List of Israeli football transfers summer 2016	0.004	Organisation
	6 ex	Slawomir Naploszek	0.004	Person
	14 ex	Ventus (producer)	0.005	Person
	14 ex	John Raspado		0.005	Person
	14 ex	Dennis Reynolds (It's Always	0.005	Fictional Character
		Sunny in Philadelphia)
	14 ex	Albert Manning	0.005	Fictional Character
	14 ex	List of Las Vegas Valley	0.005	Organisation
		lounge artists
	14 ex	Plexippus		0.005	Fictional Character
	14 ex	Nocturne (Angela Cairn)	0.005	Fictional Character

The results would be similar on the other larger datasets but they would require much larger samples to make meaningful measurements.

$ This work has been partly supported by CEAMITIC (Centre d'Excellence Africain en

Robustness of DDSampling

Rejection rate. As seen in Section 4.2, network or node failures induce the rejection of some patterns. In this context, we evaluate the mean rejection rate by drawing 10,000 patterns by varying p and z. We repeat 100 times each experiment by randomly generating the dataset partition and changing down nodes. As rejection rates are independent of datasets, Figure 7 plots the average rejection rate and the standard deviation computed by averaging the results from the 5 UCI datasets. For network failures, the average rejection rate does not depend on a particular partitioning type and Figure 7 (left) presents the evolution of the average rejection rates according to p for M ∈ {1, 2, 3, 4, 5}. In accordance with the theoretical analysis, for a given p, we see that the rejection rate increases with M since E[L] increases with M . Moreover, for a given M , we see that the increase of the rejection rate is sub-linear because E[L] decreases with p. Nevertheless, it remains inferior to 50% if p is inferior to 0.1, which already is a level of network failure much higher than what is observed in practice. Figure 7 (right) presents the average rejection rates with the proportion of down nodes. First, as proved in Section 4.2, we observe that the average rejection rate is lower for horizontal partitioning than for hybrid or vertical partitioning (since E[L] ≥ 1). Second, the standard deviation of vertical partitioning is higher than that of other partitioning. Indeed, with vertical partitioning, the average rejection rate can be very low or very high depending on whether the most frequent items are placed or not into down nodes. However, as for network failures, we note that the rejection rate remains acceptable.

Degradation of the accuracy of sampling. Two main problems may arise in distributed databases: network communication errors and node inaccessibility.

These phenomena induce a bias in the performed drawings because we chose to reject a pattern X as soon as an itemAt query fails during its drawing. To mea-


Maud Allary

M.D Aubert Agostini

M.D Lisa Calderon

M.D Laura Miquel

Ph.D Patrice Crochet

M.D Antoine Netter
email: antoine.netter@gmail.com

Using pneumovaginoscopy to perform the removal of a vaginal fibroid

Keywords: Vaginal fibroid, vNOTES, vaginal surgery

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Abstract Objective

To describe and assess the feasibility of a novel surgical technique (pneumovaginoscopy) to perform vaginal surgery.

Design

Video of a single surgical procedure.

Setting

A university hospital.

Patient(s)

A forty-two-year-old woman, gravida 2 para 2, presenting with chronic pelvic pain.

The vaginal examination revealed a 4-centimeter spherical mass bulging through the posterior vaginal wall. The MRI identified this mass as being either a subserosal pedunculated uterine fibroid (type 7 according to the FIGO classification) or an ectopic fibroid of the posterior vaginal wall (type 8).

Intervention(s)

The whole procedure was performed using pneumovaginoscopy. The GelPOINT V-Path (Applied Medical, Rancho Santa Margarita, California, USA) which is the most often used device to perform transvaginal natural orifice transluminal endoscopic surgery (vNOTES) procedures was introduced into the vagina to create a pneumovagina. Monopolar scissors were used to perform an incision trough the posterior vaginal wall in order to reach the fibroid. The myomectomy was performed using traction movements of the fibroid associated with the dissection of the capsule. The absence of a uterine pedicle at the end of the myomectomy was in favor of an ectopic fibroid of the vagina (type 8 of the FIGO classification). The vaginal defect was closed with interrupted sutures using the access points on the Gelpoint.

Main outcome measure(s)

The procedure was easily and efficiently performed using the pneumovaginoscopy technique and lasted less than an hour. The patient was discharged on day one and had no post-operative complications. She was symptom-free at her two-month post-operative visit.

Result(s)

In comparison to the classical vaginal approach, pneumovaginoscopy improves visualization through targeted lighting and close-up vision. This technique is particularly interesting when the vaginal opening is narrow and for lesions of the upper half of the vagina.

Because of the unusual expansion of the vagina, increased caution is needed to avoid bladder or rectal injuries.

Conclusion(s)

Pneumovaginoscopy is a novel technique that can be performed for vaginal pathologies with the same device used for vNOTES. We described the technique and assessed its feasibility.