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

François Rioult
email: francois.rioult@unicaen.fr

Efficiently Depth-First Minimal Pattern Mining

Condensed representations have been studied extensively for 15 years. In particular, the maximal patterns of the equivalence classes have received much attention with very general proposals. In contrast, the minimal patterns remained in the shadows in particular because of their difficult extraction. In this paper, we present a generic framework for minimal patterns mining by introducing the concept of minimizable set system. This framework addresses various languages such as itemsets or strings, and at the same time, different metrics such as frequency. For instance, the free and the essential patterns are naturally handled by our approach, just as the minimal strings. Then, for any minimizable set system, we introduce a fast minimality check that is easy to incorporate in a depth-first search algorithm for mining the minimal patterns. We demonstrate that it is polynomial-delay and polynomial-space. Experiments on traditional benchmarks complete our study.

Introduction

Minimality is an essential concept of pattern mining. Given a function f and a language L, a minimal pattern X is one of the smallest pattern with respect to the set inclusion in L satisfying the property f (X). Interestingly, the whole set of minimal patterns forms a condensed representation of L adequate to f : it is possible to retrieve f (Y ) for any pattern of Y in L. Typically, the set of free itemsets [START_REF] Boulicaut | Approximation of frequency queries by means of free-sets[END_REF] (also called generators or key itemsets [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF]) is a condensed representation of all itemsets (here, f and L are respectively the frequency and the itemset language). Of course, it is often more efficient to extract minimal patterns rather than all patterns because they are less numerous. In addition, minimal patterns have a lot of useful applications including higher KDD tasks: producing the most relevant association rules [START_REF] Zaki | Generating non-redundant association rules[END_REF], building classifiers [START_REF] Liu | Integrating classification and association rule mining[END_REF] or generating minimal traversals [START_REF] Eiter | Hypergraph transversal computation and related problems in logic and ai[END_REF]. Minimality has been studied in the case of different functions (like frequency [START_REF] Calders | A survey on condensed representations for frequent sets[END_REF] and condensable functions [START_REF] Soulet | Adequate condensed representations of patterns[END_REF]) and different languages (e.g., itemsets [START_REF] Boulicaut | Approximation of frequency queries by means of free-sets[END_REF] and sequences [START_REF] Lo | Mining and ranking generators of sequential patterns[END_REF]). Although the minimality has obvious advantages [START_REF] Li | Minimum description length principle: Generators are preferable to closed patterns[END_REF], very few studies are related to the minimality while maximality (i.e., closed patterns) has been widely studied. In particular, to the best of our knowledge, there is no framework as general as those proposed for maximality [START_REF] Arimura | Polynomial-delay and polynomial-space algorithms for mining closed sequences, graphs, and pictures in accessible set systems[END_REF].

We think that a current major drawback of minimal patterns lies in their inefficient extraction. This low efficiency comes mainly from the fact that most existing algorithms use a levelwise approach [START_REF] Boulicaut | Approximation of frequency queries by means of free-sets[END_REF][START_REF] Soulet | Adequate condensed representations of patterns[END_REF][START_REF] Calders | Depth-first non-derivable itemset mining[END_REF] (i.e., breadth-first search/generate and test method). As they store all candidates in memory during the generation phase, the extraction may fail due to memory lack. To tackle this memory pitfall, it seems preferable to adopt a depth-first traversal which often consumes less memory and is still very fast. However, check whether the minimality is satisfied or not is very difficult in a depth-first traversal. In the case of frequency with itemsets, the best way for evaluating the minimality for a pattern (saying abc) is to compare its frequency with that of all its direct subsets (here, ab, ac and bc). But, when the pattern abc is achieved by a depth-first traversal, only frequencies of a and ab have previously been calculated. As the frequency of ac and bc are unknown, it is impossible to check whether the frequency of abc is strictly less than that of ac and bc. To cope with this problem, [START_REF] Calders | Depth-first non-derivable itemset mining[END_REF][START_REF] Liu | A new concise representation of frequent itemsets using generators and a positive border[END_REF] have adopted a different traversal with reordered items. For instance, when the itemset abc is reached by this new traversal, c, b, bc, a, ac and bc were previously scanned and their frequency are known for checking whether abc is minimal. Unfortunately, such a method requires to store all the patterns in memory (here, c, b, bc and so on) using a trie [START_REF] Calders | Depth-first non-derivable itemset mining[END_REF] or an hash table [START_REF] Liu | A new concise representation of frequent itemsets using generators and a positive border[END_REF]. For this reason, existing DFS proposals [START_REF] Calders | Depth-first non-derivable itemset mining[END_REF][START_REF] Liu | A new concise representation of frequent itemsets using generators and a positive border[END_REF] do not solve the low memory consumption issue as expected.

Contributions. The main goal of this paper is to present a generic and efficient framework for minimal pattern mining by providing a depth-first search algorithm. We introduce the notion of minimizable set system which is at the core of the definition of this framework. This latter covers a broad spectrum of minimal patterns including all the languages and measures investigated in [START_REF] Soulet | Adequate condensed representations of patterns[END_REF][START_REF] Arimura | Polynomial-delay and polynomial-space algorithms for mining closed sequences, graphs, and pictures in accessible set systems[END_REF]. Fast minimality checking in a depth-first traversal is achieved thanks to the notion of critical objects which depends on the minimizable set system. Based on this new technique, we propose the DeFMe algorithm. It mines the minimal patterns for any minimizable set system using a depth-first search algorithm. To the best of our knowledge, this is the first algorithm that enumerates minimal patterns in polynomial delay and in linear space with respect to the dataset.

The outline of this paper is as follows. In Section 2, we propose our generic framework for minimal pattern mining based on set systems. We introduce our fast minimality checking method in Section 3 and we indicate how to use it by sketching the DeFMe algorithm. Section 4 provides experimental results. In Section 5, we discuss some related work in light of our framework.

Minimizable Set System Framework

Basic Definitions

A set system (F, E) is a collection F of subsets of a ground set E (i.e. F is a subset of the power set of E). A member of F is called a feasible set. A strongly accessible set system (F, E) is a set system where for every feasible sets X, Y satisfying X ⊂ Y , there is an element e ∈ Y \ X such that Xe ∈ F 1 . Obviously, itemsets fits this framework with the set system (2 I , I) where I is the set of items. (2 I , I) is even strongly accessible. But the notion of set system allows considering more sophisticated languages. For instance, it is easy to build a family set F S denoting the collection of substrings of S = abracadabra by encoding each substring s k+1 s k+2 . . . s k+n by a set {(s k+1 , 1), (s k+2 , 2), . . . , (s k+n , n)}. The set sytem (F S , E S = F S ) is also strongly accessible. The set system formalism has already been used to describe pattern mining problems (see for instance [START_REF] Arimura | Polynomial-delay and polynomial-space algorithms for mining closed sequences, graphs, and pictures in accessible set systems[END_REF]).

Intuitively, a pattern always describes a set of objects. This set of objects is obtained from the pattern by means of a cover operator formalized as follows:

Definition 1 (Cover operator). Given a set of objects O, a cover operator

cov : 2 E → 2 O is a function satisfying cov(X ∪ Y ) = cov(X) ∩ cov(Y ) for every X ∈ 2 E and Y ∈ 2 E .
This definition indicates that the coverage of the union of two patterns is exactly the intersection of their two covers. For itemsets, a natural cover operator is the extensive function of an itemset X that returns the set of tuple identifiers supported by X: cov I (X) = {o ∈ O | X ⊆ o}. But, in general, the cover is not the final aim: the cardinality of cov I (X) corresponds to the frequency of X. In the context of strings, the index list of a string X also define a cover operator: cov S (X) = {i | ∀(s j , j) ∈ X, (s j , j + i) ∈ S}. Continuing our example with the string S = abracadabra, it is not difficult to compute the index lists cov S ({(a, 1)}) = {0, 3, 5, 7, 10} and cov S ({(b, 2)}) = {0, 7} and then, to verify cov S ({(a, 1), (b, 2)}) = cov S ({(a, 1)}) ∩ cov S ({(b, 2)}) = {0, 7}.

