Trong Dinh

Thac Do

Anne Laurent
email: laurent@lirmm.fr

Alexandre Termier
email: alexandre.termier@imag.fr

PGLCM: Efficient Parallel Mining of Closed Frequent Gradual Itemsets

Keywords: Data mining, frequent pattern mining, gradual itemsets, parallelism

Numerical data (e.g., DNA micro-array data, sensor data) pose a challenging problem to existing frequent pattern mining methods which hardly handle them. In this framework, gradual patterns have been recently proposed to extract covariations of attributes, such as: "When X increases, Y decreases". There exist some algorithms for mining frequent gradual patterns, but they cannot scale to real-world databases. We present in this paper GLCM, the first algorithm for mining closed frequent gradual patterns, which proposes strong complexity guarantees: the mining time is linear with the number of closed frequent gradual itemsets. Our experimental study shows that GLCM is two orders of magnitude faster than the state of the art, with a constant low memory usage. We also present PGLCM, a parallelization of GLCM capable of exploiting multicore processors, with good scale-up properties on complex datasets. These algorithms are the first algorithms capable of mining large real world datasets to discover gradual patterns.

I. INTRODUCTION

Frequent pattern mining is the component of data mining focused on extracting patterns that occur frequently in data. These patterns can be seen as abstractions of the contents of large datasets, potentially providing insightful information. Most of the works on frequent pattern mining have focused on categorical data, either mere sets (frequent itemset mining) [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF], or more complex data having a structure of sequence [START_REF] Pei | Prefixspan: Mining sequential patterns by prefix-projected growth[END_REF], tree [START_REF] Asai | Efficient substructure discovery from large semistructured data[END_REF] or graph [START_REF] Inokuchi | An apriori-based algorithm for mining frequent substructures from graph data[END_REF]. Few of these works have focused on numerical data. There have been some works on quantitative itemset mining, where items can have numerical values [START_REF] Srikant | Mining quantitative association rules in large relational tables[END_REF]. These works focused on discretizing numerical data in order to handle them the same way as categorical data. Thus, only a small part of the information present in the numerical data was exploited. Despite some improvements [START_REF] Aumann | A statistical theory for quantitative association rules[END_REF], [START_REF] Washio | Mining quantitative frequent itemsets using adaptive density-based subspace clustering[END_REF] over original works on quantitative association rule mining, analyzing numerical data remained marginal in the field of frequent pattern mining.

However, most corporate data and many scientific datasets have many attributes which are numerical: sales numbers, prices, ages, expression level of a gene, quantity of light received by a sensor, etc.

Recently, a new pattern mining field has emerged for analyzing such data: mining of gradual patterns. Gradual patterns can be expressed as covariations of several attributes, for example: "the higher the age, the higher the salary, the lower the free time". An algorithm based on Apriori has been proposed [START_REF] Jorio | Mining frequent gradual itemsets from large databases[END_REF] for mining gradual patterns. This algorithm, as the original Apriori, can mine simple datasets, but it does not scale on large real-world datasets.

Apriori is the pioneer of all algorithms for mining frequent itemsets, however state-of-the-art algorithms considerably outperform it. One of the major steps was the works of Pasquier et al. [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF], which showed that it was sufficient to mine closed frequent itemsets, with run time improvements over an order of magnitude in many cases. Later, the FIMI'04 workshop [START_REF] Goethals | Fimi repository website[END_REF] made a competition between all closed frequent itemset mining algorithms. The winner was the LCM algorithm [START_REF] Uno | Lcm ver. 2: Efficient mining algorithms for frequent/closed/maximal itemsets[END_REF].

LCM is based on a theoretical improvement: its authors showed that a closed frequent itemset could be computed by extension of a unique other closed frequent patterns. The closed frequent itemsets are thus the nodes of a covering tree, over which efficient depth first search strategies can be applied, with a very low memory usage.

Our goal is to exploit the principles giving the good performances of LCM in order to compute efficiently gradual itemsets over large real-world databases. The contribution of this paper is threefold:

• We show that likewise itemsets, it is possible to build a covering tree over the search space of closed frequent gradual itemsets. • We present an algorithm and an implementation for mining efficiently closed frequent gradual itemsets, based on the principle of the LCM algorithm. This algorithm, GLCM, has the same strong complexity guarantees as LCM: its time complexity is linear with the number of closed frequent gradual itemsets, and its memory complexity does not depend on this number. We experimentally show that our algorithm significantly improves the state of the art. • Last, we show a simple parallelization of our algorithm, using the Melinda library [START_REF] Negrevergne | Discovering closed frequent itemsets on multicore: Parallelizing computations and optimizing memory accesses[END_REF]. We experimentally show that the parallel version can take advantage of recent multicore processors and handle large real-world datasets. It is especially interesting to note that despite LCM proven efficiency, algorithms based on its principle have mostly remained theoretical (for example [START_REF] Arimura | An output-polynomial time algorithm for mining frequent closed attribute trees[END_REF]). By showing how to design and implement an efficient algorithm with this principle, we hope to help the diffusion of the ideas found in LCM, which are still the key to efficient pattern mining algorithms.

The paper is organized as follows: in Section II, we present in detail the concept of gradual patterns and related works. In Section III, we recall the base principles of LCM, show how they can be applied to gradual patterns, and present our algorithm and its parallelization. Section IV presents detailed experiments both about the sequential and the parallel version of our algorithm. We conclude and give directions for future research in Section V.

II. GRADUAL ITEMSETS AND RELATED WORKS

As described above, gradual itemsets (also known as gradual patterns) refer to patterns like "the higher the age, the higher the salary". They can be compared to fuzzy gradual rules that have first been used for command systems, for instance for braking systems: "the closer the wall, the stronger the brake force". However, in this framework, rules are provided by human experts. More recently, it has been shown that such rules can be mined [START_REF] Berzal | An alternative approach to discover gradual dependencies[END_REF], [START_REF] Hüllermeier | Association rules for expressing gradual dependencies[END_REF], [START_REF] Jorio | Mining frequent gradual itemsets from large databases[END_REF], and can even benefit from the new multicore architectures [START_REF] Laurent | Pgpmc: Towards a multicore parallel approach for mining gradual patterns[END_REF]. In order to tackle the problem of the number of patterns generated by the approach, [START_REF] Ayouni | Mining closed gradual patterns[END_REF] introduces closed gradual itemsets.

In this framework, the authors deal with gradual items, gradual itemsets and closed gradual itemsets as defined below.

A. Preliminary Definitions

A dataset is a set of tuples R defined over the schema S = {I 1 , . . . , I n }.

Table I shows an example dataset where S = {age, salary, loans, cars}.

A gradual item is a pair (i, v) of an item (attribute) i ∈ S and a variation v ∈ {↑, ↓} where ↑ stands for a positive (ascending) variation and ↓ for a negative (descending) variation.

A gradual itemset is defined as a non-empty set of gradual items. For instance, the gradual itemset P 1 = {(age, ↑ ), (salary, ↑)} means "the higher the age, the higher the salary".

The evaluation of the support of such gradual itemsets has been defined in different manners depending on the authors. [START_REF] Hüllermeier | Association rules for expressing gradual dependencies[END_REF] is based on regression, while [START_REF] Berzal | An alternative approach to discover gradual dependencies[END_REF], [START_REF] Calders | Mining rankcorrelated sets of numerical attributes[END_REF] and [START_REF] Laurent | Graank: Exploiting rank correlations for extracting gradual dependencies[END_REF] consider the number of tuples that are concordant and discordant, in the idea of exploiting the Kendall's tau ranking correlation coefficient [START_REF] Kendall | The problem of m rankings[END_REF]. In [START_REF] Jorio | Mining frequent gradual itemsets from large databases[END_REF], the authors consider another definition of the support based on the maximum proportion of tuples that can be ordered according to the gradual itemset.

In this framework, let us consider a gradual itemset P = {(i k1 , v k1 ), . . . , (i kj , v kj )} where {k 1 , . . . , k j } ⊆ {1, . . . , n} and the k 1 , ..., k j are all distinct. Two tuples t and t can be ordered with respect to P if all the values of the corresponding items from the gradual itemset can be ordered to respect the respective variation: for every l ∈ [k 1 , k j ], t.i l ≤ t .i l if v l =↑ and t.i l ≥ t .i l if v l =↓. The fact that t precedes t in the order induced by P is denoted t P t .

For instance, from Let L = {t 1 , ..., t m } be a list of tuples from R and P be a gradual itemset. L respects P if ∀i ∈ [1, m -1] we have t i P t i+1 . Let L P be the set of lists of tuples that respect P .

The formal definition of the support of P is support(P ) = max L∈L (|L|) |R| , i.e. it is the size of the longest list of tuples that respects P . Note that the support of an itemset containing a single item is always 100% as it is always possible to order all the tuples by one column.

The rest of this paper is based on this definition of support.

From the implementation point of view, it seems that [START_REF] Jorio | Mining frequent gradual itemsets from large databases[END_REF] is the most efficient one so far. It deals with binary matrices to represent how tuples are ordered (adjacency matrix) with regard to a gradual itemset. As shown below, this representation is very efficient, especially as it allows to apply AN D binary masks for joining gradual itemsets represented by their matrices. However, as the problem is similar to determining the longest path in a graph, it can be time consuming. Moreover, managing all the matrices can lead to performance degradation due to memory consumption.

For instance, Table II reports the way the information is stored in main memory and then processed for computing the support and joining itemsets. In this matrix, it can be seen that t 2 precedes t 2 , t 4 and t 5 (value 1 in the matrix) but not t 1 and t 3 . We have here: support({(age, ↑), (salary, ↑ )}) = 3/5 as P 1 is supported by the maximum ordered lists of tuples < t 1 , t 2 , t 4 > and < t 1 , t 2 , t 5 >.

B. Closed Gradual Itemsets

Closed itemsets have been studied for many years as they represent one of the keys to manage huge databases and to reduce the number of patterns without loss of information. Generally speaking, p is said to be closed if there does not exist any p such that p ⊂ p and support(p) = support(p ) Two closure operators have been defined in [START_REF] Ayouni | Mining closed gradual patterns[END_REF] for closed gradual itemsets: g and f . Given an ordered list of tuples S, f returns the gradual itemset (all the items associated with their respective variations) respecting all sequences in S. Given a gradual itemset P , g returns the set of the maximal lists of tuples which respect the variations of all gradual items in P .

For instance, f

(< t 1 , t 5 , t 3 >) = {(loans, ↑), (cars, ↓ )} and g({(age, ↑), (salary, ↑)}) = {< t 1 , t 2 , t 4 >, < t 1 , t 2 , t 5 >} Provided these definitions, a gradual itemset p is said to be closed if f (g(p)) = p. The closure of p is denoted Clo(p).
Compared to the context of classical items, the main issue here is to manage the fact that g does not return a set of tuples but it returns a set of lists of tuples that can be ordered.

As far as we know, these definitions have not been included by the authors within the mining process, but rather as a post-processing step which is not efficient. Indeed, it does not allow to benefit from the runtime and memory reduction and thus does not provide any added value for running the algorithms on huge databases. We thus propose below a novel approach to cope with this.

III. EFFICIENTLY MINING GRADUAL ITEMSETS

In this section, we present our algorithms for mining efficiently closed frequent gradual itemsets. We first explain the principle of the LCM algorithm for mining closed frequent itemsets. We show how we could adapt this algorithm to gradual itemsets, and we give complexity results on the new algorithm. We then present a parallelization of this algorithm.

A. LCM principle

LCM is the most efficient algorithm for computing closed frequent itemsets, as shown by the results of the FIMI'04 competition [START_REF] Goethals | Fimi repository website[END_REF]. It is the only such algorithm to exhibit a complexity which is linear with the number of closed frequent itemsets to find, hence its name: Linear time Closed itemset Miner. This result comes from an important theoretical advance: the authors of LCM could prove that there existed a covering tree over all the closed frequent itemsets, and the edges of this tree could be computed efficiently at runtime. The closed frequent itemsets can thus be discovered with a depth first algorithm, without maintaining a special storage space for the previously obtained patterns: a closed frequent itemset can be outputted as soon as it is discovered. This is not the case for most other closed frequent itemset mining algorithms, which have to keep in memory all the previously found frequent itemsets, to avoid duplications and for some algorithms such as [START_REF] Lucchese | Parallel mining of frequent closed patterns: Harnessing modern computer architectures[END_REF] check closure. The closed frequent itemsets can thus only be outputted at the end of computation, and the memory usage can be very important.

LCM is a depth first search algorithm. Each node of the search tree either corresponds to a closed frequent itemset or to an empty leaf. The pseudo-code of LCM is given in Algorithm 1 (coming from [START_REF] Uno | An efficient algorithm for enumerating closed patterns in transaction databases[END_REF]).

Algorithm 1 Algorithm LCM

Q = Clo(P ∪ i) ; 10: if P (i -1) = Q(i -1) then 11:
Enum ClosedPatterns(Q) ; 12: end if 13: end for Each recursive iteration represents a node of the search tree. Its input is a closed frequent pattern. If this pattern is not frequent (line 5), then we are at the end of a branch. Else, the pattern if frequent and the main goal of the iteration is to compute all its direct descendants in the search tree. This is done with an operation called prefix preserving extension (ppc-extension). Let P be a closed frequent itemset. For an item i ∈ P , we define P (i) = {j | j ∈ P and j ≤ i}. Let core i(P ) be the minimum index i such that T (P (i)) = T (P ) (with core i(⊥) = 0). Then an itemset Q is called a ppc-extension of P if (i) Q = Clo(P ∪ {i}) for some i ∈ I (ii) i ∈ P and i > core i(P ) (iii) P (i -1) = Q(i -1), i.e. P and Q share the same (i -1)-prefix. The authors of LCM have shown that for any closed frequent itemset Q = ⊥, there exist only one closed frequent itemset P such that Q is a ppc-extension of P (Theorem 2 in [START_REF] Uno | An efficient algorithm for enumerating closed patterns in transaction databases[END_REF]). This is the interest of ppc-extension: it is the very operation that allows the building of a covering tree of closed frequent itemset. Here P will be the unique father of Q, and ⊥ is the root of the covering tree.

In Algorithm 1, ppc-extension is performed in lines 8-10. For a closed frequent itemset P , all its possible ppcextensions Q are searched. First, all the i satisfying condition (ii) are iterated over in line 8. Q is computed according to condition (i) in line 9. And condition (iii) is checked in line 10. In line 11, Q is a ppc-extension of P , so a new recursive iteration (i.e. a new node of the search tree) is built with Q.

Example: Let us consider the following transaction database: With ε = 3, the depth first search performed by LCM is shown in Figure 1 1 .

By definition core i(⊥) = 0, so any item can be used to extend ⊥. This is shown by the arcs outgoing from ⊥, each labelled with the item used for extension. We explain here the branch for item 1. In the case of item 1, Clo({1}) = {1, 4, 6}, which is our leftmost node for depth 1. It is frequent in the database, so we circle it in the figure as a solution, and the iteration continues. We have to compute core i({1, 4, 6}). Removing 6 from {1, 4, 6} gives the itemset {1, 4}, and Clo({1, 4}) = {1, 4, 6}, hence core i(P ) < 4. Removing 4 and 6 from {1, 4, 6} gives the itemset {1}, and we already know that Clo({1}) = {1, 4, 6}. 1 is the smallest item i such that Clo(P (i)) = Clo(P ), thus core i({1, 4, 6}) = 1. The item 1 is boxed in the figure .  Possible extensions for {1, 4, 6} are 2, 3 and 5. The corresponding itemsets are represented below {1, 4, 6} in the figure, however they are not frequent so the function immediately returns. The itemsets are not circled in this case, to show that they are not closed frequent itemsets.

B. Adapting LCM principle to gradual itemsets

In order to mine closed frequent gradual itemsets with an algorithm similar to LCM, we need to be able to build a covering tree over all the closed frequent gradual itemsets. As seen before, we thus need to redefine ppc-extension for closed frequent gradual itemsets.

We first give the definition of core i for gradual itemsets. The definition is almost identical to the itemset case: let P be a closed gradual itemset , for an item x we have P (x) = {(y, v) | (y, v) ∈ P and y ≤ x}. core i(P ) is the minimum item i such that (i, v) ∈ P and g(P (i)) = g(P ), with core i(⊥) = 0.

We then give the definition of ppc-extension: the closed gradual itemset Q is a ppc-extension of P if (i) Q = Clo(P ∪ {(i, v)}) for some (i, v), with i ∈ I and v ∈ {↑, ↓}, (ii) (i, v) satisfies (i, v) ∈ P and (i, ¬v) ∈ P and i > core i(P ) (with ¬ ↑=↓ and ¬ ↓=↑), (iii)

P (i -1) = Q(i -1)
Our ppc-extension for gradual itemsets verifies the same theorem than ppc-extension for itemsets:

Theorem 1: Let Q = ⊥ be a closed gradual itemset.Then, there is just one closed gradual itemset P such as Q is a ppc-extension of P .

Skech of proof

The proof of this theorem follows exactly the same steps as the proof in [START_REF] Uno | An efficient algorithm for enumerating closed patterns in transaction databases[END_REF]. This proof mainly resorts to the properties of the closure operators f and g, which are the same for any closure operators. For gradual itemsets, the properties of monotonicity, extensivity and idempotency have been proven in [START_REF] Ayouni | Mining closed gradual patterns[END_REF].