For some languages, the same pattern is described by several distinct sets and then it is necessary to have a canonical form. For example, consider the set {(a, 1), (b, 2), (r, 3)} corresponding to the string abr. Its suffix {(b, 2), (r, 3)} encodes the same string br as {(b, 1), (r, 2)}. The latter is the canonical form of the string br. To retrieve the canonical form of a pattern, we introduce the notion of canonical operator: Definition 2 (Canonical operator). Given two set systems (F, E) and (G, E), a canonical operator φ :

F ∪G → F is a function satisfying (i) X ⊂ Y ⇒ φ(X) ⊂ φ(Y ) and (ii) X ∈ F ⇒ φ(X) = X for all sets X, Y ∈ G.
In this definition, the property (i) ensures us that the canonical forms of two comparable sets with respect to the inclusion remain comparable. The property (ii) means that the set system (F, E) includes all canonical forms. Continuing our example about strings, it is not difficult to see that φ S : {(s k , k), (s k+1 , k + 1), . . . , (s k+n , n)} → {(s k , 1), (s k+1 , 2), . . . , (s k+n , n-k +1)} satisfies the two desired properties (i) and (ii). For instance, φ S ({(b, 2), (r, 3)}) returns the canonical form of the string {(b, 2), (r, 3)} which is {(b, 1), (r, 2)}.

Minimizable Set System

Rather than considering an entire set system, it is wise to select a smaller part that provides the same information (w.r.t. a cover operator). For this, it is necessary that this set system plus the cover operator form a minimizable set system: Definition 3 (Minimizable set system). A minimizable set system is a tuple (F, E), G, cov, φ where:

-(F, E) is a finite, strongly accessible set system. A feasible set in F is called a pattern. -(G, E) is a finite, strongly accessible set system satisfying for every feasible set X, Y ∈ F such that X ⊆ Y and element e ∈ E, X\{e} ∈ G ⇒ Y \{e} ∈ G. A feasible set in G is called a generalization. -cov : 2 E → 2 O is a cover operator. -φ : F ∪ G → F is a canonical operator such that for every feasible set X ∈ G, it implies cov(φ(X)) = cov(X).
Let us now illustrate the role of G compared to F in the case of strings. In fact, G S gathers all the suffixes of any pattern of F S . Typically, {(b, 2), (r, 3)} ∈ G S is a generalization of {(a, 1), (b, 2), (r, 3)} ∈ F S . As said above, {(b, 2), (r, 3)} has an equivalent form in F S : φ S ({(b, 2), (r, 3)}) = {(b, 1), (r, 2)}. By convention, we extend the definition of cov S to G S by considering that cov S (φ S (X)) = cov S (X). In addition, it is not difficult to see that G S satisfies the desired property with respect to F S : for every feasible set

X, Y ∈ F S such that X ⊆ Y and element e ∈ E S , X \ {e} ∈ G S ⇒ Y \ {e} ∈ G S . Indeed, if X \ {e} is a suffix of X,
it means that e is the first letter. If we consider a specialization of X and we again remove the first letter, we also obtain a suffix belonging to G S . Therefore, (F S , E S ), G S , cov S , φ S is a minimizable set system.

Obviously, a minimizable set system can be reduced to a system of smaller cardinality of which the patterns are called the minimal patterns: Definition 4 (Minimal pattern). A pattern X is minimal for (F, E), G, cov, φ iff X ∈ F and for every generalization Y ∈ G such that Y ⊂ X, cov(Y ) = cov(X). M(S) denotes the set of all minimal patterns. Definition 4 means that a pattern is minimal whenever its cover differs from that of any generalization. For example, for the cover operator cov S , the minimal patterns have a strictly smaller cover than their generalizations. The string ab is not minimal due to its suffix b because cov S ({(b, 2))}) = cov S ({(a, 1), (b, 2)}) = {0, 7}. For our running example, the whole collection of minimal strings is M(S S ) = {a, b, r, c, d, ca, ra, da}.

Given a minimizable set system S = (F, E), G, cov, φ , the minimal pattern mining problem consists in enumerating all the minimal patterns for S.

Enumerating the Minimal Patterns

This section aims at effectively mining all the minimal patterns in a depth-first search manner (Section 3.3). To do this, we rely on two key ideas: the pruning of the search space (Section 3.1) and the fast minimality checking (Section 3.2).

Before, it is important to recall that the minimal patterns are sufficient to induce the cover of any pattern. From now, we consider a minimizable set system S = (F, E), G, cov, φ . The minimal patterns M(S) is a lossless representation of all patterns of F in the sense we can find the cover of any pattern.

Theorem 1 (Condensed representation). The set of minimal patterns is a concise representation of F adequate to cov: for any pattern X ∈ F, there exists Y ⊆ X such that φ(Y ) ∈ M(S) and cov(φ(Y )) = cov(X).

Theorem 1 means that M(S) is really a condensed representation of S because the minimal pattern mining enables us to infer the cover of any pattern in S. For instance, the cover of the non-minimal pattern {(a, 1), (b, 2)} equals to that of the minimal pattern φ({(b, 2)}) = {(b, 1)}: cov S ({(a, 1), (b, 2)}) = cov S ({(b, 1)}) = {0, 7}. It is preferable to extract M(S) instead of S because its size is lower (and, in general, much lower) than the total number of patterns.

Search Space Pruning

The first problem we face is fairly classical. Given a minimizable set system S = (F, E), G, cov, φ , the number of patterns |F| is huge in general (in the worst case, it reaches 2 |E| patterns). So, it is absolutely necessary not to completely scan the search space for focusing on the minimal patterns. Effective techniques can be used to prune the search space due to the downward closure of M(S):

Theorem 2 (Independence system). If a pattern X is minimal for S, then any pattern Y ∈ F satisfying Y ⊆ X is also minimal for S.

The proof of this theorem strongly relies on a key lemma saying that a nonminimal pattern has a direct generalization having the same cover (proofs are omitted due to lack of space): Lemma 1. If X is not mininal, there exists e ∈ X such that X \ {e} ∈ G and cov(X) = cov(X \ {e}).

For instance, as the string da is minimal, the substrings d and a are also minimal. More interestingly, as ab is not minimal, the string abr is not minimal. It means that the string ab is a cut-off point in the search space. In practice, antimonotone pruning is recognized as a very powerful tool whatever the traversal of the search space (level by level or in depth).

Fast Minimality Checking

The main difficulty in extracting the minimal patterns is to test whether a pattern is minimal or not. As we mentioned earlier, this is particularly difficult in a depth-first traversal because all subsets have not yet been enumerated. Indeed, depth-first approaches only have access to the first parent branch contrary to levelwise approaches. To overcome this difficulty, we introduce the concept of critical objects inspired from critical edges in case of minimal traversals [START_REF] Murakami | Efficient algorithms for dualizing large-scale hypergraphs[END_REF]. Intuitively, the critical objects of an element e for a pattern X are objects that are not covered by X due to the element e. We now give a formal definition of the critical objects derived from any cover operator: Definition 5 (Critical objects). For a pattern X, the critical objects of an element e ∈ X, denoted by cov(X, e) is the set of objects that belongs to the cover of X without e and not to the cover of e: cov(X, e) = cov(X \ e) \ cov(e).

Let us illustrate the critical objects with our running example. For {(a, 1), (b, 2)}, the critical objects cov(ab, a) of the element (a, 1) correspond to ∅ (= {0, 7} \ {0, 3, 5, 7, 10}). It means that the addition of a to b has no impact on the cover of ab. At the opposite, for the same pattern, the critical objects of (b, 2) are {3, 5, 10} (= {0, 3, 5, 7, 10} \ {0, 7}). It is due to the element b that ab does not cover the objects {3, 5, 10}.

The critical objects are central in our proposition for the following reasons: 1) the critical objects easily characterize the minimal patterns; and 2) the critical objects can efficiently be computed in a depth-first search algorithm. Minimal pattern characterization The converse of Lemma 1 says that a pattern is minimal if its cover differs from that of its generalization. We can reformulate this definition thanks to the notion of critical objects as follows:

Property 1 (Minimality). X ∈ F is minimal if ∀e ∈ X such that X \ e ∈ G, cov(X, e) = ∅.
Typically, as b is a generalization of the string ab and at the same time, cov(ab, a) is empty, ab is not minimal. Property 1 means that checking whether a candidate X is minimal only requires to know the critical objects of all the elements in X. Unlike the usual definition, no information is required on the subsets. Therefore, the critical objects allow us to design a depth-first algorithm if (and only if) computing the critical objects does not also require information on the subsets. Efficiently critical object computation In a depth-first traversal, we want to update the critical objects of an element e for the pattern X when a new element e ′ is added to X. In such case, we now show that the critical objects can efficiently be computed by intersecting the old set of critical objects cov(X, e) with the cover of the new element e ′ : Property 2. The following equality holds for any pattern X ∈ F and any two elements e, e ′ ∈ E: cov(Xe ′ , e) = cov(X, e) ∩ cov(e ′ ).

For instance, Definition 5 gives cov S (a, a) = {1, 2, 4, 6, 8, 9}. As cov S (b) = {0, 7}, we obtain that cov S (ab, a) = cov S (a, a) ∩ cov S (b) = {1, 2, 4, 6, 8, 9} ∩ {0, 7} = ∅. Interestingly, Property 2 allows us to compute the critical objects of any element included in a pattern X having information on a single branch. This is an ideal situation for a depth-first search algorithm.

Algorithm DeFMe

The algorithm DeFMe takes as inputs the current pattern and the current tail (the list of the remaining items to be checked) and it returns all the minimal patterns containing X (based on tail). More precisely, Line 1 checks whether X is minimal or not. If X is minimal, it is output (Line 2). Lines 3-14 explores the subtree containing X based on the tail. For each element e where Xe is a pattern of F (Line 4) (Property 1), the branch is built with all the necessary information. Line 7 updates the cover and Lines 8-11 updates the critical objects using Property 2. Finally, the function DeFMe is recursively called at Line 12 with the updated tail (Line 5).

Algorithm 1 DeFMe(X, tail)

Input: X is a pattern, tail is the set of the remaining items to be used in order to generate the candidates. Initial values: X = ∅, tail = E. Output: polynomially incrementally outputs the minimal patterns.

1:

if ∀e ∈ X, cov(X, e) = ∅ then 2: print X 3:
for all e ∈ tail do 4:

if Xe ∈ F then 5:

tail := tail \ {e} 6:

Y := Xe 7: cov(Y ) := cov(X) ∩ cov(e) 8: cov(Y, e) := cov(X) \ cov(e) 9:
for all e ′ ∈ X do 10:

cov(Y, e ′ ) := cov(X, e ′ ) ∩ cov(e) 11:

end for 12:

DeFMe(Y, tail) 13:

end if 14:

end for 15: end if Theorems 3 and 4 demonstrate that the algorithm DeFMe has an efficient behavior both in space and time. This efficiency mainly stems from the inexpensive handling of covers/critical objects as explained by the following property: Property 3. The following inequality holds for any pattern X ∈ F:

|cov(X)| + e∈X | cov(X, e)| ≤ |cov(∅)|
Property 3 means that for a pattern, the storage of its cover plus that of all the critical objects is upper bounded by the number of objects (i.e., |cov(∅)|). Thus, it is straightforward to deduce the memory space required by the algorithm:

Theorem 3 (Polynomial-space complexity). M(S) is enumerable in O(|cov(∅)| × m)
space where m is the maximal size of a feasible set in F.

In practice, the used memory space is very limited because m is small. In addition, the amount of time between each output pattern is polynomial:

Theorem 4 (Polynomial-delay complexity). M(S) is enumerable in O(|E| 2 × |cov(∅)|) time per minimal pattern.
It is not difficult to see that between two output patterns, DeFMe requires a polynomial number of operations assuming that the membership oracle is computable in polytime (Line 4). Indeed, the computation of the cover and that of the critical objects (Lines 7-11) is linear with the number of objects due to Property 3; the loop in Line 3 does not exceed |E| iterations and finally, the number of consecutive backtracks is at most |E|.

Experimental Study

The aim of our experiments is to quantify the benefit brought by DeFMe both on effectiveness and conciseness. We show its effectiveness with the problem of free itemset mining for which several prototypes already exist in the literature. Then we instantiate DeFMe to extract the collection of minimal strings and compare its size with that of closed strings. All tests were performed on a 2.2 GHz Opteron processor with Linux operating system and 200 GB of RAM memory.

Free Itemset Mining

We designed a prototype of DeFMe for itemset mining as a proof of concept and we compared it with two other prototypes: ACminer based on a levelwise algorithm [START_REF] Boulicaut | Approximation of frequency queries by means of free-sets[END_REF] and NDI2 based on a depth-first traversal with reordered items [START_REF] Calders | Depth-first non-derivable itemset mining[END_REF]. For this purpose, we conducted experiments on benchmarks coming from the FIMI repository and the 2004 PKDD Discovery Challenge3 . The first three columns of Table 1 give the characteristics of these datasets. The fourth column gives the used minimal support threshold. The next three columns report the running times and finally, the last three columns indicate the memory consumption. The best performances are highlighted in bold in Table 1 for both time and space. ACminer is by far the slowest prototype. Its levelwise approach is particularly penalized by the large amount of used memory. Except on the genomic datasets 74x822 and 90x27679, the running times of NDI clearly outperform those of DeFMe. As a piece of information, Figure 1 details, for various minsup thresholds, the speed of DeFMe. It plots the number of minimal patterns it extracted for each second of computing time.

Concerning memory consumption, DeFMe is (as expected) the most efficient algorithm. In certain cases, the increase of the storage memory would not be sufficient to treat the most difficult datasets. Here, ACminer and NDI are not suitable to process genomic datasets even with 200GB of RAM memory and relatively high thresholds. More precisely, Figure 1 plots the ratio between NDI's and DeFMe's memory use for various minsup thresholds. It is easy to notice that this ratio quickly leads NDI to go out DeFMe works with bounded memory and then is not minsup limited.

Minimal String Mining

In this section, we adopt the formalism of strings stemming from our running example. We compared our algorithm for minimal string mining with the maxMotif prototype provided by Takeaki Uno that mines closed strings [START_REF] Arimura | Polynomial-delay and polynomial-space algorithms for mining closed sequences, graphs, and pictures in accessible set systems[END_REF]. Our goal is to compare the size of condensed representations based on minimal strings with those based on all strings and all closed strings. We do not report the execution times because maxMotif developed in Java is much slower than DeFMe (developed in C++). Experiments are conducted on two datasets: chromosom 4 and msnbc coming from the UCI ML repository (www.ics.uci. edu/ ~mlearn). the number of patterns increases with the decrease of the minimal frequency threshold. Interestingly, the two condensed representations become particularly useful when the frequency threshold is very small. Clearly the number of minimal strings is greater than the number of closed strings, but the gap is not as important as it is the case with free and closed itemsets.

Related Work

The collection of minimal patterns is a kind of condensed representations. Let us recall that a condensed representation of the frequent patterns is a set of patterns that can regenerate all the patterns that are frequent with their frequency. The success of the condensed representations stems from their undeniable benefit to reduce the number of mined patterns by eliminating redundancies. A large number of condensed representations have been proposed in literature [START_REF] Calders | A survey on condensed representations for frequent sets[END_REF][START_REF] Hamrouni | Key roles of closed sets and minimal generators in concise representations of frequent patterns[END_REF]: closed itemsets [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF], free itemsets [START_REF] Boulicaut | Approximation of frequency queries by means of free-sets[END_REF], essential itemsets [START_REF] Casali | Essential patterns: A perfect cover of frequent patterns[END_REF], Non-Derivable Itemsets [START_REF] Calders | Depth-first non-derivable itemset mining[END_REF], itemsets with negation [START_REF] Kryszkiewicz | Generalized disjunction-free representation of frequent patterns with negation[END_REF] and so on. Two ideas are at the core of the condensed representations: the closure operator [START_REF] Hamrouni | Key roles of closed sets and minimal generators in concise representations of frequent patterns[END_REF] that builds equivalence classes and the principle of inclusion-exclusion. As the inclusion-exclusion principle only works for the frequency, this paper exclusively focuses on minimal patterns considering equivalence classes. In particular, as indicated above the system S I = (2 I , I), 2 I , cov I , Id is minimizable and M(S I ) corresponds exactly to the free itemsets (or generators). The frequency of each itemset is computed using the cardinality of the cover. Replace the cover operator cov I by cov I : X → {o ∈ O | X ∩ o = ∅} leads to a new minimizable set system (2 I , I), 2 I , cov I , Id of which minimal patterns are essential itemsets [START_REF] Casali | Essential patterns: A perfect cover of frequent patterns[END_REF]. The disjunctive frequency of an itemset X is |O| -|cov I (X)|.

Minimal pattern mining has a lot of applications and their use is not limited to obtain frequent patterns more efficiently. Their properties are useful for higher KDD tasks. For instance, minimal patterns are used in conjunction of closed patterns to produce non-redundant [START_REF] Zaki | Generating non-redundant association rules[END_REF] or informative rules [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF]. The sequential rules also benefit from minimality [START_REF] Lo | Non-redundant sequential rules -theory and algorithm[END_REF]. It is also possible to exploit the minimal patterns for mining the classification rules that are the key elements of associative classifiers [START_REF] Liu | Integrating classification and association rule mining[END_REF]. Our framework is well-adapted for mining all such minimal classification rules that satisfy interestingness criteria involving frequencies.Assuming that the set of objects O is divided into two

disjoint classes O = O 1 ∪ O 2 , the confidence of the classification rule X → class 1 is |O 1 ∩ cov I (X)|/|cov I (X)|.
More generally, it is easy to show that any frequency-based measure (e.g., lift, bond) can be derived from the positive and negative covers. In addition, the essential patterns are useful for deriving minimal traversals that exactly corresponds to the maximal patterns of M( (2 I , I), 2 I , cov I , Id ). Let us recall that the minimal transversal generation is a very important problem which has many applications in Logic (e.g., satisfiability checking), Artificial Intelligence (e.g., model-based diagnosis) and Machine Learning (e.g., exact learning) [START_REF] Eiter | Hypergraph transversal computation and related problems in logic and ai[END_REF][START_REF] Murakami | Efficient algorithms for dualizing large-scale hypergraphs[END_REF].

The condensed representations of minimal patterns are not limited to frequency-based measures or itemsets. Indeed, it is also possible to mine the minimal patterns adequate to classical aggregate functions like min, max or sum [START_REF] Soulet | Adequate condensed representations of patterns[END_REF]. Minizable set systems are also well-adapted for such measures. For instance, let us consider the function cov min (X) = {val(i)|∃i ∈ I, val(i) ≤ min(X.val)} that returns all the possible values of val less than min(X.val). This function is a cover operator and (2 I , I), 2 I , cov min , Id is even a minimizable set system. The minimal patterns adequate to min correspond to the minimal patterns of the previous set system. Furthermore, the value min(X.val) could be obtained as follows max(cov min (X)). A similar approach enables us to deal with max and sum. In parallel, several studies have extended the notion of generators to address other languages such as sequences [START_REF] Lo | Mining and ranking generators of sequential patterns[END_REF][START_REF] Gao | Efficient mining of frequent sequence generators[END_REF], negative itemsets [START_REF] Gasmi | Extraction of association rules based on literalsets[END_REF], graphs [START_REF] Zeng | FOGGER: an algorithm for graph generator discovery[END_REF]. Unfortunately no work proposes a generic framework to extend the condensed representations based on minimality to a broad spectrum of languages as it was done with closed patterns [START_REF] Arimura | Polynomial-delay and polynomial-space algorithms for mining closed sequences, graphs, and pictures in accessible set systems[END_REF]. For instance, [START_REF] Boulicaut | Approximation of frequency queries by means of free-sets[END_REF][START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF][START_REF] Calders | Depth-first non-derivable itemset mining[END_REF][START_REF] Liu | A new concise representation of frequent itemsets using generators and a positive border[END_REF] only address itemsets or [START_REF] Lo | Mining and ranking generators of sequential patterns[END_REF][START_REF] Gao | Efficient mining of frequent sequence generators[END_REF] focus exclusively on sequences. In this paper, we have made the connection between the set systems and only two languages: itemsets and strings due to space limitation. Numerous other languages can be represented using this set system framework. In particular, all the languages depicted by [START_REF] Arimura | Polynomial-delay and polynomial-space algorithms for mining closed sequences, graphs, and pictures in accessible set systems[END_REF] are suitable.

Conclusion

By proposing the new notion of minimizable set system, this paper extended the paradigm of minimal patterns to a broad spectrum of functions and languages. This framework encompasses the current methods since the existing condensed representations (e.g., free or essential itemsets) fit to specific cases of our framework. Besides, DeFMe efficiently mines such minimal patterns even in difficult datasets, which are intractable by state-of-the-art algorithms. Experiments also showed on strings that the sizes of the minimal patterns are smaller than the total number of patterns.

Of course, we think that there is still room to improve our implementation even if it is difficult to find a compromise between generic method and speed.

We especially want to test the ability of the minimal patterns for generating minimal classification rules with new types of data, such as strings. Similarly, it would be interesting to build associative classifiers from minimal patterns.

Fig. 1 .

 1 Fig. 1. Ratio of mining speed (left) and memory use (right) of NDI by DeFMe.

Figure 2 4Fig. 2 .Fig. 3 .

 223 Fig. 2. Number of patterns in chromosom

Table 1 .

 1 Characteristics of benchmarks and results about free itemset mining

	time (s)	memory (kB)

We use the notation Xe instead of X ∪ {e}.

As this prototype mines non-derivable itemsets, it enable us to compute free patterns when the depth parameter is set to 1.

fimi.ua.ac.be/data/ and lisp.vse.cz/challenge/ecmlpkdd2004/

Acknowledgments. This article has been partially funded by the Hybride project (ANR-11-BS02-0002).


Isabelle Bloch

Alain Bretto

come


Wilson A Higashino
email: whigashi@uwo.ca

Cédric Eichler
email: eichler@laas.fr

Miriam A M Capretz
email: mcapretz@uwo.ca

Thierry Monteil
email: monteil@laas.fr

Maria Beatriz
email: beatriz@ic.unicamp.br

F De Toledo

Patricia Stolf
email: stolf@irit.fr

From Inception to Execution: Query Management for Complex Event Processing as a Service

Keywords: Complex Event Processing, Reconfigurable Systems, Automatic Query Optimization

Complex Event Processing (CEP) is a set of tools and techniques that can be used to obtain insights from highvolume, high-velocity continuous streams of events. CEP-based systems have been adopted in many situations that require prompt establishment of system diagnostics and execution of reaction plans, such as in monitoring of complex systems. This article describes the Query Analyzer and Manager (QAM) module, a first effort toward the development of a CEP as a Service (CEPaaS) system. This module is responsible for analyzing user-defined CEP queries and for managing their execution in distributed cloud-based environments. Using a language-agnostic internal query representation, QAM has a modular design that enables its adoption by virtually any CEP system.

I. INTRODUCTION

Current trends in sensor and mobile technologies have been generating massive amounts of data that require innovative approaches to be processed and understood. This has motivated the creation of new technologies, of which Complex Event Processing (CEP) is one prominent example, to obtain insights from high-volume, high-velocity continuous streams of data.

Complex Event Processing is defined as a "set of tools and techniques for analysing and controlling the complex series of interrelated events that drive modern distributed information systems" [START_REF] Luckham | The Power of Events: An Introduction to Complex Event Processing in Distributed Enterprise Systems[END_REF]. CEP-based systems interpret input data as a stream of events and accept user definitions of queries (or rules) to derive semantically enriched "complex" events from a series of simpler events. These complex events can then be used to trigger actions, thereby enabling prompt establishment of system diagnostics and execution of reaction plans. Due to these characteristics, CEP has been adopted in many situations that require fast autonomous response, such as network monitoring, and smart building management. This article is a first effort toward the development of a cloud-based CEP system designed to be consumed as a service. Such a CEP as a Service (CEPaaS) system has been conceptualized to leverage public cloud environments to implement elasticity and to provide low-latency processing of data coming from diverse physical locations. Users simply define CEP queries using a graphical environment, with the system transparently managing their execution. This article introduces QAM (Query Analyzer and Manager), a module responsible for analyzing user-defined CEP queries and managing their execution. QAM uses a formalism based on attributed graphs and graph-rewriting rules to model queries and to implement four important tasks required by CEP systems: single-query optimization, multi-query optimization, operator placement, and autonomic runtime query management. Because of its modular design, QAM can be adopted by any CEP system as long as its query definitions can be transformed into the language-agnostic query representation used by QAM. This paper is structured as follows: Section II offers an overview of related work. Section III discusses the notion of offering CEP in the service model. Section IV is dedicated to QAM and the four operations for which it is responsible. Finally, Section V presents conclusions and future research directions.