A property that is often used in the proof of [START_REF] Uno | An efficient algorithm for enumerating closed patterns in transaction databases[END_REF] is, when adapted to gradual itemsets: let P be a gradual itemset and (i, v) ∈ P be a gradual item. Then g(P ∪ {(i, v)}) = g(P )∩g({(i, v)}). This property is not demonstrated in [START_REF] Ayouni | Mining closed gradual patterns[END_REF], however it comes from Theorem 1 in [START_REF] Jorio | Mining frequent gradual itemsets from large databases[END_REF], where the set of sequences output by g is encoded into a binary matrix.

Thanks to the ppc-extension for gradual itemsets, we can write a mining algorithm similar to LCM. We present our GLCM algorithm in Algorithm 2.

For simplicity (and performance) reasons, we have decided to represent gradual items as integers, instead of pairs. A gradual item (i, v) will be encoded by the integer enc(i, v) such as:

enc(i, v) = 2i if (i, v) = (i, ↑) 2i + 1 if (i, v) = (i, ↓)
The even integers representing positive (ascending) variations and the odd integers representing negative (descending) variations. With this encoding, we force the items of I to be [0, n -1], with a renaming if necessary.

With such a coding of gradual items, ppc-extension for gradual itemsets is even closer of ppc-extension for itemsets: point (i) and (iii) are strictly identical, where i stands for the encoding of a gradual item and core i is applied on encoded gradual itemsets and returns itself an integer code instead of an item. To avoid confusion with item 0, we fix core i(⊥) = -1. For point (ii), we have to check the (encoded) value of core i. If it is an even value of the form enc(i, v) = 2i, it means that the gradual itemset P contains (i, ↑). It would not make sense to try to extend P with enc(i, v) + 1 = 2i + 1, corresponding to the gradual item (i, ↓). In this case we directly skip to enc(i, v) + 2, i.e. (i + 1, ↑). This verification is handled in lines 18-22 of Algorithm 2. Lines 23-27 show the ppc-extension itself, and are very similar to LCM.

The differences between LCM and GLCM lie first in a small optimization specific to gradual itemset in lines 14-15. Any gradual itemset, representing co-variations items, has a symmetric gradual itemset where the items are the same and the variations are all reversed. For example, the symmetric of {(1, ↑), (2, ↓), (3, ↑)} is {(1, ↓), (2, ↑), (3, ↓)}, supported by the same tid sequences but in the reverse order. It is redundant to compute a gradual itemset and its opposite, so we arbitrarily decided to compute only gradual itemsets whose first variation is ascending, they represent themselves and their opposite as well.

The computation of support in line 11 is standard for gradual itemsets: we compute the longest transaction sequence supporting P . More interesting is the computation of closure, shown in Algorithm 3. As a pre-processing, at the initialization of the algorithm we compute for each gradual item the sequence of tuples corresponding to the order for that item (line 3 in Algorithm 2). We then encode this sequence in a binary matrix in the same way as [START_REF] Jorio | Mining frequent gradual itemsets from large databases[END_REF]: columns and lines represent tids. If a transaction t i is before L enc(i,v) ← tid sorted in v order of item i value GlcmLoop({e}, T , B, ε) 9: end for end if 28: end for a transaction t j in the sequence, then there is a 1 in the corresponding binary matrix. This is a matrix encoding for graphs, where the graph is simply the sequence of tids.

Example: Let us consider a gradual itemset P supported by two lists of tuples tids: < t 1 , t 3 , t 2 > and < t 5 , t 3 , t 4 >. Then the binary matrix B P encoding these sequences is shown below:

Transaction id t1 t2 t3 t4 t5 t1 1 1 1 0 0 t2 0 1 0 0 0 t3 0 1 1 1 0 t4 0 0 0 1 0 t5 0 0 1 1 1
The binary matrices contain all the necessary information to make the computations of the f and g closure functions, as shown in Algorithm 3.