II. RELATED WORK

The basis of the CEP field was established by classical systems, such as Aurora [START_REF] Abadi | Aurora: a new model and architecture for data stream management[END_REF] and STREAM [START_REF] Arasu | STREAM: The Stanford Data Stream Management System[END_REF], but their centralized architecture makes them inappropriate for the CEP as a Service scenario. Cloud environments have been targeted in more recent works such as TimeStream [START_REF] Qian | TimeStream: Reliable Stream Computation in the Cloud[END_REF] and Stream-Cloud [START_REF] Gulisano | StreamCloud: A Large Scale Data Streaming System[END_REF]. However, these are mostly based on clustered architectures, whereas this research envisions a CEP system distributed over wide-area networks. For further information, the survey by Cugola and Margara [START_REF] Cugola | Processing flows of information: from data stream to complex event processing[END_REF] provides a comprehensive review of modern and historical CEP systems. CEP queries have usually been defined by means of specific proprietary languages such as CQL [START_REF] Arasu | The CQL continuous query language: semantic foundations and query execution[END_REF]. Despite standardization efforts [START_REF] Jain | Towards a Streaming SQL Standard[END_REF], a huge variety of query description languages are still in use today. The adoption of a language-agnostic representation by QAM is motivated by this variety. The surveys by Eckert et al. [START_REF] Eckert | A CEP Babelfish: Languages for Complex Event Processing and Querying Surveyed[END_REF] and by Cugola and Margara [START_REF] Cugola | Processing flows of information: from data stream to complex event processing[END_REF] provide a comprehensive review of CEP languages.

Most CEP systems deal with some of the aspects that should be handled by the QAM module, including query optimization, operator placement, multi-query optimization, and dynamic runtime management. For instance, Kalyvianaki et al. [START_REF] Kalyvianaki | SQPR: Stream query planning with reuse[END_REF] described a query planner which was capable of executing multi-query optimization, and Abadi et al. [START_REF] Abadi | The design of the Borealis stream processing engine[END_REF] showed dynamic reconfiguration actions in the context of the Borealis system. Nevertheless, none of these studies has used a unified and integrated approach to handle all four tasks as proposed in QAM.

III. CEP AS A SERVICE

A CEP as a Service system aims to bring its users the functionalities of CEP associated with the many advantages of the service model, such as: (1) No up-front investment in hardware and software infrastructure; (2) Low maintenance cost, as the service model reduces the need for infrastructure monitoring, maintenance, and backup execution; (3) constant upgrades, mostly without interruption and at no charge.

Nevertheless, offering such a service involves many challenges, which is reflected in the limited number of similar services today. For instance, low latency is essential to many CEP use cases, but is difficult to achieve in a service environment because there is no control over the locations of the event sources and consumers. CEP use cases may also require a high-available service and may impose an unpredictable and variable load over it, requiring the implementation of innovative elasticity capabilities in the CEPaaS engine.

It is argued here that a distributed deployment over resources available in public cloud environments can be highly beneficial for such a CEP as a Service system. A distributed design improves system scalability because it enables allocation of user queries over many available servers. It also enhances the overall system availability because there is no single point of failure. In addition, use of public cloud resources also makes the system easily accessible by any client with Internet access. Finally, it also enables exploration of the inherent elasticity of cloud environments, facilitating fast allocation and de-allocation of computational resources according to system load.

IV. QUERY ANALYZER AND MANAGER

Implementation of a CEP as a Service system is a complex task involving the definition of many components and policies. This section introduces the Query Analyzer and Manager (QAM), which is the module responsible for analyzing user queries and for managing their execution.

Figure 1 informally illustrates the typical lifecycle of a QAM-managed query. The user initially defines a query using a CEP language, which is transformed into an attributed Directed Acyclic Graph (DAG) and sent to the QAM module. In the DAG format, the query goes through a pipeline of three tasks that results in mapping the query execution into a set of distributed components. Then QAM manages the runtime execution of the query and the evolution of the system deployment, responding to context changes such as hardware and software failures. The following subsections detail the QAM tasks.

A. Single-query optimization

Single-query optimization is the action of modifying a query to improve its efficiency (w.r.t. some optimization criterion such as CPU usage, network consumption, or processing latency) while keeping its functional properties unchanged. In Fig. 1, this process is illustrated by removal of the (redundant) operators D and E in the "User 1" query. These transformations are executed at design time right after a new query is created and registered by the user. In consequence, this step assumes no a priori knowledge of available resources or of network and server states.

B. Multi-query optimization

Multi-query optimization consists in finding overlaps (common partial results) between queries and merging them into a single execution graph. This step usually aims to optimize the same criteria as the single-query optimization step. It can be executed as a separate step when a new query is created or as part of the operator placement step. In Fig. 1, the execution graphs are merged into a single one because both queries share the same processing represented by the operators A and C.

C. Operator placement

Operator placement is the task of mapping each query execution into the set of available computational resources. In the context of a cloud-based CEP system, this translates into deciding which datacentre will execute each query, the number and types of server required in each datacentre, and how the query operators should be split among multiple processors. Note that this step implies choices at two different levels of granularity. First, a datacentre must be chosen, typically using aggregated metrics. Then placement is conducted within the selected datacentre. This step is executed during initial system deployment, whenever a new query is registered, and in general, whenever a reconfiguration requires a placement decision (e.g., when an operator is duplicated to parallelize its execution, the placement routine is called to decide where the created operator instance should be deployed). In Fig. 1, execution of operators A, B, C, and I is mapped into one server, whereas the other operators are mapped to another server.

The QAM also uses attributed graphs to represent the available cloud servers and the network topology that interconnects them. Therefore, operator placement can be performed using classical approaches that map graphs into a substrate graph (e.g., [START_REF] Houidi | Exact adaptive virtual network embedding in cloud environments[END_REF]).

D. Autonomic management

Autonomic management refers to the self-managed evolution of the system in runtime. Here, queries are reconfigured in response to context changes such as violations of monitored parameters, hardware and software failures, and evolving client requests. These transformations are executed in runtime and may require performing a complex set of actions. In Fig. 1, a new server is provisioned during this step, to which the execution of the operator I is migrated.

E. Realization

Being both formal and visual, graphs have been successfully used to model the structural constraints and properties of a vast range of systems in multiple fields, including software architectures. Remarkably, graphs rewriting techniques can be used to design correct-by-construction frameworks for the specification of system transformations [START_REF] Hirsch | Consistent transformations for software architecture styles of distributed systems[END_REF]. Such techniques have been used in particular for autonomic management of various systems such as machine-to-machine scenarios [START_REF] Eichler | Graph-based formalism for machine-to-machine self-managed communications[END_REF].

Note that both single and multi-query optimization as well as autonomic management implies system transformations. Each of these can be enforced using similar techniques, specifically by defining transformations stemming from an existing graph-based framework. Use of such a representation is supported by the fact that several CEP languages, such as CQL [START_REF] Arasu | The CQL continuous query language: semantic foundations and query execution[END_REF], can easily be translated into directed attributed graphs.

V. C ONCLUSIONS

This work has presented the Query Analyzer and Manager, a generic CEP module that can be used to analyze user-defined queries and manage their execution. QAM represents queries and the deployment environment as directed attributed graphs and uses graph transformations to express reconfigurations and other dynamic aspects of the system. In particular, QAM is responsible for completion of four important CEP-related tasks: single-query optimization, multi-query optimization, operator placement, and autonomic runtime query management.

In the future, the authors plan to develop, implement, and evaluate each step of the QAM using graphs and graph transformations. Note that the mechanisms implied in the various transformational steps are very similar to each other. In particular, the authors believe that transformations and policies can be built in an iterative fashion, in the sense that singlequery optimization transformations (e.g., operator duplication) can still be relevant in multi-query optimization that and in turn can be used in the dynamic (autonomic) management task.

Fig. 1 .

 1 Fig. 1. Query Analyzer and Manager steps.


Emilie Rebeyrol

ENAC Christophe Macabiau

Laurent Lestarquit

Lionel Ries

CNES Jean-Luc Issler

ENST Marie-Laure Boucheret

Michel Bousquet

Supaero Biography

BOC power spectrum densities

à la diffusion de documents scientifiques 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.