Di Jorio et al. [START_REF] Jorio | Mining frequent gradual itemsets from large databases[END_REF] have shown that given two gradual patterns P and Q and their respective binary matrix representations B P and B Q , the binary matrix of P ∪ Q was BM & = B e 16: end for 17: return BM ; B P ∪Q = B P AND B Q . This is exactly what we need for closure function g: we give it a gradual pattern P as input, and want all the transaction sequences supporting P . By ANDing all the binary matrices of the items in P (lines [START_REF] Arimura | An output-polynomial time algorithm for mining frequent closed attribute trees[END_REF][START_REF] Berzal | An alternative approach to discover gradual dependencies[END_REF][START_REF] Hüllermeier | Association rules for expressing gradual dependencies[END_REF][START_REF] Laurent | Pgpmc: Towards a multicore parallel approach for mining gradual patterns[END_REF], we obtain the binary matrix of P , B P . This matrix encodes the graph representing the order between tuples supporting P . To get the actual sequences, we would have to find all the longest pathes in this graph. However as the result of g is directly passed to f , and that f can directly work with the matrix B P , we can avoid this step.

f itself takes a set of sequences of tid, here encoded in a binary matrix BM . It has to check for each item if the variations of this item are compatible with each of the input sequences. This comes to check if all the 1 in the input matrix BM can be found in the matrix of item i, B i (remember that if B[x, y] = 1, it means that t x < t y for the gradual itemset associated to B). We thus AND BM and B i for each item i, and keep only the items i such that BM AND B i = BM .

The use of binary matrices has the advantage to avoid costly computations with sequence and graph structures, and lead to compact structures thanks to bitmap representation.

Complexity: The GLCM algorithm makes a depth first exploration of a covering tree over all the closed frequent gradual itemsets. Like LCM, it's complexity is thus linear in the number of closed frequent gradual itemsets to find.

For each closed frequent gradual itemset, the complexity of support computation comes to find the longest path in a graph, which as been proven to be linear in the number of nodes of the graph for directed acyclic graphs, i. GLCM inherits from LCM its good complexity properties. Especially, its space complexity do not depend on the number of closed frequent gradual itemsets to find. This allow in practice to run with a very low and near constant memory usage, whereas other algorithms can use exponentially more memory.

C. Parallelization

The existing work for discovering frequent gradual itemsets, Grite [START_REF] Jorio | Mining frequent gradual itemsets from large databases[END_REF], has been parallelized as the Grite-MT algorithm in order to exploit multicore processors, with good results [START_REF] Laurent | Pgpmc: Towards a multicore parallel approach for mining gradual patterns[END_REF].

We also give a simple parallelization for the GLCM algorithm in this paper, which is based on the works for parallelizing LCM [START_REF] Negrevergne | Discovering closed frequent itemsets on multicore: Parallelizing computations and optimizing memory accesses[END_REF]. The authors have defined a parallelism environment, Melinda, that simplifies the parallelization of existing sequential algorithms by relieving the algorithm designer of the burden of manual thread synchronization while being efficient for recursive algorithm.

Melinda is based on the Linda approach [START_REF] Gelernter | Multiple tuple spaces in linda[END_REF]. It consists of a shared memory space, called TupleSpace. All the threads can access the TupleSpace, and either deposit or retrieve a data unit called Tuple, via the two primitives get(T uple) and put(T uple). All the synchronizations for accessing the TupleSpace are handled by Melinda.

PGLCM is the parallel implementation of GLCM, using Melinda, shown in Algorithm 4. In PGLCM, the tuples correspond to recursive calls. A tuple will thus simply be a closed gradual itemset P that would normally have been passed in parameter to GlcmLoop. The other arguments of GlcmLoop are constants after initialization, so for sake of efficiency they are treated as global variables accessible by all threads and do not need to be passed in the tuples.

Instead of recursive calls (lines 8 and 26 of GLCM), PGLCM only creates a new tuple in the TupleSpace: put(P ) (lines 8 and 27 in PGLCM). This means that there is new node of the covering tree to explore.

The threads themselves execute the code of Algorithm 5.

As soon as a thread is idle, it asks for a tuple in order to work on a new node of the search tree (line 2 of Algorithm 5). Melinda enforce locality properties, so a thread of a given processor is most likely to receive tuples that it has put before, and whose corresponding data will already be in the cache of the processor. L enc(i,v) ← tid sorted in v order of item i value 4:

B enc(i,v) ← bitmap matrix associated to L enc(i,v) 5: end for 6: B ← {B 1 , ..., B 2×|I| } 7: for all gradual item encoding e ∈ [0, 2 × |I| -1] do

IV. EXPERIMENTS

We present in this section an experimental study on the execution time and memory consumption of GLCM and PGLCM. We first present comparative experiments between our new algorithms and the current state of the art, Grite (sequential) [START_REF] Jorio | Mining frequent gradual itemsets from large databases[END_REF] and Grite-MT (parallel) [START_REF] Laurent | Pgpmc: Towards a multicore parallel approach for mining gradual patterns[END_REF]. The comparison is "unfair": GLCM/PGLCM compute only the closed frequent gradual itemsets, whereas Grite/Grite-MT compute all the frequent gradual itemsets. However, there exist no algorithm (before GLCM) for mining closed frequent gradual itemsets. The experiments in the paper defining the notion of closure for gradual itemsets [START_REF] Ayouni | Mining closed gradual patterns[END_REF] rely on a post-processing of the results of Grite, which takes even more time than running Grite alone.

Thus, our experiments reflect the fact that up to now the only way to get gradual itemsets was to use Grite/Grite-MT, and we show the advantage of using our approach instead.

The comparative experiments are based on synthetic datasets produced with the same modified version of IBM Synthetic Data Generator for Association and Sequential Patterns as the one used in [START_REF] Jorio | Mining frequent gradual itemsets from large databases[END_REF], [START_REF] Laurent | Pgpmc: Towards a multicore parallel approach for mining gradual patterns[END_REF].

All the experiments are conduced on a 4-socket server with 4 Intel Xeon 7460 with 6 cores each, for a total of 24 cores. The server has 64 GB of RAM. We compare our C++ implementation of GLCM/PGLCM with the original C++ implementation of Grite/Grite-MT.

A. Comparative experiments: sequential

The first experiment compares the run time and memory usage for GLCM and Grite. The dataset used, C1000A20, has 1000 transactions and 20 items. Figure 2 shows the execution time for both programs when varying the support, with a logarithmic scale for time. Figure 3 shows the memory usage. The execution time results show that GLCM is two orders of magnitude faster that Grite for handling this small dataset: for the lowest value it answers in 29s, while Grite needs 1 hour and 40 minutes. Both programs have a low memory usage on this small dataset. As expected GLCM memory usage is constant whatever the support value, while for lower support values Grite increases its memory usage, because it depends on the number of frequent gradual itemsets to find.

B. Comparative experiments: parallel

The next experiment compares the scaling capacities of PGLCM and Grite-MT on several cores, for the dataset C500A50 with 500 transactions and 50 items. This dataset is more difficult than the previous one, as the complexity lies in the number of items which determines the number of (closed) frequent gradual itemsets. Figure 4 shows the execution time for both algorithms w.r.t. the number of threads, with a logarithmic scale for time. Figure 5 shows the speedup w.r.t. sequential execution for both algorithms. Last, Figure 6 shows the memory consumption. In this experiment with a more complex dataset, PGLCM is again two orders of magnitude faster than Grite-MT. With all 24 threads, PGLCM completes execution near instantly in 1.4s, while Grite-MT needs 335s. The memory usage does not change much whatever the number of threads for both programs. Grite-MT exhibits a better speedup than PGLCM on this experiment. However, the run times for PGLCM get very low with more than 8 threads: they are between 1 and 2 seconds. There may not be enough work for PGLCM to exploit all 24 threads.

We thus did the same experiment with C800A100, a more complex dataset with 800 transactions and 100 items. Grite-MT could not run for this dataset: it filled up the 64 GB of RAM of our machine and could not complete. This excessive memory consumption was already mentioned in [START_REF] Laurent | Pgpmc: Towards a multicore parallel approach for mining gradual patterns[END_REF], and comes from the fact that memory complexity in Grite/Grite-MT, like in Apriori, depends on the number of frequent gradual itemsets to find. PGLCM does not have this problem, we thus report its run time in Figure 7, the speedup in Figure 8 and the memory consumption in Figure 9.

For this more complex problem the run time with 24 cores is 48s, so there is enough computation to keep the program busy. The speedups are far better in this case, with an excellent speedup of 22.15 for 24 threads. The granularity of our parallelization is well adapted to complex datasets. For further works, it could be interesting to be able to decompose the computations in lower granularity tasks when faced with simpler datasets such as C500A50.

C. Using PGLCM to mine real-world data

We have also run experiments on a real dataset of DNA micro-arrays describing gene expressions in the framework of breast cancer. The data are described over 4, 408 genes which correspond to the items, there are 108 transactions. This dataset is very complex, and up to now no algorithm was able to process it in order to extract gradual patterns. We could run PGLCM with 24 threads on this dataset. The run times for different support value are presented in Figure 10. Memory consumption remained constant at 17 GB. This dataset is much more complex than the synthetic datasets presented before: this time PGLCM needed nearly 16 hours to give results for the lowest support value tested. However, the important point is that for the first time gradual itemsets could be mined from this gene expression dataset. Correlation between expression values of genes is very important to determine gene regulations, our algorithms thus opens the way for new methods for analyzing gene expression data, and many other numerical datasets.

V. CONCLUSION AND PERSPECTIVES

We have presented in this paper GLCM, the first algorithm for directly mining closed frequent gradual itemsets. Such gradual itemsets allow to find covarations between numerical attributes, with many applications to real data.

Our algorithm is based on the ppc-extension idea developed in the LCM algorithm, and which is currently the most efficient way to mine closed patterns, with a time complexity linear in the number of results to find and a memory complexity constant w.r.t. the number of results to find.

We also parallelized our algorithms in order to exploit the computing power of recent multicore processors.

Our experimental study have shown that our approach, either sequential or parallel, is two orders of magnitudes faster than the state of the art. Our parallel algorithm scales well with the number of available cores for complex datasets, where such computing power is really needed. The low memory requirements of our algorithm allow it to handle large real world datasets, which could not be handled by existing algorithms due to memory saturation. Our algorithms thus removed the lock that prevented the use of gradual patterns analysis in realistic applications.

Our work opens several perspectives. An immediate perspective is to cooperate with practitioners having large numerical datasets, in order to help them extracting and analyzing gradual datasets. Reporting the results of such experiments will allow to show the practical interest of gradual pattern and hopefully lead to further research in the field of gradual pattern mining.

Other perspectives lie in the improvement of our algorithms. Currently, our algorithm always uses the same binary matrices whatever the gradual itemset under consideration. However [START_REF] Jorio | Mining frequent gradual itemsets from large databases[END_REF] has shown that the binary matrices could be reduced: some transactions never appear in the support of a pattern, so the corresponding lines and columns can be suppressed from the corresponding binary matrix. This optimization would not reduce the theoretical complexity, however the FIMI workshop results [START_REF] Goethals | Fimi repository website[END_REF], [START_REF] Uno | An efficient algorithm for enumerating closed patterns in transaction databases[END_REF] showed that reducing databases was one of the keys for reducing practical run time.

Algorithm 2 GLCM 1 :

 21 Algorithm Input: T :transaction database, ε:minimum support 2: for all gradual item (i, v) ∈ I × {↑, ↓} do 3:

4 :B

 4 enc(i,v) ← bitmap matrix associated to L enc(i,v) 5: end for 6: B ← {B 1 , ..., B 2×|I| } 7: for all gradual item encoding e ∈ [0, 2 × |I| -1] do 8:

k

  = core i(P ) 20: else 21: k = core i(P ) + 1 22: end if 23: for e = k + 1 to 2 × |I| -1 do 24: Q = Clo(P ∪ {e}, B) ; 25: if P (e -1) = Q(e -1) then 26: GlcmLoop(Q, T , B, ε) ; 27:

Algorithm 3 Functions Clo and G 1 : 3 : 12 :

 31312 Function Clo(P, B) 2: return F (G(P, B), B) ; Function F(BM, B) 4: P ← ∅ 5: for all gradual item encoding e ∈ [1, 2 × |I| -1] do Function G(P, B) 13: BM ← B P [0] 14: for all gradual item encoding e ∈ P do 15:

  e. O(||T ||) in our case. The complexity of closed frequent itemset computation is thus, like LCM, dominated by closure computation. Analyzing Algorithm 3 shows that f and g both loop on the items, and make binary matrix computations inside the loops. The time complexity of Clo is thus O(|I| × ||T || 2 ). Closure operation is embedded in a loop on items in GlcmLoop, so the overall time complexity per closed frequent gradual itemset is O(|I| 2 × ||T || 2 ). The space complexity mainly depends on the storage of the initial database and of the binary matrices for items, this gives a space complexity of O(||T || + |I| × ||T || 2 ).

Algorithm 4 PGLCM 1 :

 41 Algorithm Input: T :transaction database, ε:minimum support, N : number of threads 2: for all gradual item (i, v) ∈ I × {↑, ↓} do 3:

k 5

 5 = core i(P ) + 1 23: end if 24: for e = k + 1 to 2 × |I| -1 do 25: Q = Clo(P ∪ {e}, B) ; 26: if P (e -1) = Q(e -1) then Function threadFunction() 1: while get(tuple) do 2: P ← tuple.pattern;

  end whileWhen there are no more tuples in the TupleSpace and no thread working, Melinda sends a termination signal, and the program stops.

Figure 2 .

 2 Figure 2. Time vs support, sequential

Figure 3 .

 3 Figure 3. Memory vs support, sequential

Figure 4 .

 4 Figure 4. Time vs #threads

Figure 6 .

 6 Figure 5. Speedup

Figure 9 .

 9 Figure 7. Time vs #threads

Figure 10 .

 10 Figure 10. Time vs support, 24 threads

  Table I, it can be seen that t 1 and t 2 can be ordered with respect to P 1 as t 1 .age ≤ t 2 .age AN D t 1 .salary ≤ t 2 .salary: we have t 1 P t 2 .

  Figure 1. Example of LCM execution, circled itemsets are the closed frequent itemsets, boxed items are core i values.

								1	2		3	4	5	6
			1 4 6				2			3		4	5	6
		2	3	5		3	4	5	4	5	6	5	6	6
	1 2 4 6	1 3 4 6		1 4 5 6	2 3	2 4		2 5	3 4	3 5	3 6	4 5	4 6	5 6
					5	6		6
					2 4 5	2 4 6		2 5 6

The interested reader will have noticed that it is the same example database as in[START_REF] Uno | An efficient algorithm for enumerating closed patterns in transaction databases[END_REF]. However the support value is 3 here instead of

in[START_REF] Uno | An efficient algorithm for enumerating closed patterns in transaction databases[END_REF], hence the difference in output.

ACKNOWLEDGMENT

The authors would like to thank Benjamin Négrevergne for providing them the Melinda library.


Anne Laurent
email: anne.laurent@lip6.fr

QUERYING FUZZY MULTIDIMENSIONAL DATABASES: UNARY OPERATORS AND THEIR PROPERTIES

Keywords: Fuzzy Multidimensional Queries, Successive Queries, Combination of Queries

In this paper, we study the properties of flexible queries in the OLAP (On-Line Analytical Processing) framework, focusing on unary operators. For this purpose, we consider the model we have defined for fuzzy multidimensional databases. This model provides means to handle fuzzy data and flexible queries. The operators defined in this model are closed on the set of fuzzy hypercubes (hereafter cubes), which means that the result of each operator on a fuzzy cube is a cube. Thus, these operators can be nested into expressions. In this paper, the combination of several queries is investigated in order to study the possibility for the definition of an algebra to manipulate fuzzy cubes. This would provide a framework for query rewriting and, as a result, for query optimization.

Introduction

OLAP (standing for On-Line Analytical Processing) is a recent framework devoted to the fast analysis of multidimensional information [START_REF] Codd | Providing OLAP (On-Line Analytical Processing) to User-Analysts: An IT Mandate[END_REF] . It consists in a set of technologies to collect, store, and treat multidimensional data for analysis. It has appeared that the relational database model is not suitable for this type of applications devoted to analysis, and the multidimensional model has emerged to support OLAP [START_REF] Codd | Providing OLAP (On-Line Analytical Processing) to User-Analysts: An IT Mandate[END_REF] . The multidimensional model provides a framework to deal with data as multidimensional arrays.

However, no model is able to deal with fuzziness, neither for the representation of ill-defined data, nor for the handling of flexible queries. For this reason, a model for fuzzy multidimensional data representation and manipulation has been proposed [START_REF] Laurent | Bases de données multidimensionnelles floues[END_REF] . In this work, several operations are introduced with a view to apply them to discover relevant knowledge from fuzzy multidimensional databases. For this process, called Fuzzy-OLAP Mining 3 , successive queries (including combinations) are needed.

In this paper, we limit ourselves to unary operator definitions, and we study their properties when combining them. We aim at defining rules for query rewriting and optimization. The final goal of this study is to provide the model with an algebra to manipulate queries efficiently in a simple way. Binary operators are out of the scope of this paper but they have to be studied in order to deal efficiently with several fuzzy hypercubes.

In this paper, properties of operation combinations are studied in the way followed in papers on the relational algebra [START_REF] Ullman | Principles of Database Systems[END_REF] . The paper is organized as follows. Section 2 presents multidimensional databases and their fuzzy extension. Section 3 focuses on the choice of the operators in the model we propose. Sections 4 and 5 detail successive roll-up, slice, dice and projection operations. Section 6 deals with the combination of queries.

Multidimensional Databases

Multidimensional databases have emerged to support OLAP. They are devoted to the efficient treatment of large amounts of multidimensional data for analysis. There is no unique model for the definition of multidimensional databases [START_REF] Vassiliadis | A survey of logical Models for OLAP Databases[END_REF] . The next Section presents some common properties of all existing models.

Classical Model

Roughly speaking, a multidimensional database is a set of hypercubes. Each hypercube is defined by means of dimensions. A dimension of particular interest is chosen to be the measure and its values are stored inside the hypercube, in the cells. Hierarchies may be defined on dimensions in order to deal with several levels of granularity. Fig. 1 shows a cube describing sale results by means of three dimensions P RODU CT , DIST RICT and M ON T H. The slice operation consists in selecting slices from the cube by using a criterion on a dimension, for instance to select sales that have occurred in ATLANTA. The dice operation consists in selecting a subset of cells matching a criterion on the measure, for instance to select sales between 50, 000 and 80, 000 units. The projection operation consists in deleting one or several dimension(s), for instance to describe sale results by means of only two dimensions instead of three. The roll-up operation consists in describing the cell values at some higher level of granularity on a dimension, for instance by rolling a cube up from the level of months to the level of quarters. The sum, mean or any other function may be considered in order to get the sale results at this new level of granularity.

However, data from the real world are often imperfect, either because they are imprecise (the age is young), or because they are uncertain (the age is perhaps 18). A model has been defined for multidimensional databases in order to represent and manipulate these data 2 . This model handles also flexible multidimensional queries. For instance, the subset of data corresponding to the age young may be extracted.

Fuzzy Model

A fuzzy multidimensional database contains elements which may be imperfectly defined, imprecise and/or uncertain. Given a reference set (R for instance), an element is a pair (v, d) where v is a value which may be precise (25) or defined by a fuzzy set (for example young) and d (d ∈ [0, 1]) is the confidence degree associated with this value. A domain is a finite set of elements.

A dimension is defined on a given domain. The pair (v

(d i ), d(d i )) represents an element d i of dimension D i . PRODUCT DISTRICT µ µ µ µ = 0.7 = 1 = 1 = 1 (82800,0.8) ( ( ( ) ) ) ,0.8 ,1 ,1 µ µ

Fig. 2. Example of a fuzzy cube

A fuzzy cube is defined as a mapping:

D 1 × . . . × D k → D C × [0, 1]
where D 1 , . . . , D k are dimensions, and D C is the measure. A degree ranging from 0 to 1 is associated to each cell element to denote the extent to which the cell belongs to the cube. This degree is denoted by µ.

Thus the model handles degrees indicating to which extent entities (slices of the cube and cells) belong to the cubes. These degrees may come from the data themselves (e.g., degrees of reliability of heterogeneous sources providing data) or from the fuzzy operations successively applied to the cube (selection of values matching a fuzzy criterion).

-→ x denotes the cell identified by a set of values describing its position on all the dimensions. For instance, a cell is identified by its position (T ents, January, Atlanta) on dimensions P RODU CT, M ON T H, DIST RICT. An element in a cell -→ x of a cube is denoted (v( -→ x ), d( -→ x )) where v( -→ x ) is the value contained in the cell, and d( -→ x ) the degree of confidence associated with this value.

Moreover, each cell -→ x is associated with a degree µ corresponding to the extent to which this cell belongs to the cube. This degree thus applies on the whole information given by the dimension positions and the cell value. An example is given by Fig. 2.

As for relational databases, there may be two definitions of the equivalence of two cubes, based either on the structure of the cube (mapping), or on the content of the cube (element values). In the sequel of this paper, we consider two fuzzy cubes as equivalent if the following conditions are fulfilled:

• the 2 cubes are defined on the same dimensions,

• active domains of all the dimensions are the same (the elements taken from the cubes are the same ones -values and degrees)

• the 2 cubes contain exactly the same cells (same elements, same degrees µ).

For the sake of simplicity, a query is said to be equivalent to another if it produces an equivalent cube.

Operations are defined, providing tools to manipulate cubes by means of flexible OLAP queries. They are briefly described below and will be further studied in Section 3. For each operation, C denotes the cube on which the operation is performed, and C the resulting cube.

Fuzzy Dice. The first type of query is a selection over the cells of the cube. The degrees µ of membership of cells are modified according to the satisfaction of the value v( -→ x ) in the cell, the former degree µ C ( -→ x ) and the degree of confidence d( -→ x ). The satisfaction of the value to the criterion O is computed by means of a so-called measure of satisfiability C 6 . We denote by µ O the membership function of criterion O. For each cell -→ x , the membership degree after selection is computed as follows:

µ C ( - → x ) = T (C(µ O , v( - → x )), d( - → x ), µ C ( - → x )) (1)
where

T : [0, 1] × [0, 1] × [0, 1] → [0, 1
] is defined for instance from a t-norm as T (x, y, z) = (x, (y, z)) ∀(x, y, z) ∈ [0, 1] 3 . Note that in our model, the chosen formula does not take the degree of confidence into account when comparing the value to the criterion. Another solution would be to merge first the value with its degree of confidence but we do not adopt this solution. The degree of confidence behaves as an upper bound, or a threshold.

Also note that for the fuzzy sets we consider, membership degrees are not interpreted as possibility degrees, but as degrees of truth. No disjunctive interpretation is supposed. This is the reason why theory of possibility (with necessity/possibility measures) is not carried. Fuzzy Slice. The second type of query is a selection over some dimension. For each value d i of the considered dimension, the new degree d C (d i ) is computed according to the former degree d C (d i ) and the extent to which the value satisfies the selection criterion O. Therefore, for each d i of the dimension, we have:

d C (d i ) = (C(µ O , v(d i )), d C (d i )) (2)
Fuzzy Roll-Up. This operation consists in the generalization of a cube at a higher level of granularity. Choosing a dimension and a hierarchy on this dimension, rolling a cube up results in a modification of the active domain of the dimension: values are taken from the new level of granularity, and degrees of membership of each slice are computed according to the degrees of the children of each value from the former cube. Cell elements are modified according to the function of aggregation.

For instance, a count function may be chosen in order to summarize a cube at a high level of granularity. Computations are detailed below.

Let C be a fuzzy cube to roll-up, and dim the dimension to be generalized. Let h be the considered hierarchy, defined by a fuzzy relation R. The roll-up operation is performed from the level of granularity L 1 to the level L 2 , using the function φ. Let C be the resulting cube. We have:

C (dim,h,L1,L2,φ) ----------→ roll-up C
For each value b on dimension dim from level L 2 , coefficients indicating to which extent each value a from level L 1 generalizes into b are considered. If the hierarchy is defined by means of a fuzzy relation, then these coefficients are computed using the transitive closure of R. If the hierarchy is defined by means of fuzzy partitions, then these coefficients are computed using the degree of membership of each value a to the fuzzy set describing b. c(a, b) denotes the coefficient of transition between values a ∈ L 1 and b ∈ L 2 .

In the resulting cube C , the degrees µ in cells and the degrees on slices are modified. They are computed according to previous values and coefficient of transition between values from levels L 1 and values from level L 2 . Concerning slice degrees, the same operation is performed. Note that each element e from the domain of the dimension dim to be rolled up is like (v(e), d(e)).

For each element e 2 in the resulting cube such that v(e 2 ) = b and b ∈ L 2 , we have:

d C (e 2 ) = max {e1|v(e1)=a} min(c(a, b), d(e 1 ))
Note that drill-down is not altered by the introduction of fuzziness. Fuzzy Projection. This operation is not modified by the extension of the model to fuzziness. The projection is possible only if the domains of all dimensions to destroy (the ones that are not selected) are reduced to a singleton [START_REF] Agrawal | Modeling Multidimensional Databases[END_REF] . This means that a roll-up operation may be required before applying a projection.

Further Study of the Operators

This section focuses on the choice of operators for equations ( 1) and ( 2). For this purpose, both the semantic of the operators and the efficiency of computations have to be taken into account. Indeed, fast computations are required, due to the huge amount of data. For this reason, we require our model to be consistent with the classical case, in order to deal with the classical case as often as possible, letting the classical multidimensional database management system work.

Comparing the value with the criterion

Here, we focus on the choice of the measure C used to compare the value to the criterion. We need comparison measures between fuzzy subsets to determine to which extent two fuzzy values are similar. In our case, we will have to evaluate the satisfiability of a value to a reference description (a fuzzy criterion described by its membership function). This requires a particular kind of measure of resemblance which must enable the measurement of the inclusion of a (classical or fuzzy) description V into a reference REF and must produce a single value in order to be easily understandable. Such measures are called measures of satisfiability [START_REF] Bouchon-Meunier | Towards general measures of comparison of objects[END_REF] . We use the notation C for these operations. In the proposed model, the chosen measure is the following one:

C(V, REF ) = M (V ∩REF ) M (V ) if M (V ) = 0 0 otherwise
where

M (A) = x∈Ω f A (x) if Ω is countable Ω f A (x)
dx otherwise This measure is chosen because it is consistent with the classical case. It is equivalent to the classical case when considering a precise value. This property is interesting because it enhances performances when dealing with precise data. The proof of consistency is very easy:

We denote by µ REF and µ V the membership functions describing the criterion REF and the data V . If the data is precise then it is a singleton {x 0 } such that for all x = x 0 , we have µ V (x) = 0 and µ

V (x 0 ) = 1. Thus we have M (V ∩ REF ) = µ REF (x 0 ) and M (V ) = 1.
The computation is thus reduced to the computation of the membership degree of x 0 to the fuzzy set representation of the criterion:

C(V, REF ) = µ REF (x 0 )

Aggregation operator

Most of the existing relational fuzzy querying models consider precise data and fuzzy criteria [START_REF]Fuzziness in Database Management Systems[END_REF] . In our model, we have to take into account first the fact that both data and criteria may be fuzzy, and second the fact that all the successive operators applied are closed on the set of fuzzy cubes. Thus in order to compute the degree µ of each cell after a dice operation, we have to aggregate the degrees representing:

• the appropriateness of the value to the vague criterion,

• the degree of confidence in the value of the cell, and

• the degree µ from the former cube.

The properties below have to be fulfilled by this operator for the semantic of the operation, and for computational reasons.

Level of membership. After a selection, a cell cannot belong to the cube at a higher degree than the previous one or than the satisfaction of the criterion. This leads to consider an operator such that for all (x, y, z) ∈ [0, 1] 3 , T (x, y, z) ≤ min(x, y, z). As a consequence, 0 is an absorbent element: T (x, y, z) = 0 if x, y or z equals 0. A t-norm is suitable.

Monotonicity (decreasing). The result of the aggregation must decrease when decreasing one or several degrees: T (x , y , z ) ≤ T (x, y, z) if x ≤ x and y ≤ y and z ≤ z.

Idempotence. Idempotence may be required in order not to alter the membership degree of a cell when the degree of appropriateness for the value is the same as the former degree µ. This would lead to the choice of the t-norm min, which is the only idempotent one, to construct T . This choice is very interesting when considering successive selections by the same criterion, since it guarantees the stability of the result. Any other t-norm would modify the resulting degree in a counter-intuitive way. This is the reason why the current implementation of the system uses this t-norm min. We have thus ∀x ∈ [0, 1], T (x, x, x) = x.

However, in the case of successive selections by different criteria, it would be also interesting to weaken the degree µ each time a selection is performed to data which do not completely fulfill the criterion. For this reason, a t-norm like the product may be considered.

Commutativity and associativity. These properties allow the system to enhance performances since it can optimize the order of computations. T-norms are commutative and associative, thus the t-norms min and product, among others, are suitable.

Concerning the slice operation, the C measure and the operator have to be chosen. As previously, we argue that a slice cannot belong to the cube with a higher degree than the previous degree or than the degree of satisfaction of the criterion. This would be counter-intuitive to obtain a degree higher than the former one after a selection operation. Thus depending on whether the idempotence is required or not, the chosen t-norm is either min or product (these operators are both common and available in classical multidimensional database management systems).

The Need for Successive Queries

This paper is devoted to the study of successive queries. This study is motivated by several reasons.

First, Fuzzy OLAP Mining requires the application of combinations of queries. For instance, building a fuzzy decision tree requires successive slice, successive dice in order to build the successive partitions of the data set. Moreover, successive operations and combination of queries are needed when navigating through the data, especially when dealing with hierarchies for successive roll-up operations. Finally, this study is motivated from the theoretical point of view in comparison with the classical relational and multidimensional models, where the study of operator properties is a classical task, especially for query optimization 4 .

Successive Roll-Up Operations

This section focuses on roll-up. This operator aggregates the data from a level of granularity to a higher one (for instance from the level of districts to the level of regions). An operator φ is thus required in order to merge cell values (e.g. sum, average). We study here the result of two successive roll-up operations on the same dimension, for a hierarchy defined by a fuzzy relation. We are given:

• dim the dimension to roll up,

• R the fuzzy order relation defining the hierarchy (we denote by f R the membership function of R and by f RT the membership function of its maxmin transitive closure),

• {L i } levels of granularity from the hierarchy (for all i, L i ⊆ dom(dim)),

• and φ the function used to merge cell values.

We compare the results of operations ( 3) and (4).

C (dim,R,L1,L2,φ) -----------→ roll-up C (dim,R,L2,L3,φ) -----------→ roll-up C 1 (3)
C (dim,R,L1,L3,φ) -----------→ roll-up C 2 (4)
Proposition. Let C be a cube to be rolled up by function φ on dimension dim structured by hierarchy R. Let L 1 be the level of granularity of C, and L 2 and L 3 two higher levels of granularity. Degrees on slices and µ degrees in cells are the same by direct roll-up (from L 1 to L 3 in cube C 2 ) or indirect roll-up (first from L 1 to L 2 in cube c and then from L 2 to L 3 in cube C 1 ):

• For all - → x , we have d C2 ( - → x ) = d C1 ( - → x ) and µ C2 ( - → x ) = µ C1 ( - → x ).
• For all c n ∈ L 3 , we have

d C2 (c n ) = d C1 (c n ).
Proof. Let us consider query (3), we have:

∀c n ∈ L 3 , d C1 (c n ) = max b l ∈L2
min( max

a k ∈L1 min(d(a k ), f RT (a k , b l )), f RT (b l , c n ))
Considering query (4), we have:

∀c n ∈ L 3 , d C2 (c n ) = max a k ∈L1 min(d(a k ), f RT (a k , c n )) Besides, f RT (a k , c n ) = max b l ∈L2 min(f RT (a k , b l ), f RT (b l , c n )) Thus d (c n ) = max a k ∈L1 min(d(a k ), max b l ∈L2 min(f RT (a k , b l ), f RT (b l , c n ))) Hence we have d C2 (c n ) = d C1 (c n )
The same holds for degrees µ.

Aggregate functions * used for the construction of cubes and the computation of super-aggregates (aggregates of aggregates) are of several kinds [START_REF] Gray | Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tabs, and Sub-Totals[END_REF] . Aggregate functions can be distributive (e.g. count, min, max), algebraic (e.g. average), or holistic (e.g. median). The two first categories of functions allow optimizations while the third one requires a direct computation from the whole database. For instance, the minimum value can be easily computed using a lower level, since it is associative. For counting, a sum has to be applied on the intermediate level, while average requires two values to be handled (count and sum). However in this paper, neither the construction of the cubes nor the semantic of the measures are studied. Thus this question is out of the scope of this paper. Note that the problem described here is not due to the introduction of fuzziness and that is the same in classical multidimensional databases. Only associative aggregate functions (which are parts of distributive ones) result in the equality of equations ( 3) and ( 4). Associativity guarantees that values obtained directly by computing the resulting cube from level L 1 to level L 3 are the same as using an indirect computation by first rolling the cube up to level L 2 .

Successive Slice, Dice and Projection Operations

This section focuses on the methods for query rewriting and studies the rules that are applicable in our framework. These properties are quite the same as in the relational framework and guarantee that some optimization may be done 4 .

Successive Dice Operations

Due to the commutativity property of t-norms, the result of two successive selections on the cells is independent of the order:

C γ1 --→ dice C γ2 --→ dice C 1 ( 5
)
is equivalent to:

C γ2 --→ dice C γ1 --→ dice C 2 (6)
Proposition. Given C 1 the cube obtained by applying a selection on the cells of the cube by the criterion γ 1 followed by a selection by the criterion γ 2 , and C 2 the cube obtained by applying a selection on the cells of the cube by the criterion γ 2 followed by a selection by the criterion γ 1 , we have

C 1 = C 2 .
Proof. This amounts to show that each cell contains the same degree µ since this degree is the only one that is modified by a dice operation. µ γ1 (resp. µ γ2 ) denotes the membership function of γ 1 (resp. γ 2 ). Due to associativity and commutativity properties of t-norms, we have:

∀ - → x , µ C1 ( - → x ) = T (C(v( - → x ), µ γ2 ), d( - → x ), T (C(v( - → x ), µ γ1 ), d( - → x ), µ C ( - → x ))) = T (T (C(v( - → x ), µ γ2 ), d( - → x ), µ C ( - → x )), C(v( - → x ), µ γ1 ), d( - → x )) = T (C(v( - → x ), µ γ1 ), d( - → x ), T (C(v( - → x ), µ γ2 ), d( - → x ), µ C ( - → x ))) = µ C2 ( - → x )
Remark. Note that the only way to get

C 1 = C (= C = C 2 ) by applying twice the same selection (γ 1 = γ 2 ) is to consider an idempotent t-norm. Indeed, if for each cell - → x , T (C(v( - → x ), µ γ ), d( - → x ), T (C(v( - → x ), µ γ ), d( - → x ), µ C ( - → x ))) is equal to T (C(v( - → x ), µ γ ), d( - → x ), µ C ( - → x
)) then T is necessarily built using the tnorm min.

Successive Slice Operations

The proof of the commutativity is very simple, and it is quite the same as the previous one for the dice operation. When applying a selection on a dimension by criteria γ 1 and γ 2 , the order has no effect on the resulting cube:

C (D,γ1) ----→ slice C (D,γ2) ----→ slice C 1 (7)
is equivalent to:

C (D,γ2) ----→ slice C (D,γ1) ----→ slice C 2 (8)
Proposition. Denoting C the first cube, D the dimension on which the selection is applied, dom(D) its domain, C 1 (resp. C 2 ) the cube obtained by selection first by criterion γ 1 (resp. γ 2 ) and then by criterion γ 2 (resp. γ 1 ).

Proof.

∀d i ∈ dom(D), d C1 (d i ) = (C(v(d i ), µ γ2 ), (C(v(d i ), µ γ1 ), d C (d i ))) = ( (C(v(d i ), µ γ2 ), C(v(d i ), µ γ1 ), d C (d i ))) = (C(v(d i ), µ γ1 ), (C(v(d i ), µ γ2 ), d C (d i ))) = d C2 (d i )
Remark. Note that, as mentioned above, the only way to get the same cube by applying twice the same selection (γ 1 = γ 2 ) is to consider an idempotent t-norm. If for each slice

d i ∈ dom(D), (C(v(d i ), µ γ ), (C(v(d i ), µ γ ), d(d i ))) is equal to (C(v(d i ), µ γ ), d(d i )
) then is the t-norm min.

Cascade of Projections

Considering a set of dimensions {A 1 , ..., A n , B 1 , ..., B m } such that {A 1 , ..., A n } ⊆ {B 1 , ..., B m }, we know that the two queries ( 9) and (10) are equivalent. This is analogous to the classical model by Agrawal and al. [START_REF] Agrawal | Modeling Multidimensional Databases[END_REF] :

C {B1,...,Bm} --------→ P roj C {A1,...,An} -------→ P roj C 1 (9)
C {A1,...,An} -------→ P roj C 2 (10)
Indeed, the projection is the operation consisting in selecting a set of dimensions by destroying the other ones (whose active domains have to be reduced to singletons). In this case, since the set of A i 's is among the set of B i 's, limiting directly the dimensions to the A i 's leads to the same result as limiting first to the B i 's and then to the A i 's.

Splitting Criteria

This section studies if there are equivalences between successive queries using two criteria and a single query using the conjunction of these criteria.

Cascade of Dice Selections

We study here if query (11) is equivalent to query (12), where ∧ stands for the conjunction of criteria. We show below that µ C1 is not equal to µ C2 in any case (see Fig. 3). A counterexample may be considered. In the case the following conditions are true, µ C1 is different from µ C2 :

C γ1 --→ dice C γ2 --→ dice C 1 (11) C γ1∧γ2 ----→ dice C 2 (12)
• γ 1 ∩ γ 2 = ∅, • v ∩ γ 1 = ∅, • v ∩ γ 2 = ∅,
• T is built using a strict t-norm (such that (a, b) > 0 if a > 0 and b > 0).

For each -→ x , we have:

µ C2 ( - → x ) = T (C(v( - → x ), µ γ1∧γ2 ), d( - → x ), µ C ( - → x )) and µ C1 ( - → x ) = T (C(v( - → x ), µ γ2 ), d( - → x ), T (C(v( - → x ), µ γ1 ), d( - → x ), µ C )) = T ( (C(v( - → x ), µ γ1 ), C(v( - → x ), µ γ2 )), d( - → x ), µ( - → x )) Thus C(v( - → x ), µ γ1 ) = 0 and C(v( - → x ), µ γ2 ) = 0. Besides, C(v( - → x ), µ γ1∧γ2 ) = 0 since v( - → x ) ∩ γ 1 ∩ γ 2 = ∅. Thus (C(v( - → x ), µ γ1 ), C(v( - → x ), µ γ2 )) = C(v( - → x ), µ γ1∧γ2 )
However, successive selections on the cells are often performed in order to refine a criterion, and there is no need to apply two successive criteria having an empty intersection. We focus thus on the cases where γ 1 ∩ γ 2 = ∅. Considering successive selections for the refinement of the selection criterion, we have γ 2 ⊆ γ 1 . If the used t-norm to aggregate the degrees is not idempotent then there exist some examples where the result is different when applying successively the two criteria or by applying simultaneously γ 1 ∧ γ 2 = γ 2 . If is the t-norm min then queries (11) and (12) are equivalent:

Proposition. We consider T built using the idempotent t-norm = min. Denoting C 1 the cube obtained by applying a selection on the cells of the cube by the criterion γ 1 followed by a selection by the criterion γ 2 , and C 2 the cube obtained by applying a selection on the cells of the cube by the criterion

γ 1 ∧ γ 2 , C 1 is equal to C 2 if and only if γ 2 ⊆ γ 1 . Proof. only if see above the counter-example if T (C(v( - → x ), µ γ2 ), d( - → x ), T (C(v( - → x ), µ γ1 ), d( - → x ), µ C ( - → x ))) = T ( (C(v( - → x ), µ γ2 ), C(v( - → x ), µ γ1 )), d( - → x ), µ C ( - → x )) Besides, C(v( - → x ), µ γ2 ) ≤ C(v( - → x ), µ γ1
) since γ 2 ⊆ γ 1 and C is monotonous, being a measure of satisfiability. Thus we have:

µ C1 = T ( (C(v( - → x ), µ γ2 ), C(v( - → x ), µ γ1 )), d( - → x ), µ C ( - → x )) = T (C(v( - → x ), µ γ2 ), d( - → x ), µ C ( - → x )) = T (C(v( - → x ), µ γ1∧γ2 ), d( - → x ), µ C ( - → x )) = µ C2

Cascade of Slice Selections

The problem is the same as previously, checking whether query (13) is equivalent to query (14), where ∧ stands for the conjunction of criteria. The slice operation, applied twice on the same dimension, either by two successive criteria, or by their conjunction, results in the same cube only if the second criterion is included within the first one.

C (D,γ1) ----→ slice C (D,γ2) ----→ slice C 1 (13) C (D,γ1∧γ2) -------→ slice C 2 (14)
Proposition. Denoting C 1 the cube obtained by applying a selection on the cells of the cube by the criterion γ 1 followed by a selection by the criterion γ 2 , and C 2 the cube obtained by applying a selection on the cells of the cube by the criterion

γ 1 ∧ γ 2 , C 1 is equal to C 2 iff: • γ 1 ⊆ γ 2 , • is idempotent ( = minimum)
The proof is the same as previously.

Combining Operators

Next subsections focus on projection, slice and dice combination properties. Problems appear when dealing with roll-up. However, we insist on the fact that this is not due to the introduction of fuzziness. The points described here are of the same kind in the classical models.

Commuting Slice and Dice

The slice and dice operations do not modify the same entities in the cube. Thus queries ( 16) and (15) are equivalent.

C γ1 --→ dice C (D,γ2) ----→ slice C 1 (15) C (D,γ2) ----→ slice C γ1 --→ dice C 1 (16)
Proposition. Slice and Dice operations can be applied successively without any effect of the order.

The proof of this property is obvious since these operations do not interact. The first operation modifies degrees d(d i ) on slices d i from the domain of dimension D while the second one modifies degrees µ inside cells.

Dealing with projections when combining queries

A projection operation results in the destruction of one or several dimensions. Moreover, note that the projection can only be performed if the dimension to destroy has an active domain containing a single value. Otherwise, a slice would have to be automatically chosen, which is not possible. Thus a slice operation reducing the active domain to a singleton may be required (or a roll-up). In this framework, the following queries are not applicable:

C D\{D} ----→ proj C (D,γ) ---→ slice C 1 C D\{D} ----→ proj C (D,h,L1,L2,φ) ---------→ roll-up C 1
where D stands for a set of dimensions, and D\D stands for a set of dimensions that does not include dimension D.

Commuting Selections and Projections

C D ---→ proj C (dim,γ) -----→ slice C 1 (17) C (dim,γ) -----→ slice C D ---→ proj C 1 (18)
A slice operation is not relevant if the dimension has been destroyed by a projection. If the projection and the slice do not apply on the same dimension, the order of the two successive operations has no effect on the resulting cube.

Proposition. If D ∩ {dim} = ∅ then a slice operation on dimension dim can be mixed with a projection on dimensions D whatever the order may be without modifying the result.

The proof of this property is obvious since the two operations (projection and slice) do not modify the same entities of the cube. Obviously, the same holds for dicing, without any restriction on the dimension(s) to be deleted by projection:

Proposition. A dice operation on dimension can be mixed with a projection whatever the order may be without modifying the result.

Commuting Roll-Up and Projection

Note that most of the time, a roll-up is necessary before a projection in order to reduce the active domain. If the dimension to roll-up is among the ones to be destroyed, then the roll-up must be performed first to the upper level where only one value is contained in the active domain. This level is usually called level ALL.

Proposition. If D ∩ {dim} = ∅ then a roll-up operation on dimension dim can be mixed with a projection on dimensions D whatever the order may be without modifying the result.

The proof of this property is obvious, since the projection operation does not modify the set of cells to be merged in order to compute the cube on the higher level of granularity.

Commuting Roll-Up and Selection (slice or dice)

Rolling a cube up modifies the active domain of a dimension to a higher level of granularity. It modifies the content of the cells (elements and µ degrees) as well. The compatibility of the criterion regarding the data has to be studied very carefully. For instance, selecting sales results by a criterion describing medium sales does not have the same effect depending on the level of granularity. This level of granularity depends on the roll-up operations previously applied. If the roll-up operation is applied using the aggregation function count or sum, the selection criterion is not compatible anymore with data after roll-up whereas it was compatible before.

For instance, we consider the cube describing cell results, Fig. 4 shows that the description of sales depends on the level of granularity. The sum of all units sold within a region is supposed to be greater than the number of units sold within a district. However, this definition depends on the function used to determine the cell values. If the average (or minimum, maximum, median . . . ) value is considered, then the definition of low, medium, and high sales does not depend on the level of granularity.

Conclusion

In this paper, we study the properties of unary operators over fuzzy cubes. This work is twofold. First it aims at studying operators of aggregation in order to deal with degrees of confidence and degrees of membership. Second, this work aims at studying the combination of unary operators in order to define an algebra.

In most cases, properties from the classical relational and multidimensional models are preserved after the introduction of fuzziness. Moreover if a property is not preserved, it appears for particular cases that do not occur in the framework of data mining, which is the goal of the fuzzy multidimensional database model.

Current and future work concern the study of binary operators (union, intersection, difference, product, join). It will provide foundations to manipulate complex queries in an algebraic way for query rewriting. The system will thus be able to perform query optimization. The enhancement of the implementation of the operators introduced in this paper is also planned. The existing system FU UB (standing for FUzzy cUBe) is implemented using Oracle Express Server, Oracle Express Objects, Java and C++ 2 .

Fig. 1 .

 1 Fig. 1. Example of a classical cubeOperations are defined in order to manipulate hypercubes. The unary operators are slice and dice (selection of information), projection (selection of dimensions) and roll-up (navigation through levels of hierarchies by means of an aggregation function).The slice operation consists in selecting slices from the cube by using a criterion on a dimension, for instance to select sales that have occurred in ATLANTA. The dice operation consists in selecting a subset of cells matching a criterion on the measure, for instance to select sales between 50, 000 and 80, 000 units. The

  (BOSTON, .8) , (CHICAGO, 1) , (DENVER, .2)} PRODUCT: X = set of products domain = {(CANOES, .7) , (TENTS, 1)}

  For each b ∈ L 2 , µ C (..., b, ...) is a function of • the degrees µ C (..., a, ...) with a ∈ L 1 , and • the values c(a, b). We have: µ C (..., b, ...) = max a∈L1 min(c(a, b), µ C (..., a, ...))

Fig. 3 .

 3 Fig. 3. A Counter Example

FlexibleFig. 4 .

 4 Fig. 4. Criteria Depending on the Granularity Level

* Note that aggregate refers here to the function defined to compute a summary value of cell values, as used in the classical relational model. This must not be confused with the aggregation of degrees in the Fuzzy Logic framework.