terms of tracking, interference and multipath mitigation. As this BOC modulation, along with a modified version called alternate BOC (ALTBOC), is a serious candidate for GALILEO and GPS, it is important to understand all characteristics of this signal, in order to conduct several studies like payload design, receiver implementation, performance and robustness evaluation. One of the aspects of this signal is the power spectrum density that impacts all characteristics presented above. The aim of this paper is, in a first part, to review the currently admitted BOC power spectrum density theoretical expressions, and to discuss a deviation of the assumptions necessary for the derivation of these classical theoretical expressions w.r.t to the reality of these signals.

Then, a second objective is to present theoretical expressions of ALTBOC and constant envelope ALTBOC power spectrum densities.

First the paper recalls the formal expressions of the different possible offset carrier modulations: BOC, ALTBOC and constant envelop ALTBOC signals in the time domain. Then, the assumptions for the development of the classical power spectrum density calculation are clearly laid down. Next, it is shown that in the case of odd ratio (2*f s /f c ) BOC signals, these assumptions, and particularly the fact that the BOC square sub-carrier can be incorporated in the chip waveform, are not met. Then, we show that, for these calculation assumptions to be met in that case of odd ratio BOC, it is equivalent to modify the code sequence. Finally, with this view, the obtained power spectrum density is the same as the one obtained with the classical theory, due to the negligible effect of the code sequence correlation values. Finally, we present the theoretical expressions of the ALTBOC and constant envelope ALTBOC power spectrum densities.

I. INTRODUCTION

The modernization of the Global Positioning System (GPS) and the development of the Galileo System have led to design new signals to provide different services to a variety of users. The most important innovation used for these signals is the Binary Offset Carrier (BOC) modulation because it significantly improves the performance obtained until then in the radionavigation system. This modulation is candidate for the new GPS military signal, the M-code. But it is also candidate for many signals in the future Galileo system:

-in L1

II. OFFSET CARRIER SIGNALS

BOC Signal Definition

In the literature two notations are used to define the BOC signal.

The first model defines the BOC signal as the product of a materialized code with a sub-carrier which is equal to the sign of a sine or a cosine waveform. It is presented in [START_REF] Betz | Binary Offset Carrier Modulations for Radionavigation[END_REF], [START_REF] Ries | Tracking and Multipath Performance Assessments of BOC Signals Using a Bit-Level Signal Processing Simulator[END_REF]] and [START_REF] Godet | Technical Annex to Galileo SRD Signal Plans[END_REF]. In this case if c(t) is the code sequence waveform and f s the sub-carrier frequency, the expression of the sine-phased BOC signal is:

( ) ( ) t f sign t c t x S π 2 sin ) ( ) ( ⋅ = with (1) ) ( ) ( c k k kT t h c t c - = ∑ h(t)
is the code materialization, it is a NRZ materialization equal to 1 over [0, T c ] and 0 everywhere else.

The second model defines the BOC signal by the following equation:

) ( ) ( c k k kT t p c t x - = ∑ (2)
with p(t) broken up into n rectangular pulses of duration T c /n with amplitudes of +/-1. In this case the sine-phased or cosine-phased sub-carrier is considered as a part of the chip waveform. It is presented in [START_REF] Pratt | BOC Modulations Waveform[END_REF] and [START_REF] Betz | Binary Offset Carrier Modulations for Radionavigation[END_REF].

In the two cases BOC signals are commonly referred to BOC(p,q). The first parameter p defines the sub-carrier rate and the second parameter q defines the spreading code rate:

023 . 1 ⋅ = p f s MHz and 023 . 1 ⋅ = q f c MHz The ratio q p f f n c s 2 2 = =
is the number of half periods of the sub-carrier during one code chip. This ratio can be odd or even.

The two models presented above are identical if the ratio n is even. In fact if n is even it is true to consider that the sub-carrier is included in the chip waveform. However it is false to consider such a thing if n is odd. The example presented below shows clearly that these two conventions lead to different time series if n is odd.

Example:

We consider:

-a code sequence equal to : {1,-1,-1,1} -a square sub-carrier which is sine-phased and with 2f S /f C = 3.

It is represented by this scheme:

If the BOC signal is written as (1), the scheme represented this signal is:

On the other hand, if we consider that the sub-carrier is included in the chip waveform and that the BOC signal can be written as (2), we have:

Both signals obtained are different. Indeed, there is a polarity inversion every 2 bits.

If n is odd a modification must be made on the time series if we want to consider that the sub-carrier is included in the code materialization. We have, in [START_REF] Betz | Binary Offset Carrier Modulations for Radionavigation[END_REF]:

( ) (
) 1) k term is introduced. This introduction is in fact equivalent to a modification of the PRN code sequence, becoming now (-1) k c k and not c k . Consequently in the case n odd if we want to consider that the sub-carrier is included in the chip waveform a modification must be made on the code sequence to obtain the same time domain expression as (1). It is quite easy to go from one convention to the other but this point is quite important because a receiver adapted to one convention would suffer large losses in receiving signal using the other convention.

) 2 ( ) 1 ( with (3) odd n ) ( ) 1 ( ) ( 2 sin ) ( ) ( 2 1 0 S T n m m T k c T k k s k c k T m t h p kT t p c t x t f sign kT t h c t x s c c - - = - - = ⋅ - = ∑ ∑ ∑ - = c π A (-
After discussions with the recognized experts in the domain and according to us, the first convention is the most suitable definition if we want to stick to the original BOC definition. Afterwards we assume that the BOC signal is defined by the first notation whatever the parity of n.

Alternate BOC Signal Definition

Contrary to the BOC signal the ALTBOC signal provides spectral isolation between the two upper and lower components of a same composite signal. This signal allows keeping the BOC implementation simplicity while permitting to differentiate the lobes. The idea of Alternate BOC modulation is to perform the same process as BOC modulation but the sub-carrier used is a "complex" sub-carrier. In that way, the signal spectrum is not split up, but only shifted to higher frequencies. Shifting to lower frequencies is obviously also possible. As for the BOC signal the problem of notation could exist but in [START_REF] Ries | Tracking and Multipath Performance Assessments of BOC Signals Using a Bit-Level Signal Processing Simulator[END_REF] the ALTBOC signal is clearly defined as the product of a PRN code sequence with a "complex" sub-carrier. The ALTBOC signal can be composed of two or four codes. If there are two codes there is no pilot component and the expression of the signal is:

) ( ) ( ) ( ) ( ) ( * _ t er t c t er t c t x L u BOC ALT ⋅ + ⋅ = with [ ] [ ] ) ( ) ( ) 2 sin( ) 2 cos( ) ( t s j t c t f sign j t f sign t er r r S S ⋅ + = ⋅ + = π π c u is the upper code and c L the lower code. T C x(t) p(t) x(t)
If a pilot channel is introduced, four codes are needed and the expression of the ALTBOC signal is:

( ) ( ) ) ( ) ( ) ( * ' ' _ t er c j c t er c j c t x L L u u BOC ALT ⋅ ⋅ + + ⋅ ⋅ + = with [ ] [ ] ) ( ) ( ) 2 sin( ) 2 cos( ) ( t s j t c t f sign j t f sign t er r r S S ⋅ + = ⋅ + = π π
c u is the data upper code, c u ' the pilot upper code, c L the data lower code and c L ' the pilot lower code.

But in this case the signal doesn't have a constant envelope and thus may be distorted within the satellite payload due to non-linear amplification. That's why an innovation was proposed in [START_REF] Godet | Technical Annex to Galileo SRD Signal Plans[END_REF] in order to create a constant envelope signal which is as close as possible to the ALTBOC signal. The innovation introduces new terms which can be compared to intermodulation products. The expression of the new signal obtained, called constant envelope ALTBOC, is presented in [START_REF] Soellner | Comparison of AWGN code tracking accuracy for Alternative-BOC, Complex-LOC and Complex-BOC modulation options in Galileo E5-Band[END_REF]: As the BOC signal, the ALTBOC is generally referred to an ALTBOC(p,q) with:

( ) ( ) ( ) ( )                          - ⋅ + ⋅ ⋅ + +             - ⋅ - ⋅ ⋅ + +             - ⋅ + ⋅ ⋅ + +             - ⋅ - ⋅ ⋅ + = 4 ) ( 4 ) ( 4 ) ( 4 ) ( ) ( ' ' ' ' _ Ts t sc j t sc c j c Ts t sc j t sc c j c Ts t sc j t sc c j c Ts t sc j t sc c j c t x ap ap U U ap ap L L as as U U as as L L BOC ALT with ' ' ' ' ' ' ' ' L L U u L U L U L U U L L U U L c c c c c c c c c c c c c c c c = = = = and ( ) ( ) ( ) ( )                      + - +               - - =                      + + +               - = 4 2 cos 4 2 2 cos 2 1 4 2 cos 4 2 ) ( 4 2 cos 4 2 2 cos 2 1 4 2 cos 4 2 ) ( π π π π π π π π π π t f sign t f sign t f sign t sc t f sign t f sign t f sign t sc
023 . 1 ⋅ = p f s MHz and 023 . 1 ⋅ = q f c

MHz

III. POWER SPECTRUM DENSITY OF THE BOC SIGNAL Assumptions

If we consider a stationary signal:

∑ - - ⋅ = k c k kT t p c t s ) ( ) ( θ (4)
with c k the digital code sequence considered as random and non-periodic, p(t) the materialization waveform, T c the code period and θ a variable which is uniformly distributed on T c .

The autocorrelation function of this signal is:

[ ] [ ] [ ] [ ] ∑ ∑ ∑ ∫ ∑∑ - ℜ × ℜ = - - + - - - - × ℜ = -       - - - - - × = - m c p c c m k T c c c c c k n c c n k mT m T t s t s E dt mT kT t p kT t p T m t s t s E nT t p kT t p E c c E t s t s E c ) ( ) ( 1 ) ( ) ( ) ( ) ( 1 ) ( ) ( ) ( ) ( ) ( ) ( ) (
The power spectrum density of s(t) is the Fourier Transform of the autocorrelation of s(t):

( ) c c fT j c c s m fmT j c c s m c p c c s e S f P T f G e f P m T f G mT m T FT f G π π τ 2 2 2 2 ) ( 1 ) ( ) ( ) ( 1 ) ( ) ( ) ( 1 ) ( = ⋅ ℜ =       - ℜ × ℜ = ∑ ∑ - with P(f) the Fourier Transform of the waveform p(t).
If the code sequence is binary, equiprobable and independent, the power spectrum density is equal to:

c s T f P f G 2 ) ( ) ( =
The BOC signal is regarded as stationary signal. The PRN code sequence is considered random, non periodic, identically distributed, binary, equiprobable and independent. Consequently this formula can be used to calculate the power spectrum density of the BOC signal if the BOC time domain expression is similar to (4). To have a signal similar to (4), the sub-carrier must be included in the chip waveform.

We have seen in the previous section that if n is even there is no problem because the materialization of the signal is equal to the sub-carrier over [0,T c ]. In this case the expression of the signal is:

) 2 ( ) 1 ( with (5) even n ) ( ) ( 2 1 0 S T n m m T k c T k T m t h p kT t p c t s s c c - - = - = ∑ ∑ - = h is the code materialization, it is equal to 1 over [0,T s /2] .
But as shown before if n is odd a modification on the PRN code sequence must be made if we want to consider that the sub-carrier is included in the code materialization. Nevertheless this PRN code modification has no impact on the final expression of the power spectrum density of the BOC signal if the new PRN code can be assumed to be an independent sequence over time. This assumption is true for most of the PRN sequences used in GNSS up to now. So this theory can be used to calculate the power spectrum density of the BOC signal. However it would be wrong to use this theory with short codes.

Expressions of the Power Spectrum Densities

If the BOC signal is sine-phased, the normalized power spectrum densities are equal to:

odd n for ) cos( ) cos( ) sin( 1 ) ( even n for ) cos( ) sin( ) sin( 1 ) ( 2 2             =             = n fT f fT n fT T f G n fT f fT n fT T f G c c c c BOC c c c c BOC π π π π π π π π
And if the BOC signal is cosine-phased the expressions are:

( ) ( ) odd n for 1 cos cos cos 1 ) ( even n for 1 cos cos sin 1 ) ( 2 2                   -             =                   -             ⋅ = n T f n T f f fT T f G n T f n T f f fT T f G c c c c BOC c c c c BOC π π π π π π π π

IV. POWER SPECTRUM DENSITY OF THE ALTBOC SIGNAL

The study is made on the ALTBOC signal with four codes and the power spectrum densities are calculated for the ALTBOC with a non constant envelope and for the ALTBOC with a constant envelope.

Assumptions

The assumptions are the same as these made to calculate the power spectrum density of the BOC signal. The ALTBOC signals are regarded as stationary signals. The different PRN code sequences are considered identically distributed and independent. The most interesting ALTBOC signal is the ALTBOC(15,10) because it is proposed for the Galileo E5a/E5b frequency. Consequently the calculation of the power spectrum density will be made considering n odd and n even but the curves will be only plotted for n odd. The theory used to calculate the power spectrum density of the ALTBOC signal will be the same as the one used to calculate the power spectral density of the BOC signal. So, a modification will be made on each code sequence in order to be able to consider that the sub-carrier is included in the chip waveform in the case n odd.

Power Spectrum Density of the ALTBOC signal

The ALTBOC is equal to:

) ( ) ( ) ( ) ( ) ( _ t n t C t m t C t x L U BOC ALT ⋅ + ⋅ = with ) ( ) ( ) ( ) ( ) ( ) ( ' ' t c j t c t C t c j t c t C L L L u u U ⋅ + = ⋅ + = [ ] [ ] [ ] [ ] ) 2 sin( ) 2 cos( ) ( ) ( ) ( ) 2 sin( ) 2 cos( ) ( ) ( ) ( t f sign j t f sign t b j t a t n t f sign j t f sign t b j t a t m S S S S π π π π ⋅ - = ⋅ - = ⋅ + = ⋅ + =
The autocorrelation of the ALTBOC is equal to:

       ⋅ + ⋅ + ⋅ + ⋅ + ⋅ + ⋅ + ⋅ + ⋅ = ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ' ' ' ' _ τ τ τ τ τ τ τ τ τ τ τ τ τ τ τ τ τ b c a c b c a c b c a c b c a c x K K K K K K K K K K K K K K K K K L L L L u u u u BOC ALT
assuming that the crosscorrelation between the different codes is equal to zero. Moreover the complex crosscorrelation cancel each other out. So, the power spectrum density of the signal is equal to: The first case studied is the case n even. In [START_REF] Pratt | BOC Modulations Waveform[END_REF]] and [START_REF] Betz | Binary Offset Carrier Modulations for Radionavigation[END_REF] it is demonstrated that:

( ) ( ) [ ] ( ) 2 2 2 2 2 2 2 1 cos cos sin 1 ) ( 2 cos ) (       -                     = = n T f n T f fT f f A t f sign FT f A c c c S π π π π π and ( ) ( ) [ ] ( ) 2 2 2 2 2 2 2 cos sin sin 1 ) ( 2 sin ) (                     = = n T f n T f fT f f B t f sign FT f B c c c S π π π π π
Consequently, for n even:

( )             -       = n T f n T f fT T f f G c c c c ALTBOC π π π π cos 1 cos sin 8 ) ( 2 2 2 2
If n is odd, we have:

( ) ( ) [ ] ( ) 2 2 2 2 2 2 2 1 cos cos cos 1 ) ( 2 cos ) (       -                     = = n T f n T f fT f f A t f sign FT f A c c c S π π π π π and ( ) ( ) [ ] ( ) 2 2 2 2 2 2 2 cos sin cos 1 ) ( 2 sin ) (                     = = n T f n T f fT f f B t f sign FT f B c c c S π π π π π
Finally the normalized power spectrum density of the ALTBOC with a non constant envelope and with n odd is:

( )             -       = n T f n T f fT f T f G c c c c ALTBOC π π π π cos 1 cos cos 8 ) ( 2 2 2 2
The next graph represents the power spectrum densities of the ALTBOC(15,10) with a non constant envelope computed with the expression above and with MATLAB simulations. The calculation of the power spectrum density of the ALTBOC with a constant envelope is based on the calculation made in [START_REF] Betz | Binary Offset Carrier Modulations for Radionavigation[END_REF] to calculate the power spectrum density of the BOC signal. The appendix shows that for n odd the normalized power spectrum density of the ALTBOC signal with a constant envelope is:

( )             +             -       -             = 2 4 cos 2 cos 2 2 cos 2 cos cos cos 4 ) ( 2 2 2 2 2 s s s s c c c ALTBOC T f T f T f T f n T f fT T f f G π π π π π π π
The next graph represents the power spectrum densities of the ALTBOC(15,10) with a constant envelope calculated with the expression above and with MATLAB simulations. A comparison can be made between the spectrum of the ALTBOC and the spectrum of the constant envelope ALTBOC.

Fig. 4: Comparison of Power Spectrum Densities

The spectra of the ALTBOC signal and constant envelope ALTBOC signal have similar main-lobes and first sidelobes, even if the central lobe of the constant envelope ALTBOC is 1 dB weaker than this of the ALTBOC.

However their further side-lobes are different. This difference is due to the modification made in order to obtain a constant envelope. Indeed the transformation made on the time domain ALTBOC signal expression added spectral lines. In the Galileo system these spectral lines would be filtered by the RF filter after the amplifier and the two signals would, finally, have very close shapes.

V. CONCLUSION

This paper has provided two main points. First it has underlined the problem of convention concerning the time domain expression of the BOC signal in the case n=2f s /f c odd. Indeed the two conventions are equivalent if n is even but if n is odd a modification must be made on the code sequence to consider that the sub-carrier is included in the chip waveform. Fortunately the properties of the PRN code sequence used in GNSS permit to neglect this modification on the code and the classical expressions of the power spectrum densities can be used.

Secondly the expressions of the power spectrum densities of the ALTBOC and the constant envelope ALTBOC signal have been presented. A particular attention is made on the ALTBOC(15,10) which is candidate for Galileo E5a/E5b frequency band. The constant envelope ALTBOC signal is very interesting because it provides spectral isolation between the two upper and lower components of a same composite signal. By this way it is possible to track each component separately or together.

APPENDIX CALCULATION OF THE ALTBOC SIGNAL WITH A CONSTANT ENVELOPE

The ALTBOC signal with a constant envelope is expressed as:

                   - - ⋅ +       - ⋅ + +       - + ⋅ +       - ⋅ - +       - - ⋅ +       - ⋅ + +       - + ⋅ +       - ⋅ - = 4 ) ( 4 ) ( 4 ) ( 4 ) ( 4 ) ( 4 ) ( 4 ) ( 4 ) ( ) ( ' ' ' ' ' ' ' ' _ Ts t
= ,       - = 4 2 _ Ts t sc sc as as , ) ( 1 _ t sc sc ap ap = and       - = 4 2 _ Ts t sc sc ap ap .
Different terms of crosscorrelation must be taken into account and analyzed. The code sequences are independent, so the crosscorrelation between two different codes is equal to zero. Consequently, all the crosscorrelation terms in which the crosscorrelation between two different codes appears are null. Other crosscorrelation terms are null because the crosscorrelation between the different sub-carrier (sc as and sc ap ) is equal to zero. The last crosscorrelation terms are complex. Fortunately they cancel each other out.

The correlation function of the constant envelope ALTBOC signal is equal to: As the autocorrelations of the different codes are equal, we obtained:

         ℜ + ℜ + ℜ + ℜ + ℜ + ℜ + ℜ + ℜ + ℜ + ℜ + ℜ + ℜ + ℜ + ℜ + ℜ + ℜ = ℜ ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( 2 _ 1 _ 2 _ 1 _ 2 _ 1 _ 2 _ 1 _ 2 _ 1 _ 2 _ 1 _ 2 _ 1 _ 2 _ 1 _ ' ' ' ' ' ' ' '
       ⋅ + ⋅ + ⋅ + ⋅ = 2 2 2 2 _ ) ( 2 _ 4 ) ( 1 _ 4 ) ( 2 _ 4 ) ( 1 _ 4 ) ( f SC T f SC T f SC T f SC T f G ap c ap c as c as c BOC ALT
with SC as _1(f), SC as _2 (f), SC ap _1 (f) and SC as _2 (f) the Fourier Transform of sc as _1(t), sc as _2 (t), sc ap _1 (t) and sc ap _2(t) over [0,T c ].

Beginning with the calculation of the Fourier Transform of sc as _1 over [0,T c ]:

      - - = ∑ - = 2 ) 1 ( ) ( 1 _ 2 / 1 0 s T n m m as T m t t sc s µ with 2 T , 8 3T 2 1 2 8 3T , 4 T 2 1 - 4 T , 8 T 2 1 8 T 0, 2 1 2 ) ( s s s s s s s 2 /                    + -                   + = t s T µ
Before calculating the Fourier Transform of sc as _1(t) the calculation of the Fourier Transform of µ ts/2 (t) is necessary.

∫ + - ⋅       - =             - dt e T m t T m t FT π µ µ            ⋅ + - ⋅ - ⋅ + ⋅ + =             -
            +       +       + - ⋅ - =             - - - 1 4 cos 2 2 cos 1 2 2 2 2 2 2 2 / s s T f j T fm j s T T f T f e f j e t m t FT s s s π π π µ π π
So the Fourier Transform of sc as _1(t) is :

( ) ( ) ∑ - = - - - ⋅             +       +       + - - = 1 0 2 2 2 1 1 4 cos 2 2 cos 1 2 2 ) ( 1 _ n m T fm j m s s T f j as s s e T f T f f j e f SC π π π π π
For n odd we have:

( ) ( )             = - - - - = - ∑ 2 cos 2 cos 1 2 1 1 0 2 2 s s T f n j n m T fm j m T f T f n e e s s π π π π So, ( )               +       +       + -             - = - 1 4 cos 2 2 cos 1 2 2 cos 2 cos 2 ) ( 1 _ 2 s s s s T f jn as T f T f T f T f n f j e f SC s π π π π π π Finally if n is odd, ( ) ( ) 2 2 2 2 2 2 1 4 cos 2 2 cos 1 2 cos cos 4 1 ) ( 1 _               +       +       + -       = s s c c as T f T f n T f fT f f SC π π π π π
The same calculation are made for SC as _2 (f), SC ap _1 (f) and SC as _2 (f).

      - -                        +       = t s T µ ∫ + - ⋅       - =             - dt e T m t T m t FT π µ µ                   -       - ⋅ - =             - - - 4 sin 2 2 sin 2 2 2 2 2 2 / s s T f j T fm j s T T f j T f j e f j e T m t FT s s s π π π µ π π
So the Fourier Transform of sc as _2(t) is :

            +                   = - 4 sin 2 2 sin 2 cos 2 cos 2 ) ( 2 _ 2 s s s s T f jn as T f T f T f T f n f e f SC s π π π π π π And if n is odd, ( ) 2 2 2 2 2 2 4 sin 2 2 sin cos cos 4 1 ) ( 2 _             +             = s s c c as T f T f n T f fT f f SC π π π π π
Continuing with the calculation of the Fourier Transform of SC ap _1 (f),

      - - = ∑ - = 2 ) 1 ( ) ( 1 _ 2 /
            +       -       - ⋅ - =             - ⋅       - =             - - - + - T f T f e f j
                       - -       = t s T µ             +       - ⋅ - =             - ⋅       - =             - - - + - f jn as T f T f T f T f n f e f SC

  Fig. 1: Shapes of sub-carriers Scas and SCap Finally the constant envelope ALTBOC signal is a classical 8-PSK modulation with a non-constant allocation of the 8 phase-states.

  f) and B(f) the Fourier Transforms of sign[cos(2πf s t)] and sign[sin(2πf s t)].

Fig. 2 :

 2 Fig. 2: Power Spectrum Density of the ALTBOC(15,10)

Fig. 3 :

 3 Fig. 3: Power Spectrum Density of the constant envelope ALTBOC(15,10)

  normalized power spectrum density of the ALTBOC signal with a constant envelope is if n odd:

Presented at ION GNSS 2005, San Diego

Emilie Rebeyrol graduated as a telecommunications engineer from the INT (She is now a Ph.D student at the satellite navigation lab of the ENAC. Currently she carries out research on Galileo signals and their generation in the satellite payload in collaboration with the CNES (Centre National dLionel Ries is a navigation engineer in the Transmission Techniques and signal processing department, at CNES since June 2000. He is responsible of research activities on GNSS2 signal, including BOC modulations and GPS IIF L5. He is involved in the GALILEO program, in which he supports ESA