Julien Melleray

EXTENSIONS OF GENERIC MEASURE-PRESERVING ACTIONS

Keywords:

We show that, whenever Γ is a countable abelian group and ∆ ≤ Γ is a finitely-generated subgroup, a generic measure-preserving action of ∆ on a standard atomless probability space (X, µ) extends to a free measure-preserving action of Γ on (X, µ). This extends a result of Ageev, corresponding to the case when ∆ is infinite cyclic.

2010 Mathematics Subject Classification

INTRODUCTION

A classical subject in ergodic theory is the study of measure-preserving actions of countable groups on a standard atomless probability space (X, µ). Given two countable groups ∆ ≤ Γ, one may ask whether any measure-preserving action of ∆ on (X, µ) extends to a meaure-preserving action of Γ, and it is well-known that, in this generality, the question has a negative answer.

Let G denote the automorphism group of (X, µ), endowed with its usual Polish group topology. The set of measure-preserving actions of Γ on (X, µ), which is just the set of homomorphisms from Γ into G, may naturally be identified with a closed subset of G Γ (endowed with the product topology), and so the space of Γ-actions is a Polish space in its own right. Then, one may wonder what happens for a generic action of ∆ on (X, µ), in the sense of Baire category: can a generic action of ∆ on (X, µ) be extended to an action of Γ on (X, µ)? This problem is for instance mentioned in [K2, p. 75], where one can find an example of countable groups ∆ ≤ Γ such that ∆ is infinite cyclic and a generic action of ∆ cannot be extended to an action of Γ.

It is well-known that, for any countable group ∆, generic actions of ∆ are free and so, given a pair of countable groups ∆ ≤ Γ, one may also ask whether a generic action of ∆ can be extended to a free action of Γ. A complete answer to that question, in the case ∆ = Z and Γ is abelian, has been provided by Ageev [START_REF]On the genericity of some nonasymptotic dynamic properties[END_REF]Theorem 2]: in that case, a generic action of ∆ does extend to a free action of Γ. In this paper, we extend Ageev's result to the case when ∆ is finitely generated abelian 1 , proving the following theorem (Corollary 3.8 below).

Theorem. Let Γ be a countable abelian group and ∆ a finitely-generated subgroup of Γ. Then a generic measure-preserving action of ∆ on a standard atomless probability space (X, µ) can be extended to a free measure-preserving action of Γ on (X, µ).

Our approach to this question is via category-preserving maps and a generalization of the classical Kuratowski-Ulam theorem valid for these maps; these notions were first considered in [MT] 2 .

The paper is organized as follows: first we quickly go over some background on the space of actions of countable groups and properties of generic measurepreserving Z-actions that will be needed in our proof. Next, we recall the definition of a category-preserving map, establish some properties, and discuss the relationship between our approach to the problem tackled here and a classical approach to similar problems in ergodic theory, which is via "Dougherty's lemma" and the notion of points of local density for a continuous map between two Polish spaces. Then we give a proof of our main result and discuss possible generalizations. While we prove that most of these possible generalizations are false, we leave open the question of whether one might drop the assumption that ∆ is finitely generated in the statement of our main result.

Acknowledgements. When preparing this paper, I benefitted from conversations with several people; in particular I'd like to thank Oleg Ageev for mentioning his paper [A]; Damien Gaboriau for interesting discussions; Bruno Sévennec for pointing out the existence of the countable group which is used to prove Theorem 3.9; Sławomir Solecki for important bibliographical information; and Todor Tsankov for useful remarks and corrections on a first draft of the paper. Work on this project was partially supported by the ANR network AGORA, NT09-461407 and ANR project GRUPOLOCO, ANR-11-JS01-008.

BACKGROUND AND TERMINOLOGY

2.1. The space of actions. For information on Polish groups and spaces, we refer the reader to [K] and [G]. The book [K2] is a good reference for ergodic theory seen from the descriptive set theoretic point of view.

Let Γ be a countable group and G be a Polish group. We denote by Hom(Γ, G) the set of homomorphisms of Γ into G. If we endow G Γ with its product Polish topology τ (the product of countably many copies of (G, τ)) then Hom(Γ, G) is a closed subset of G Γ , hence (Hom(Γ, G), τ) is a Polish topological space in its own right, and the conjugation action given by (g • π)(γ) = gπ(γ)g -1 is continuous. We may then use Baire category notions in Hom(Γ, G); below, we say that a subset Ω ⊆ Hom(Γ, G) is generic, or comeager, if it contains a countable intersection of dense open subsets of Hom(Γ, G). Dually, a set is meager if its complement is comeager; we will often use the formulation "a generic π ∈ Hom(Γ, G) has property (P)" to mean "the set of all π ∈ Hom(Γ, G) which have property (P) is generic".

By a standard atomless probability space, we mean, as usual, a probability space isomorphic to [0, 1] endowed with the Lebesgue measure. If G = Aut(X, µ) denotes the automorphism group of a standard atomless probability space (X, µ), then we endow G with its usual Polish group topology, which is most easily described by its convergent sequences: a sequence (g n ) of elements of G converges to g ∈ G, if, for any measurable A ⊆ X, one has µ(g n A∆gA) → 0 as n → +∞. Note that two measure-preserving automorphisms of (X, µ) are identified if they coincide on a set of full measure; since all the subgroups of G that we consider here are countable, this should not cause any confusion and so we'll just neglect sets of measure zero in what follows.

Notation. In the remainder of this article, (X, µ) is a standard atomless probability space and G denotes its automorphism group, endowed with its usual Polish topology.

We say that π ∈ Hom(Γ, G) is free if µ({x : π(γ)x = x}) = 0 for all γ = 1. The set of free measure-preserving actions is dense G δ in Hom(Γ, G) [GK]. If Γ is finite, any two free measure-preserving actions of Γ are conjugate, hence a free measurepreserving action of Γ on (X, µ) has a comeager conjugacy class. While such a strong fact is not true in general (for instance, conjugacy classes in Hom(Γ, G) are meager whenever Γ is amenable and infinite [FW]), it is well-known that for any countable group Γ there exist actions of Γ on (X, µ) which have a dense orbit under conjugacy [GTW], so the 0 -1 topological law (see e.g. [K, 8.46]) implies that any conjugacy-invariant subset with the property of Baire is either meager or comeager. This fact seems to be often called the dynamical alternative, after the terminology of [GK], where it was first established.

Let us also note here a few results that will be useful below;

Theorem 2.1 (King [K4]). A generic element of G admits roots of all orders. Actually, the map g → g n is category-preserving (see below for a definition) for all n = 0.

This was first proved by King in [K4], then de la Rue and de Sam Lazaro gave a simpler presentation of King's proof in [dlRdSL], and improved the above result by showing that a generic element g of G embeds in a flow, i.e there exists a continuous homomorphism F : (R, +) → G such that g = F(1).

For g ∈ G, we denote by g the subgroup of G generated by g.

Theorem 2.2 (Chacon-Schwartzbauer [CS]). For a generic element g of G, the centralizer C(g) of g coincides with g ; in particular C(g) is a maximal abelian subgroup of G.

In an earlier version of this article, the above result was incorrectly attributed to King [K3]; actually, it was proved much earlier: it is stated in [ACS], where the authors say it was already proved by Chacon-Schwartzbauer [CS] (though the result does not seem to appear explicitly there)3 . Yet another proof recently appeared in [MT].

Stepin and Eremenko, using techniques originated by Ageev and de la Ruede Sam Lazaro, proved that the centralizer of a generic element is large in the following sense.

Theorem 2.3 (Stepin-Eremenko [SE]). The infinite-dimensional torus T ω embeds isomorphically (as an abstract group) in the centralizer of a generic element of G.

What we really need for our proof is a weaker corollary of this theorem, originally proved by Ageev [A2], namely the fact that if g is a generic element of G then any finite abelian group isomorphically embeds in the centralizer of g.

Though it will not be needed in this paper, we mention for completeness that a recent result of Solecki [S], who proved that the centralizer of a generic element of Aut(X, µ) is a continuous homomorphic image of a closed subspace of L 0 (R) and contains an increasing sequence of finite dimensional tori whose union is dense (in [S], Solecki explains how to use this result to derive the theorem of Stepin-Eremenko quoted above, which is not explicitly proved in [SE] even though it is stated in the abstract of that paper and can also be derived from the authors' arguments).

2.2. Category-preserving maps. As explained in the introduction, our aim is to show that, whenever ∆ ≤ Γ are countable abelian groups and ∆ is finitely generated, a generic element of Hom(∆, G) may be extended to a free element of Hom(Γ, G). In particular, denoting by Res the restriction map from Hom(Γ, G) to Hom(∆, G), we would like to show that the image of Res is comeager. Since the conjugacy action of G on Hom(∆, G) is topologically transitive, the 0 -1 topological law implies that it is enough to show that the image of Res is not meager.

A common approach to this type of question in ergodic theory is based on an observation sometimes called Dougherty's lemma (see e.g [K3], [K4], [SE], [T]); below we quickly discuss this approach, as well as the technique used in [MT], and compare the two.

Definition 2.4. Let Y, Z be topological spaces and f

: Y → Z a continuous map. Say that y ∈ Y is locally dense for f if for any neighborhood U of y the set f (U) is a neighorhood of f (y).
Proposition 2.5 ("Dougherty's lemma " ). Assume Y, Z are complete metric spaces, f : Y → Z is continuous and the set of points which are locally dense for f is dense in Y. Then f (Y) is not meager.

Proof. Assume that the set of points which are locally dense for f is dense and f (Y) ⊆ ∪ n F n where each F n is a closed subset of Z with empty interior. Then Y = ∪ n f -1 (F n ) so some f -1 (F n ) must have nonempty interior, hence must contain a point of local density, so the interior of

f ( f -1 (F n )) ⊆ F n is nonempty, a contradiction.
Conversely, the next proposition shows that, when Y is separable, the existence of points of local density is necessary for f (Y) to be non meager, though it is certainly not necessary that the set of points of local density be dense; as a side remark, note that this is always a G δ subset of Y, see [K3].

Proposition 2.6. Assume Y, Z are Polish spaces, f : Y → Z is continuous and let A = {y ∈ Y : y is not locally dense for f }. Then f (A) is meager.
Proof. If y is not locally dense for f , then there exists an open subset U such that y ∈ U and f (y

) ∈ Int( f (U)). Hence f (y) ∈ f (U) \ Int( f (U)). Choosing a countable basis of open subsets (U n ) for the topology of Y, we see that f (A) ⊆ n f (U n ) \ Int( f (U n )) . Hence f (A) is meager.
A different approach, at least on the face of it, was used in [MT] to study similar questions.

Definition 2.7 ([MT]

). Let Y, Z be Polish spaces. Say that a continuous map f : Y → Z is category-preserving if it satisfies one of the following equivalent conditions: So far, we have explained an approach to showing that the image of the restriction map Res : Hom(Γ, G) → Hom(∆, G) is comeager; actually, we want to prove more, since we want to prove that a generic action of ∆ extends to a free action of Γ. In other words, we want to prove that the restrictions of free actions of Γ form a comeager set in Hom(∆, G). This will come for free (no pun intended) if we etablish that the restriction map is category-preserving: indeed it is easy to check, assuming that the restriction map is category-preserving, that the restrictions of elements taken in any comeager subset of Hom(Γ, G) must form a comeager subset of Hom(∆, G)

(i) For any comeager A ⊆ Z, f -1 (A) is comeager. (ii) For any nonempty open U ⊆ Y, f (U) is not meager. (iii) For any nonempty open U ⊆ Y, f (U)
Saying that f : Y → Z is category-preserving is a strong condition, much stronger than just saying that f (Y) is comeager. This is witnessed by the following theorem.

Theorem 2.9 ( [MT]). Let Y, Z be Polish spaces, and f : Y → Z be a category-preserving map. Let also A be a subset of Y with the property of Baire. Then the following assertions are equivalent:

(i) A is comeager in Y. (ii) {z : A ∩ f -1 (z) is comeager in f -1 (z)} is comeager in Z.
In what follows, we will use the notation ∀ * y ∈ Y A(y) to signify that A is comeager in Y; for example, the equivalence in the above theorem, when written using this notation, becomes (for A ⊆ Y with the property of Baire):

(∀ * y ∈ Y A(y)) ⇔ (∀ * z ∈ Z ∀ * y ∈ f -1 (z) A(y)) .
The above statement, in the case Y = Y 1 × Y 2 and f is a coordinate projection, is the classical Kuratowski-Ulam theorem. It enables one to "split category along the fibers of f " and will be extremely useful in our proof.

After a first draft of this paper was completed, I became aware of the paper [T], where the author considers maps which "respect genericity" -i.e such that the inverse image of a comeager set is comeager, and the image of a comeager set is comeager. Any map which respects genericity is category-preserving, and a category-preserving map respects genericity if and only if it has a dense image.

Thus, in the context of this article, the two notions are essentially equivalent; compared to [T], our approach is somewhat simpler because we have Theorem 2.9 at our disposal, while [T] only uses the classical Kuratowski-Ulam theorem.

The following simple proposition from [MT] will also be useful. As an example, an immediate corollary of this lemma is that, whenever H, K are Polish groups, a continuous homomorphism φ : H → K with non-meager image must be category-preserving; actually it is well-known that under these assumptions φ must be open. Let us give a slightly more interesting example.

Lemma 2.11. Let ∆ ≤ Γ be two groups, and assume that ∆ is finite and Γ is countable. Then the restriction map Res : Hom(Γ, G) → Hom(∆, G) is category-preserving.

Proof. Let Y denote the set of all free actions of Γ with a dense conjugacy class. Res(Y) is conjugacy-invariant and contains a free action of ∆, hence it must contain all of them (recall that they are all conjugate) and so is comeager. The action of G on Y is minimal, so Res : Y → Hom(∆, G) is category-preserving. Since Y is comeager in Hom(Γ, G) ( [GTW], see [START_REF]Global aspects of ergodic group actions[END_REF]Theorem 10.7] for a simple proof) this implies that Res is category-preserving.

In the proof of the main result, we will also need the following facts from [MT].

Lemma 2.12 ( [MT]). Let H be a Polish group and Γ be a countable abelian group such that, for a generic π ∈ Hom(Γ × Z, H), π(Γ × Z) = π(Γ). Then the restriction map Res : Hom(Γ × Z, H) → Hom(Γ, H) is category preserving.

This criterion was applied to obtain the following result (also proved, earlier and independently, by Tikhonov [T], using his notion of map respecting genericity).

Lemma 2.13 ([MT]

). For any integers d ≤ k, the restriction map from Hom(Z k , G) to Hom(Z d , G) is category-preserving.

PROOF OF THE MAIN RESULT

We are now ready to give the proof of our main result. We break down the argument in a series of lemmas, most of which are special cases of the main result. Some of the lemmas were already known, but the proofs we give here seem simpler and we try to limit the appeal to black boxes as much as possible; the two results that are used below and that are not proved here or in [MT] are Theorems 2.1 and 2.3. We begin by setting the notation to be used in the proof.

Notation. We recall that (X, µ) denotes a standard atomless probability space and G its automorphism group, endowed with its usual Polish topology. All groups are noted multiplicatively (in particular, 1 stands for the neutral element). If Γ is a group and A is a subset of ∆, we denote by A the group generated by A. By C k (G) we mean the set of commuting k-uples of elements of G, which we identify with Hom(Z k , G) whenever it is convenient. If ḡ ∈ C k (G), C( ḡ) denotes the centralizer of ḡ ; when Γ is some finite abelian group and ḡ ∈ C k (G), we let C Γ ( ḡ) denote the set of Γ-actions on (X, µ) which commute with ḡ. Similarly, if Γ is some finite group, π ∈ Hom(Γ, G) and k ∈ ω, C k (π) stands for the set of commuting k-uples of elements of G which commute with π(γ) for all γ ∈ Γ. Whenever d ≤ k and we view Z d as a subgroup of Z k , we view it as the subgoup of k-uples generated by the first d elements of the natural basis of Z k . Lemma 3.1. Let d be an integer, and Γ be a finite abelian group. Then the restriction map

Res : Hom(Z d × Γ, G) → Hom(Z d , G) is category-preserving.
Proof. Since the restriction map Hom(Z d , G) → Hom(Z, G) is category-preserving (Lemma 2.13), Theorems 2.2 and 2.3 imply that

∀ * ḡ ∈ C d (G) C( ḡ) = g 1
is abelian and contains an isomorphic copy of T ω .

It is also well-known that a generic element of Hom(Z d , G) is free ergodic. Now, choose ḡ ∈ C d (G) such that the action Z d (X, µ) induced by ḡ is free ergodic, and C( ḡ) = g 1 is an abelian group containing an isomorphic copy of T ω .

We may extend the action Z d (X, µ) induced by ḡ as follows: pick an isomorphic embedding φ : Γ → C( ḡ), and set π(n 1 , . . . ,

n d , γ) = g n 1 1 • • • g n d d φ(γ)
. This action extends the original action of Z d to Z d × Γ, and we claim that π is free. To see this, pick h ∈ ḡ and γ ∈ Γ, and assume that

µ({x : hφ(γ)(x) = x}) > 0 .
Since {x : hφ(γ)(x) = x} is ḡ -invariant and ḡ acts ergodically, we get

µ({x : hφ(γ)(x) = x}) = 1 .
Since γ has finite order, h must be of finite order and so h = 1 since the original Z d -action was free. Hence φ(γ) = 1, so γ = 1.

Thus a generic Z d -action extends to a free action of Z d × Γ; aplying Proposition 2.10 as in the proof of Lemma 2.11, we obtain that Res is category preserving.

An immediate corollary of this and Lemma 2.12 is the following. Lemma 3.2. Let Γ be a finite abelian group, and d ≤ k be two integers. Then the restriction map Res :

Hom(Z k × Γ, G) → Hom(Z d × Γ, G) is category-preserving.
Proof. It is enough to show the above result when k = d + 1 (a composition of category-preserving maps is still category-preserving, a fact that will be useful to us more than once) and d ≥ 1, since the case d = 0 is covered by Lemma 2.11. From Lemma 3.1 and Theorem 2.2 we obtain

∀ * π ∈ Hom(Z d+1 × Γ, G) π(Z) is maximal abelian . Hence ∀ * π ∈ Hom(Z d+1 × Γ, G) π(Z d+1 × Γ) = π(Z) = π(Z d × Γ) .
Applying Lemma 2.12 yields the desired result.

Lemma 3.3. Fix an integer d. Then, for a generic ḡ ∈ C d (G), the group C( ḡ) is divisible.

Proof. Fixing some nonzero integer p, it is enough to show that for a generic ḡ any element of C( ḡ) has a p-th root in C( ḡ). We begin with the case when d is equal to 1. We know, by Theorem 2.1, that

∀ * h ∈ G ∃ f ∈ G h = f p .
Applying Lemma 2.13 and the fact that the centralizer of a generic g coincides with g , we obtain

∀ * (g, h) ∈ C 2 (G) C(h) = C(g) = g and ∃ f ∈ G h = f p .
Since the equation h = f p implies that f and h commute, the above equation implies, using Lemma 2.13 again (projecting on the other coordinate) and Theorem 2.9, that

∀ * g ∈ G ∀ * h ∈ C(g) = g ∃ f ∈ C(g) h = f p .
In other words, for a generic g and any integer p the homomorphism h → h p of the abelian Polish group C(g) has a comeager image, hence it must be surjective, and we are done.

The general case immediately follows from Lemma 2.13, since

∀ * ḡ ∈ C d (G) C( ḡ) = C(g 1 ) and C(g 1 ) is divisible.
The following closely related lemma was already proved in [T] (using different vocabulary).

Lemma 3.4. For any nonzero integers (n 1 , . . . , n k ) the map (g 1 , . . . ,

g k ) → (g n 1 1 , . . . , g n k k ) is category-preserving from C k (G) to itself.
Proof. It is enough to show that the map (g 1 , . . . , g k ) → (g 1 , . . . , g k-1 , g p k ) is categorypreserving for each k ≥ 2 (the case k = 1 is the content of Theorem 2.2) and p = 0. Let O be comeager in C k (G). We have

∀ * (g 1 , . . . , g k-1 ) ∈ C k-1 (G) ∀ * h ∈ C(g 1 , . . . , g k-1 ) (g 1 , . . . , g k-1 , h) ∈ O .
From Lemma 3.3 we know that h → h p is a surjective homomorphism from C(g 1 , . . . , g k-1 ) to itself for a generic (g 1 , . . . , g k-1 ) ∈ C k-1 (G), so it is categorypreserving and the above equation yields

∀ * (g 1 , . . . , g k-1 ) ∈ C k-1 (G) ∀ * h ∈ C(g 1 , . . . , g k-1 ) (g 1 , . . . , g k-1 , h p ) ∈ O . That is, ∀ * (g 1 , . . . , g k ) ∈ C k (G) (g 1 , . . . , g k-1 , g p k ) ∈ O .
Lemma 3.5. Let Γ be a finite abelian group, and ∆ be a torsion-free subgroup of Z k × Γ. Then the restriction map Res :

Hom(Z k × Γ, G) → Hom( ∆, Γ , G) is category- preserving.
Note before the proof that, as a group, ∆, Γ ∼ = ∆ × Γ; also, ∆ ∼ = Z d for some d ≤ k.

Proof. We may assume that ∆ is nontrivial, i.e. isomorphic to Z d for some d ∈ {1, . . . , k}. Using the existence of simultaneous bases for subgroups of a free finitely-generated abelian group, we may find a basis e 1 , . . . , e k of Z k , nonzero integers n 1 , . . . , n d and elements γ 1 , . . . γ d of Γ such that ∆ = (e n i i , γ i ) : i ≤ d . Using these particular generating sets, the restriction map may be identified with the map G). We know from Lemma 2.11 and Theorem 2.9 that

Hom(Z k × Γ, G) → Hom(Z d × Γ, G) (g 1 , . . . , g k , π) → (g n 1 1 π(γ 1 ), . . . , g n d d π(γ d ), π) Let O be a comeager subset of Hom(Z d × Γ,
∀ * π ∈ Hom(Γ, G) ∀ * ḡ ∈ C d (π) ( ḡ, π) ∈ O .
Since, for each fixed π, the map ḡ → (g 1 π(γ 1 ), . . . , g d π(γ d )) is a homeomorphism of C d (π), this may be rewritten as

∀ * π ∈ Hom(Γ, G) ∀ * ḡ ∈ C d (π) (g 1 π(γ 1 ), . . . , g d π(γ d ), π) ∈ O .
Using Theorem 2.9 and Lemma 3.1, this is the same as

∀ * ḡ ∈ C d (G) ∀ * π ∈ C Γ ( ḡ) (g 1 π(γ 1 ), . . . , g d π(γ d ), π) ∈ O . Applying Lemma 3.4 this yields ∀ * ḡ ∈ C d (G) ∀ * π ∈ C Γ ( ḡ) (g n 1 1 π(γ 1 ), . . . , g n d d π(γ d ), π) ∈ O .
Finally, Lemma 3.2 and Theorem 2.9 lead to the desired

∀ * π ∈ Hom(Z k × Γ, G) Res(π) ∈ O .
Lemma 3.6. Let Γ 2 ≤ Γ 1 be finite abelian groups and d be an integer. Then Res :

Hom(Z d × Γ 1 , G) → Hom(Z d × Γ 2 , G) is category-preserving.
Proof. We claim that, for a generic ḡ ∈ C d (G), any homomorphism from Γ 2 to C( ḡ) extends to a homomorphism from Γ 1 to C( ḡ) . The proof of this is the same as the classical proof of the fact that a character of a finite abelian group extends to a character of a finite abelian supergroup. By induction, it is enough to prove the above fact in case there exists x ∈ Γ 1 such that Γ 1 = Γ 2 , x . Pick such an x, and let m be the smallest nonnegative integer such that x m = γ ∈ Γ 2 . Let also ḡ be such that C( ḡ) = ḡ is abelian and divisible.

Then for any homomorphism φ from Γ 2 to C( ḡ), we may find h ∈ C( ḡ) such that h m = φ(γ), and extend φ to Γ 1 by setting, for any k < ω and δ ∈ Γ 2 , φ(x k δ) = h k φ(δ). The verification that this is a well-defined homomorphism from Γ 1 to C( ḡ) is left to the reader.

Since Γ 1 , Γ 2 and C( ḡ) are abelian, the restriction map from C Γ 1 ( ḡ) to C Γ 2 ( ḡ) is a (continuous) homomorphism between two Polish groups, and we just proved that this homomorphism is surjective: hence it must be open, and in particular category-preserving.

We are almost done: let O be a comeager subset of Hom(Z d × Γ 2 , G). Then we know from Lemma 3.2 that

∀ * ḡ ∈ C d (G) ∀ * π ∈ C Γ 2 ( ḡ) ( ḡ, π) ∈ O .
Since a generic ḡ ∈ C d (g) is such that C( ḡ) = ḡ is abelian and divisible, our reasoning above yields

∀ * ḡ ∈ C d (G) ∀ * φ ∈ C Γ 1 ( ḡ) ( ḡ, φ |Γ 2 ) ∈ O . That is, ∀ * π ∈ Hom(Z d × Γ 1 , G) Res(π) ∈ O .
Now to the proof of our main result.

Theorem 3.7. Let Γ be a countable abelian group and ∆ be a finitely generated subgroup of Γ. Then the restriction map Res : Hom(Γ, G) → Hom(∆, G) is category-preserving.

Proof. We begin with the case when Γ is finitely generated. We may assume that for some nonzero integers d ≤ k, finite groups F 1 ≤ F 2 , and a subgroup H of

Z k × F 2 isomorphic to Z d , we have Γ = Z k × F 2 and ∆ = H × F 1 .
Then aplying Lemmas 3.5 and 3.6 to the following sequence yields the desired result:

Hom(Z k × F 2 , G) → Hom( H, F 2 , G) ∼ = Hom(H × F 2 , G) → Hom(H × F 1 , G) .
Now we turn to the case when Γ is not finitely generated; we apply the same method as in [MT] to deal with that case. Going back to the definition of a categorypreserving map, we pick a dense open O ⊆ Hom(∆, G) and a nonempty open U ⊆ Hom(Γ, G); without loss of generality we may assume that there is a finitely generated subgroup Γ ′ of Γ containing ∆, and a nonempty open subset U ′ of Hom(Γ ′ , G), such that

U = {π ∈ Hom(Γ, G) : π |Γ ′ ∈ U ′ } .
Since Γ ′ is finitely generated, the restriction map from Hom(Γ ′ , G) to Hom(∆, G) is category-preserving, so G). Letting γ 1 , . . . , γ n denote generators of Γ ′ , we may further assume that there exist π 0 ∈ U ′′ , ǫ > 0 and a finite measurable partition A of (X, µ) such that, for any π ∈ Hom(Γ ′ , G), one has

U ′′ = {π ∈ U ′ : π |∆ ∈ O} is open nonempty in Hom(Γ ′ ,
π ∈ U ′′ ⇔ ∀A ∈ A ∀i ∈ {1, . . . , n} µ(π 0 (γ i )(A)∆π(γ i )(A)) < ǫ . Let ψ : Γ (X Γ/Γ ′ , µ Γ/Γ ′ )
be the action of Γ co-induced by π 0 (see [K2, 10(G)]), and let Θ : X Γ/Γ ′ → X be defined by Θ( f ) = f (Γ ′ ). Then, denoting by B the (finite) measurable partition generated by A and π 0 (A), one may pick a measurepreserving bijection T : X Γ/Γ ′ → X such that T -1 (B) = Θ -1 (B) for all B ∈ B, and define φ ∈ Hom(Γ, G) by setting φ(γ) = Tψ(γ)T -1 . The construction ensures that φ |Γ ′ ∈ U ′′ , so φ ∈ U ∩ Res -1 (O), and we are done.

Remark. In general, given a Polish group H, and countable groups ∆ ≤ Γ, one may ask whether the restriction map from Hom(Γ, H) to Hom(∆, H) is categorypreserving. The current paper is concerned with the case H = Aut(X, µ), but this question is certainly also of interest for other Polish groups, such as the isometry group of the Urysohn space. Thus is seems worth pointing out that the strategy of proof presented here could conceivably be adapted to other cases; looking at the proof, it is clear that the most important (and, probably, hardest) step is to understand what happens when Γ = Z and ∆ = nZ. So, Chacon-Schwartzbauer's result (Theorem 2.1) seems to be the key to understand the general situation. If one were able to show that a generic isometry of the Urysohn space admits infinitely many n-th roots for any n then, using a line of reasoning similar to the one presented here (and some results of [MT]), one could prove that Theorem 3.7 holds also when G is the isometry group of the Urysohn space.

Corollary 3.8. Let Γ be a countable abelian group and ∆ be a finitely generated subgroup of Γ. Then a generic measure-preserving action of ∆ extends to a free measure-preserving action of Γ.

Proof. The restriction map Res : Hom(Γ, G) → Hom(∆, G) is category-preserving and has a non meager, conjugacy-invariant range, hence a comeager range. Thus the image of any comeager subset of Hom(Γ, G) is comeager in Hom(∆, G); as free actions of Γ form a dense G δ subset of Hom(Γ, G), we are done. Now, it is reasonable to wonder to which extent one can strengthen Theorem 3.7. Clearly, if Γ is no longer assumed to be abelian, then the restriction map does not need to be category-preserving in general -indeed, it will never be categorypreserving if ∆ is an abelian central subgroup of Γ, Γ is nonabelian and ∆ contains an element with infinite order. To see this, note that it follows from our results that for such a ∆, a generic π ∈ Hom(∆, G) is such that C(π) = π(∆) is an abelian group; thus, for a generic π ∈ Hom(∆, G), no action π of Γ extending π can be free, since π(Γ) ≤ C(π) must be abelian. Hence, even if ∆ is infinite cyclic and H is a finite nilpotent group, the restriction map Res : Hom(∆ × H, G) → Hom(∆, G) need not be category-preserving (the simplest counterexample being Γ = Z × Q 8 , where Q 8 denotes the quaternion group, and ∆ = Z).

Then, one may wonder whether a weakening of Theorem 3.7 holds in greater generality, namely, whether when ∆ ≤ Γ and ∆ is (say) abelian, a generic measurepreserving action of ∆ may be extended to an action of Γ (we are no longer asking that the extension be free). This statement is also false in general; a counterexample appears in [K2, p. 75]. We quickly mention another counterexample: Ageev proved in [A] that a generic element of G is not conjugate to its inverse, thus a generic measure-preserving Z-action cannot be extended to an action of any nontrivial semidirect product Z ⋊ H. Indeed, the only nontrivial group automorphism of Z is n → -n, so the image of the generator of Z under any morphism from Z ⋊ H to G must be conjugate to its inverse, and generically this does not happen.

In view of the above counterexamples, it is tempting to ask the following question: if Γ is a countable group and ∆ is an abelian central subgroup of Γ, is it true that a generic measure-preserving action of ∆ may be extended to a measurepreserving action of Γ? This is false even under the additional assumption that ∆ is solvable (I do not know of an example with ∆ nilpotent but it seems likely that such an example exists); I am grateful to Bruno Sévennec for pointing out to me the existence of a group Γ as in the example below. Theorem 3.9. There exists a countable polycyclic (hence, solvable) group Γ, whose center contains an infinite cyclic subgroup ∆, such that a generic action of ∆ cannot be extended to an action of Γ.

Proof. Let Γ be the countable group defined by the following presentation with three generators: Γ = x, y, z| [x, y] = z 4 , zxz -1 = x -1 , zyz -1 = y -1 . K.A. Hirsch showed that Γ is torsion-free, polycyclic, and its abelianization is finite (see [H] for the original reference; this is exercise 15 p.158 of [R]); from the above presentation we see that z 2 is central.

Let ∆ = z 2 ≤ Γ. We know that, for a generic action π of ∆, π is free and the centralizer of π(z 2 ) is an abelian group; since z 2 is central in Γ, any action π of Γ extending π must take its values in the abelian group C(π(z 2 )), hence have finite range since Γ has no infinite abelian quotients. Thus such a π cannot exist, since π is free and so π(∆) = π(∆) must be infinite if π extends π.

While it would be interesting to understand exactly for which pairs of groups ∆ ≤ Γ the restriction map from Hom(Γ, G) to Hom(∆, G) is category-preserving, or simply has a comeager image, the above examples show that a general answer will necessarily be complicated and is perhaps too much to ask for. Still, perhaps one may generalize Theorem 3.7 to the case when ∆ is any countable abelian group (i.e, is no longer supposed to be finitely generated), and we end the paper with that question.

Question 3.10. Is it true that, whenever ∆ ≤ Γ are countable abelian groups, the restriction map Res : Hom(Γ, G) → Hom(∆, G) is category-preserving?

  is somewhere dense.Note that f being category-preserving implies in particular that f (Y) is not meager; also, any continuous open map is category-preserving.It turns out that the two approaches are equivalent. The implication from right to left is immediate from the definition of a point of local density and condition 2.7 (iii). To see the converse, assume that there is a nonempty open subset U of Y such that U does not contain any point of local density. Then Proposition 2.6 implies that f (U) is meager, so f is not categorypreserving.

	Proposition 2.8. Assume Y, Z are Polish spaces and f : Y → Z is continuous. Then f is
	category-preserving if and only if the set of points which are locally dense for f is dense in
	Y.
	Proof.

  Since f (Y) is not meager, there must exist a point of local density y ∈ Y. Then every point of H • y is a point of local density, so the set of points of local density is dense, and we are done.

	Proposition 2.10. Let H be a Polish group, Y, Z be two Polish H-spaces and f : Y → Z
	a H-map. Assume that Y is minimal (i.e, every orbit is dense) and f (Y) is not meager.
	Then f is category-preserving.
	Proof.

After completing a first draft of this paper, I became aware that a similar approach was used by Tikhonov[T] to study embeddings of generic actions of Z d in continuous actions of R d .

I am grateful to S. Solecki for pointing this out to me.


Alice Marascu

Florent Masseglia

ATYPICITY DETECTION IN DATA STREAMS: A SELF-ADJUSTING APPROACH

Outlyingness is a subjective concept relying on the isolation level of a (set of) record(s). Clustering-based outlier detection is a field that aims to cluster data and to detect outliers depending on their characteristics (i.e. small, tight and/or dense clusters might be considered as outliers). Existing methods require a parameter standing for the "level of outlyingness", such as the maximum size or a percentage of small clusters, in order to build the set of outliers. Unfortunately, manually setting this parameter in a streaming environment should not be possible, given the fast time response usually needed. In this paper we propose WOD, a method that separates outliers from clusters thanks to a natural and effective principle. The main advantages of WOD are its ability to automatically adjust to any clustering result and to be parameterless.

INTRODUCTION

Atypical behaviours are the basis of a valuable knowledge in domains related to security (e.g. fraud detection for credit card [START_REF] Aleskerov | Cardwatch: A neural network based database mining system for credit card fraud detection[END_REF], cyber security [START_REF] Ertoz | Minds -minnesota intrusion detection system[END_REF] or safety of critical systems [START_REF] Fujimaki | An approach to spacecraft anomaly detection problem using kernel feature space[END_REF]). Atypicity generally depends on the isolation level of a (set of) records, compared to the dataset. One possible method for finding atypic records aims to perform two steps. The first step is a clustering (grouping the records by similarity) and the second step is the identification of clusters that do not correspond to a satisfying number of records. Actually, atypical events (or outliers) might be indicative of suspicious data such as skewed or erroneous values, entry mistakes or malicious behaviours. A malicious behaviour can be detected as an outlier in datasets such as transactions in a credit card database or records of usage on a web site.

To the best of our knowledge, outlier detection always relies on a parameter, given by the end-user and standing for a "degree of outlyingness" above which records are considered as atypical. For instance, in [START_REF] Knorr | Algorithms for mining distance-based outliers in large datasets[END_REF], a distance-based outlier is an object such that a userdefined fraction of dataset objects have a distance of more than a user-defined minimum distance from that object. In [START_REF] Fan | A nonparametric outlier detection for effectively discovering top-n outliers from engineering data[END_REF], the authors propose a nonparametric clustering process and the detection of outliers requires a user defined value k corresponding to the top-k desired outliers.

In this paper we propose WOD (Wavelet-based Outlier Detection), a parameterless method intending to automatically extract outliers from a dataset. In contrast to previous work, our goal is to find the best division of a distribution and to automatically separate values into two sets corresponding to clusters on the one hand and outliers on the other hand. The tail of the distribution is found thanks to a wavelet technique and does not depend on any user threshold. Our method fits any distribution depending on any characteristic such as distances between objects [START_REF] Knorr | Algorithms for mining distance-based outliers in large datasets[END_REF], objects' density [START_REF] Breunig | Lof: identifying density-based local outliers[END_REF][START_REF] Papadimitriou | LOCI: fast outlier detection using the local correlation integral[END_REF] or clusters' size [START_REF] Jaing | Two-phase clustering process for outliers detection[END_REF][START_REF] Sequeira | Admit: anomaly-based data mining for intrusions[END_REF].

Our framework involves clustering-based outlier detection in data streams. Clusteringbased detection of outliers aims to find objects that do not follow the same model as the rest of the data depending on the clusters' size or tightness [START_REF] Jaing | Two-phase clustering process for outliers detection[END_REF][START_REF] Sequeira | Admit: anomaly-based data mining for intrusions[END_REF][START_REF] Fan | A nonparametric outlier detection for effectively discovering top-n outliers from engineering data[END_REF]. This framework will allow us to illustrate our proposal with one of the possible characteristics observed for building a distribution of objects (i.e. clusters' size). The choice of data streams is motivated by the specific constraints of this domain. In a data stream environment, data are generated at a very high rate and it is not possible to perform blocking operations. In this context, requesting a parameter such as k, for top-k outliers, or x, a percentage of small clusters, should be prohibited. First, because the user doesn't have enough time to try different values of these parameters for each period of analysis on the stream. Secondly, because a permanent value may be adapted to one period of the stream but it is highly likely to be wrong on the next periods (the data distribution will change, as well as the number or percentage of outliers). For these reasons, detecting outliers should not depend on any parameter and should be adaptive in order to keep the best accuracy all along the stream.

This paper is organized as follows. Section 2 gives an overview of existing works in outlier detection and Section 3 gives a formal definition of our problem.

The first step of our method aims to group the streaming data into clusters. We describe two clustering case studies in Section 4. Section 5 gives the details of WOD and its principle for separating outliers from clusters. Section 6 shows the advantages of WOD through a set of experiments on real Web usage data and Section 7 gives our conclusion.

RELATED WORKS

Outlier detection has been extensively studied these past years, since it has a wide range of applications, such as fraud detection for credit card [START_REF] Aleskerov | Cardwatch: A neural network based database mining system for credit card fraud detection[END_REF], cyber security [START_REF] Ertoz | Minds -minnesota intrusion detection system[END_REF] or safety of critical systems [START_REF] Fujimaki | An approach to spacecraft anomaly detection problem using kernel feature space[END_REF]. Those fields of application rely on methods to find patterns which deviate significantly from a well-defined notion of normality. The concept of outlyingness has been studied by statistics [START_REF] Markou | Novelty detection: a review -part 1: statistical approaches[END_REF][START_REF] Kwitt | Unsupervised anomaly detection in network traffic by means of robust pca[END_REF] where statistical approaches construct probability distribution models under which outliers are objects of low probability [START_REF] Billor | BACON: blocked adaptive computationally efficient outlier nominators[END_REF][START_REF] Lee | Information-theoretic measures for anomaly detection[END_REF]. Within the context of intrusion detection, data dimensionality is high. Therefore, to improve overall performances and accuracy, it has become necessary to develop data mining algorithms using the whole data distribution as well as most of data features [START_REF] Knorr | Algorithms for mining distance-based outliers in large datasets[END_REF][START_REF] Aggarwal | Outlier detection for high dimensional data[END_REF].

In this paper, we focus on clustering-based outlier detection algorithms [START_REF] Knorr | Algorithms for mining distance-based outliers in large datasets[END_REF][START_REF] Ramaswamy | Efficient algorithms for mining outliers from large data sets[END_REF][START_REF] Chimphlee | Unsupervised anomaly detection with unlabeled data using clustering[END_REF][START_REF] Fan | A nonparametric outlier detection for effectively discovering top-n outliers from engineering data[END_REF][START_REF] Jin | Mining top-n local outliers in large databases[END_REF][START_REF] Eskin | A geometric framework for unsupervised anomaly detection: Detecting intrusions in unlabeled data[END_REF][START_REF] He | Discovering cluster-based local outliers[END_REF][START_REF] Papadimitriou | LOCI: fast outlier detection using the local correlation integral[END_REF]. Such techniques rely on the assumption that normal points belong to large clusters while outliers either do not belong to any cluster [START_REF] Knorr | Algorithms for mining distance-based outliers in large datasets[END_REF][START_REF] Ramaswamy | Efficient algorithms for mining outliers from large data sets[END_REF] or form very small and tight clusters [START_REF] Jaing | Two-phase clustering process for outliers detection[END_REF][START_REF] Sequeira | Admit: anomaly-based data mining for intrusions[END_REF][START_REF] Fan | A nonparametric outlier detection for effectively discovering top-n outliers from engineering data[END_REF]. In other words, outlier detection consists in identifying among data those that are far from being significant clusters. Depending on the approach, the number of parameters required to run the algorithm can be high and will lead to different outliers. To avoid this, some works return a ranked list of potential outliers and limit the number of parameters to be specified [START_REF] Ramaswamy | Efficient algorithms for mining outliers from large data sets[END_REF][START_REF] Jin | Mining top-n local outliers in large databases[END_REF][START_REF] Fan | A nonparametric outlier detection for effectively discovering top-n outliers from engineering data[END_REF]. Let us note that [START_REF] Fan | A nonparametric outlier detection for effectively discovering top-n outliers from engineering data[END_REF] proposes to reduce or to avoid given parameter to the clustering algorithm, while maintaining a parameter regarding the outliers: n the number of required outliers. In this paper, we aim to detect outliers on the basis of clusters characteristics only. Among these characteristics, we have selected the clusters' size. A distribution of the clusters' size combined with our wavelet approach allows cutting the clusters set into two sub-sets, basically corresponding to "big" and "small" clusters. This method would also cut down this set with regard to other characteristics, such as clusters tightness or their number of neighbors (density) for instance. Applications of wavelet theory in data mining have been studied by [START_REF] Li | A survey on wavelet applications in data mining[END_REF] and the authors propose a survey on this topic.

In [START_REF] Yu | Findout: finding outliers in very large datasets[END_REF], the authors propose a technique for both clustering and outlier detection in static data, based on their previous work [START_REF] Sheikholeslami | Wavecluster: A multi-resolution clustering approach for very large spatial databases[END_REF]. [START_REF] Yu | Findout: finding outliers in very large datasets[END_REF] considers a dataset of d-dimensional points. Their goal is to apply a wavelet transform on the feature space. For this purpose, they first partition the original feature space into cells in order to obtain a quantized space (where a point o k belongs to a cell c i if o ki is comprised in the intervals of c ij for each dimension j). Then, a density function ρ(c i ) , based on the number of points contained in each cell, is specified. This density function will allow deciding whether a point is an outlier or not depending on a user threshold.

PROBLEM STATEMENT

Clustering is the problem of finding a partition of a data set so that similar objects are in the same part of the partition and different objects are in different parts. A data stream S = {S 1 , ..., S i , ..., S n } is a series of batches S i , read in increasing order of the indices i. Each batch contains a set of objects O = {o 1 , ..., o m }.

In this paper, we propose to process the stream of a Web site's usage, batch after batch. Let W be the site being analyzed. We propose to study two clustering problems associated to this data.

3.1. Clustering PHP requests. In this case, our goal is to extract clusters and detect atypical events among the requests performed to PHP scripts on W . Therefore, our objects will be the parameters given to the PHP scripts on W . We do not propose an intrusion detection framework, since atypical usage does not automatically correspond to malicious behaviours. Nevertheless, we expect our results to be useful for an automatic detection of atypicity in data streams. Section 4.2 describes our principle for clustering such data.

3.2. Clustering navigations. First, we need to define a navigation sequence as the series of URLs requested by a user. This definition will use the definition of itemsets from [START_REF] Agrawal | Mining Association Rules between Sets of Items in Large Databases[END_REF]. Definition 1. Let I = i 1 , i 2 , ..., i n be a set of items. Let X = i 1 , i 2 , ..., i k /k ≤ n and ∀j ∈ [1..k] i j ∈ I. X is called an itemset (or a k-itemset). Let T = t 1 , t 2 , ..., t m be a set of times, over which a linear order < T is defined, where t i < T t j means t i occurs before t j . A transaction T is a pair T = (tid, X) where tid is the transaction's identifier and X is the associated itemset. Associated to each item i in X we have a time-stamp t i which represents the valid time of occurrence of i in T . Definition 2. A navigation sequence is an ordered list of itemsets denoted by < n 1 , n 2 , . . . , n n >, where n j is an itemset and each item of n j stands for a URL.

In this case, a batch is made of k navigation sequences. Each navigation sequence n in the data stream is associated to a client c and n corresponds to the series of requests performed by c on the Web site. In section 4.1 we propose a method for clustering the navigation sequences of a data stream.

Atypicity detection.

For each case (PHP requests and navigations), our goal is to separate clusters in order to give the list of atypical events. Our principle (based on a multi-resolution analysis) for this parameterless detection is presented in Section 5.

CLUSTERING STREAMING USAGE DATA

Our method will process the data stream as batches of equal size. Let B 1 , B 2 , ...B n be the batches, where B n is the most recent batch of transactions. The principle of WOD will be to cluster the content of each batch b in [B 1 ..B n ] and to detect outliers according to the clusters' size. In this section, we describe an agglomerative clustering principle that has been adapted on two different kinds of data. As we will observe in the experiments, WOD is a self adjusting outlier detection method. Therefore, in order to assess that feature, we want to work on different datasets with different characteristics. The Web usage dataset has rather constant characteristics (size of clusters, content, distribution, etc.). On the other hand, the PHP dataset shows an important variation of usage in terms of distribution of the clusters.

4.1. Clustering Navigations. The general principle of our method can be described as follows: for each batch of transactions, our algorithm extracts the clusters of users (grouped by behavior) and then analyzes their navigations by means of a sequence alignment process. This allows us to obtain clusters of behaviors that represent the current usage of the Web site. In [START_REF] Marascu | Mining sequential patterns from data streams: a centroid approach[END_REF] the authors have proposed a method for mining sequential patterns in data streams which is based on sequence alignment. The clustering function of this paper catches and extends this principle. For each cluster c, the aligned sequence corresponding to the content of c gives a summary of c. After processing each batch, we are provided with patterns (the summaries or alignments obtained for the clusters) and their supports (the size of the clusters).

For each batch, the clustering algorithm is initialized with only one cluster which contains the first navigation (the first sequence of the batch). To each cluster s is associated a centroid ς c (the aligned sequence of the cluster) that summarizes the cluster. WOD will process the batch of sequences in only one scan. During this scan, the following operations are performed:

(1) For each navigation n in the batch, n is compared to each existing centroid. Let c be the cluster such that its centroid ς c is the most similar to n, then n is inserted into c. If no such cluster has been found, then a new cluster is created and n is inserted in this new cluster. The comparison of n (the navigation sequence) with a cluster c is explained in Subsection 4.1.2. (2) For each cluster c, the centroid ς c of c is computed incrementally. This step (detailed in Subsection 4.1.1) is very important, since each sequence s has to be compared to the centroid of each cluster. (3) At the end of the scan, the centroid of each cluster c will stand for the extracted knowledge since it can be considered as a summary of c.

4.1.1.

Centroid of a Cluster. The centroid ς c of cluster c is computed thanks to an alignment technique applied to c. When the first sequence is inserted into c, ς c is equal to this unique sequence.

The alignment of sequences is based on the definition of [START_REF] Kum | ApproxMAP: Approximate mining of consensus sequential patterns[END_REF] and leads to a weighted sequence represented as follows: SA =< I 1 : n 1 , I 2 : n 2 , ..., I r : n r >: m. In this representation, m stands for the total number of sequences involved in the alignment. I p (1 ≤ p ≤ r) is an itemset represented as (x i1 : m i1 , ...x it : m it ),where m it is the number of sequences containing the item x i at the p th position in the aligned sequences. Finally, n p is the number of occurrences of itemset I p in the alignment. Example 1 describes the alignment process of 4 sequences. Starting from two sequences, the alignment begins with

Step 1 :

S 1 : <(a,c) (e) ()> S 2 : <(a,d) (e) (h)> SA 12 :
(a:2, c:1, d:1):2 (e:2):2 (h:1):1

Step 2 : the insertion of empty items (at the beginning, at the end or inside the sequence) until both sequences contain the same number of itemsets.

Example 1. Let us consider the following sequences

: S 1 =< (a,c) (e) >, S 2 =< (a,d) (e) (h) >, S 3 =< (a,b) (e) (i,j) >, S 4 =< (b) (e) (h,i) >.
The steps leading to the alignment of these sequences are detailed in Figure 1. First, an empty itemset is inserted at the end of S 1 . Then S 1 and S 2 are aligned in order to provide SA 12 . The alignment process is then applied to SA 12 and S 3 . The alignment method goes on processing two sequences at each step.

At the end of this alignment process, the aligned sequence (SA 14 in figure 1) is a summary of the corresponding cluster. An approximate sequential pattern representing each cluster can be obtained by specifying k: the number of occurrences of an item in order for it to be displayed. For instance, for the sequence SA 14 from Figure 1 and k = 2 the filtered aligned sequence will be: <(a,b)(e)(h,i)> (corresponding to the items having a number of occurrences greater or equal to k).

The aligned sequence is incrementally updated, each time a sequence is added to its cluster. For that purpose, we maintain a matrix which contains the number of items for each sequence and a table representing the distances between sequences. This is illustrated in Figure 2. Our matrix (left) stores for each sequence the number of occurrences of each item in this sequence. For instance, s 1 is a sequence containing twice the item a. The table of distances stores the sum of similarities (similM atrix) between sequences. Let s 1i be the number of occurrences of item i in sequence s 1 and let m be the total number of items. similM atrix is computed thanks to the matrix in the following way :

similM atrix(s 1 , s 2 ) = m i=1 min(s 1i , s 2i ).
For instance, with two sequences s 1 and s 2 in the matrix of Figure 2, this sum is:

s 1a + s 2 b + s 2c = 1 + 0 + 1 = 2.
Sometimes, the alignment has to be refreshed and cannot be updated incrementally. Let us consider a sequence s n . First, s n is inserted in the matrix and its distance to the other Seq a b c s 1 2 0 1 s 2 1 0 1 . . . 2, s n is inserted after s 2 . Let r be the rank where s n is inserted (in our current example, r = 2) in c. After inserting s n , there are two possibilities:

Seq

(1) r > 0.5 × |c|. In this case, the alignment is updated incrementally and

ς c = alignment(ς c , s n ).
(2) r ≤ 0.5 × |c|. In this case, the centroid has to be refreshed and the alignment is computed again for all sequences of this cluster.

Comparing Sequences and Centroids.

Let s be the current sequence and C the set of all clusters. Our algorithm scans C and, for each cluster c ∈ C, performs a comparison between s and ς c (the centroid of c, which is an aligned sequence). This comparison is based on the longest common sub-sequence (LCS) between s and ς c (see Definition 3). The length of the sequence is also taken into account since it has to be no more than 120% and no less than 80% of the original sequence (i.e. the first sequence inserted into c).

Definition 3. Let s 1 and s 2 be two sequences. Let LCS(s 1 , s 2 ) be the length of the longest common subsequences between s 1 and s 2 . The similarity sim(s 1 , s 2 ) between s 1 and s 2 is defined as follows:

sim(s 1 , s 2 ) = 1 - 2 × LCS(s 1 , s 2 ) |s 1 | + |s 2 |
The dissimilarity d(s 1 , s 2 ) between s 1 and s 2 is defined as follows:

d(s 1 , s 2 ) = 1 -sim(s 1 , s 2 )
Let t be the length of the first sequence inserted into c, s is inserted into c if the three following conditions hold:

• ∀d ∈ C/d = c, sim(s, ς d ) ≤ sim(s, ς c ); • 0.8 × t ≤ |s| ≤ 1.2 × t; • sim(s, ς c ) ≥ 0.7.
The first condition ensures that s will be inserted into a cluster having the most similar centroid to s. The second condition ensures that after inserting s, c will contain sequences of similar length and that the clusters' average length will not vary too much. Finally, the third condition ensures that ς c and s are similar (with a degree of 70%). If there is no cluster such that these conditions hold, then a new cluster is created and s is inserted into this new cluster.

Algorithm Data Preparation

Input: Output:

(1) Foreach request, parse the parameters and build the corresponding objects.

(2) Build M , the similarity matrix between each pair of objects ;

(3) ∀p ∈ M, N eighbors p ← sorted list of neighbors for p (the first object in the list of p is the closest to p). (4) DensityList ← sorted list of objects by density ; End algorithm Data Preparation FIGURE 3. Algorithm Data Preparation 4.2. Clustering PHP requests. In this section we present the preprocessing principle we use to build objects from the PHP requests, the similarity we propose between them and our clustering algorithm.

Preprocessing. We focus on PHP scripts since there are still potential malicious usage of these scripts and an algorithm intending to extract atypical usage behaviours might help identifying attacks. For each batch of the usage data stream, our preprocessing step firstly filters the data corresponding to PHP scripts, with parameters. Secondly, for each parameter, we build an object corresponding to the keyword given by the user. Let us consider, for instance, the following request: staff.php?FName=John&LName=Doe. The corresponding objects are o 1 =John and o 2 =Doe. Therefore, at the end of this preprocessing step, we are provided with the set of all the parameters extracted from the batch. Similarity Between Objects. We consider each object as a sequence of characters. Our comparison of two parameters is then based on the dissimilarity between two words, based on the LCS as described in definition 3.

Example 2.

Let us consider two parameters p 1 =intrusion and p 2 =induction. The LCS between p 1 and p 2 is L=inuion. L has length 6 and the dissimilarity between p 1 and p 2 is d = 1 -2×L |p1|+|p2| = 33.33%. Which also means a similarity of 66.66% between both parameters.

The goal of this paper is to focus on our new outlier detection paradigm (described in Section 5). Therefore, the clustering algorithm we propose has to be well adapted to data streams and PHP requests (though it is not the center of our contribution). Actually, we could have used a k-means algorithms as well as hierachical or neural methods, for instance. The main interest of this clustering step is to show the impact of a distribution variation on the outlier detection. Such a variation may occur with any clustering algorithm and any distance or similarity measure. This will be discussed in the experiments. Algorithm Clustering (Figure 4) is based on an agglomerative principle. The principle of our clustering algorithm is to increase the volume of clusters by adding candidate objects, until the Maximum Dissimilarity (MD) is broken (i.e. there is one object o i in the cluster such that the dissimilarity between o i and the candidate object o c is greater than MD). Our preprocessing step is illustrated by Algorithm Data Preparation (Figure 3).

PARAMETERLESS OUTLIER DETECTION

Most previous work in outlier detection requires a parameter [START_REF] Jin | Mining top-n local outliers in large databases[END_REF][START_REF] Zhong | Clustering-based network intrusion detection[END_REF][START_REF] Portnoy | Intrusion detection with unlabeled data using clustering[END_REF][START_REF] Oldmeadow | Adaptive clustering for network intrusion detection[END_REF], such as a percent of small clusters that should be considered as outliers or the top-n outliers. Generally, their key idea is to sort the clusters by size and/or tightness. We consider that our clusters will be as tight as possible, according to our clustering algorithm, and we aim to extract outliers by sorting the clusters by size. The problem is to separate "big" and "small" clusters without any apriori knowledge about what is big or small. Our solution is based on an analysis of cluster distribution, once they are sorted by size. One possible distribution shape is illustrated in figure 5 (screenshot made with our real data). The key idea of WOD is to use a wavelet transform to cut down such a distribution. With a prior knowledge on the number of plateaux (we want two plateaux, the first one standing for small groups, or outliers, and the second one standing for big groups, or clusters) we can cut the distribution in a very effective manner. In figure 5, the y axis stands for the size of the clusters, whereas their index in the sorted list is represented on x, and the two plateaux allow separating small and big clusters. Actually, each cluster having size lower than (or equal to) the first plateau will be considered as an outlier.

Algorithm

FIGURE 5. Detection of outliers by means of Haar Wavelets

The wavelet transform is a tool that cuts up data or functions or operators into different frequency components, and then studies each component with a resolution matched to its scale [START_REF] Daubechies | Ten lectures on wavelets[END_REF][START_REF] Chui | An introduction to wavelets[END_REF]. In other words, wavelet theory represents series of values by breaking them down into many interrelated component pieces; when the pieces are scaled and translated wavelets, this breaking down process is termed wavelet decomposition or wavelet transform. Wavelet reconstructions or inverse wavelet transforms involve putting the wavelet pieces back together to retrieve the original object [START_REF] Young | Wavelet Theory and Its Applications[END_REF]. Mathematically, the continuous wavelet transform is defined by:

T wav f (a, b) = 1 √ a +∞ -∞ f (x)ψ * ( x -b a )dx
where z * denotes the complex conjugate of z, ψ * (x) is the analyzing wavelet, a (> 0) is the scale parameter and b is the translation parameter. This transform is a linear transformation and it is co-variant under translations and dilations. This expression can be equally interpreted as a signal projection on a function family analyzing ψ a,b constructed from a mother function in accordance with the following equation:

ψ a,b (t) = 1 √ a ψ( t-b a )
. Wavelets are a family of basis functions that are localized in time and frequency and are obtained by translations and dilations from a single function ψ(t), called the mother wavelet. For some very special choices of a, b, and ψ, ψ a,b is an orthonormal basis for L 2 (R). Any signal can be decomposed by projecting it on the corresponding wavelet basis function. To understand the mechanism of wavelet transform, we must understand the multiresolution analysis (MRA). A multiresolution analysis of the space L 2 (R) consists of a sequence of nested subspaces such as:

...

⊂ V 2 ⊂ V 1 ⊂ V 0 ⊂ V -1 ... ⊂ V j+1 ⊂ V j ... j∈Z V j = L 2 (R) j∈Z V j = {0} ∀j ∈ Z if f (x) ∈ V j ⇐⇒ f (2 -1 x) ∈ V j+1 ( or f (2 j x) ∈ V 0 ) ∀k ∈ Z if f (x) ∈ V 0 ⇐⇒ f (x -k) ∈ V 0
There is a function ϕ(x) ∈ L 2 (R), called scaling function, which by dilation and translation generates an orthonormal basis of V j . Basis functions are constructed according to the following relation :

ϕ j,n (x) = 2 -j 2 ϕ(2 -j x-n), n ∈ Z, and the basis is orthonormated if +∞ -∞ ϕ(x)ϕ * (x+ n)dx = δ(n), n ∈ Z.
For each V j , its orthogonal complement W j in V j-1 can be defined as follows:

V j-1 = V j ⊕ W j and L 2 (R) = j∈Z W j . As W j is orthogonal to V j-1 , then W j-1 is orthogonal to W j , so ∀j, k = j then W j ⊥ W k .
There is a function ψ(x) ∈ R, called wavelet, which by dilations and translations generates an orthonormal basis of W j , and so of L 2 (R). The basis functions are constructed as follows:

ψ j,n (x) = 2 -j 2 ψ(2 -j x -n), n ∈ Z Therefore, L 2 (R)
is decomposed as a direct sum of the spaces W j which becomes an orthogonal sum [START_REF] Chui | An introduction to wavelets[END_REF], i.e. L 2 (R) = j∈Z W j . To summarize the wavelet decomposition: given a f n function in V n , f n is decomposed into two parts, one part in V n-1 and the other in W n-1 . At next step, the part in V n-1 continues to be decomposed into two parts, one part in V n-2 and the other in W n-2 and so on. Figure 6 gives an illustration of the multiresolution analysis.

FIGURE 6. Multiresolution Analysis Principle

A direct application of multiresolution analysis is the fast discrete wavelet transform algorithm. The idea is to iteratively smooth data and keep the details all along the way. More formal proofs about wavelets can be found in [START_REF] Daubechies | Ten lectures on wavelets[END_REF][START_REF] Young | Wavelet Theory and Its Applications[END_REF]. The wavelet transform provides a tool for time-frequency localization and are generally used to summarize data and to capture the trend in numerical functions. In practice, the majority of wavelets coefficients are small or insignificant, so to capture the trend only a few significant coefficients are needed. We use the Haar wavelets to illustrate our outlier detection method. Let Then, we keep only the two most significant coefficients and we make the others zero. In our series of coefficients ([7, -4.75, -1.25, -2.25, 0, -1.5, -0.5, -1]) the most two significant ones are 7 and -4.75, meaning that the series becomes [7, -4.75, 0, 0, 0, 0, 0, 0]. In the following step, the inverse operation is calculated and we obtain an approximation of the original data [2. 25, 2.25, 2.25, 2.25, 11.75, 11.75, 11.75, 11.75]. This gives us two plateaux corresponding to values {1, 1, 2, 5} and {9, 10, 13, 15}. The set of outliers contains all the clusters having size smaller than the first plateau(e.g. 2.25). In our example, o = {1, 1, 2} is the set of outliers.

More generally, advantages of this method, for our problem, are illustrated in figures 8 and 9. Depending on the distribution, wavelets will give different indexes (where to cut). For instance, with few clusters having the maximum size (see graph with solid lines from figure 8 ), wavelets will cut the distribution in the middle. On the other hand, with a large number of such large clusters (see graph with dashed lines from figure 8), wavelets will accordingly increase the number of clusters in the little plateau (taking into account the large number of big clusters). Furthermore, in our usage data at INRIA, there is a variation between night and day in the usage of PHP scripts. This variation results into two main shapes. Figure 9 gives an illustration of two different distributions, similar to the ones we found out in our experiments. Let us consider the 10% filter on this distribution, which aims to isolate outliers corresponding to 10% of the global shape. If one uses the 10% percent filter in order to detect outliers, one will obtain a relevant outlier detection for the first distribution (corresponding to usage of scripts at 1 am). However, with the second distribution (calculated from the usages at 5 pm), this filter will give a very high value and return clusters that should not be considered as outliers. On the other hand, our wavelet based filter will adjust to the distribution variation and the threshold for outlier detection will only slightly increase, taking into account the new distribution shape.

FIGURE 9. A Distribution Varying With Time

Applying the wavelet transform on the series allows us to obtain a good data compression and, meanwhile, according to different trends, a good separation. Knowing that outliers are infrequent objects, they will always be grouped into small clusters. WOD's principle of separating outliers from clusters is based on theorem 1. Theorem 1. Let F be the set of features used to build the distribution D on the clustering result. Let P1 and P2 be the two plateaux obtained after selecting the most two significant coefficients of the wavelet transform on D. The optimal separation into two groups according to F and regarding the minimisation of the sum squared error, is given by P1 and P2.

Proof In an orthonormal base, it has been shown that keeping the largest k wavelet coefficients gives the best k-term Haar approximation to the original signal, in terms of minimizing the sum squared error for a given k [START_REF] Stollnitz | Wavelets for computer graphics: A primer, part 1[END_REF]. For this propose, let us consider the original signal f (x) and the basis functions u 1 (x), ...u m (x). The signal can thus be represented depending on the basis functions as :

f (x) = m i=1 c i u i (x)
The goal is to find an approximating function with fewer coefficients. Let σ be a permutation of 1, ..., m and f ′ the approximating function using only the first m ′ elements of σ, with m ′ < m.

f ′ (x) = m ′ i=1 c σ(i) u σ(i) (x)
The square of L 2 error of this approximation is:

||f (x) -f ′ (x)| | 2 2 =< f (x) -f ′ (x)|f (x) -f ′ (x) > = m i=m ′ +1 c σ(i) u σ(i) | m j=m ′ +1 c σ(j) u σ(j) = m i=m ′ +1 m j=m ′ +1 c σ(i) c σ(j) < u σ(i) |u σ(j) > = m i=m ′ +1 (c σ(i) ) 2
Due to the basis orthonormality, < u i , u j >= δ, so, for any m ′ < m, to minimize this error the best choice for σ is the increasing permutation (or the permutation that contains the elements ordered in increasing order).

Therefore, for m ′ = 2 we obtain the best 2-term Haar approximation to the original signal.

Based on theorem 1, we select the clusters having size smaller than the first plateau. These clusters can be considered as outliers without any parameter given by the end-user.

EXPERIMENTS

The goal of our experiments is to show the advantages of our parameterless outlier detection in a streaming environment. In such an environment, choosing a good level of outlyingness is highly difficult given the short time available to take a decision. In this context, an outlier detection method which does not depend on a parameter such as k, for the top-k outliers, or a percentage p of small clusters, should be much appreciated. On the other hand, such a parameterless outlier detection method also has to guarantee good results. This method should be able to provide the end-user with an accurate separation into small and big clusters. It should also be able to fit any kind distribution shape (exponential, logarithmic, linear, etc.). Finally, it should also be able to automatically adjust to the number of clusters and to their size from one batch to the other. Our claim is that WOD matches all these requirements and we illustrate these features in this section . For these experiments we used real data, coming from the Web Log usage of INRIA Sophia-Antipolis from January 2006 to April 2007. The original files have a total size of 18 Gb. FIGURE 10. size of outliers with a top-k filter and number of outliers with a % filter on dataset navigations 6.1. Navigations. The access log files of this experiments correspond to a total of 11 millions navigations that have been split into batches of 8500 requests each (in average). In this section, we report some results on the first 15 batches, since they are very representative of the global results.

Figure 10 shows the behaviour of two filters on the first 15 batches. Foreach batch, the number of objects (navigation sequences) and clusters is given in Table 1. The first filter (left part of Figure 10) shows the size of clusters selected by a top-k filter. The principle of this filter is to select only the first k clusters after sorting them by size. An obvious disadvantage of this filter is to select either too much or not enough clusters. Let us consider, for instance, batch 13 in this figure. With k = 50 the maximum outliers size is 12, whereas with k = 90 this size is 265 (which is the maximum size of a cluster in this batch since it contains only 87 clusters). Another disadvantage is to arbitrary select or ignore clusters with equal size. For instance, with s = {1, 1, 2, 2, 3, 5, 10} a series of sizes and k = 3, the top-k filter will select the 3 first clusters having sizes: 1, 1 and 2, but will ignore the 4 th cluster having size 2.

We also have implemented a filter based on p, a percentage of clusters, to select outliers. The number of outliers selected by this filter with different values of p (i.e. from 0.01 to 0.09) are given in Figure 10 In our experiments, this filter is generally better than a top-k filter. Actually, we can notice homogeneous results from Figure 10. For instance, with batch 13 we can see a number of outliers ranging from 24 (1 %) to 70 (9 %). . Unfortunately, a value of 80 for this filter cannot be considered as a reference. For instance, in batch number 11, we notice a cluster having size 127 is considered an outlier. The maximum size of a cluster in batch 11 is 172 and there are 82 clusters. This result is thus not acceptable and shows that top-k is unable to adjust to changes in the distribution of cluster sizes. On the other hand, thanks to its wavelet feature, WOD is able to automatically adjust and will select 8 as a maximum size of an outlier.

On the right graph of Figure 11, we focus on three percentage filters with 1%, 4%, 9% and we compare them to WOD. For instance, with batch 11, we know that WOD labels clusters having size less than or equal to 8 as outliers. That filtering gives a total of 38 clusters (where filter 4 % gives 45 outliers). These clusters represent a total of 184 objects in a batch which contains 2294 objects. Our observation is that WOD and 4% would give similar results. However, we discuss the advantages of WOD on the percentage filter in subsection 6.3.

PHP parameters.

For these experiments, the log files have been split into batches of 10,000 php requests. We focus on 16 batches, since they are representative of the global results and they illustrate the variation of distribution. The first 8 batches have been selected among PHP request occuring between 1 and 2 am, and the 8 former have been selected among requests occuring between 3 and 4 pm. Figure 12 shows the behaviour of filters top-k and p% on those 16 batches. First surface in Figure 12 (left) shows the size of clusters selected by a top-k filter. Let us consider, for instance, batch 13 in Figure 12. With k = 50 the maximum outliers size is 4, whereas with k = 90 this size is 67 (which is the maximum size of a cluster in this batch, which contains only 84 clusters).

Regarding the percentage filter, the number of outliers selected by this filter with different values of p (i.e. from 0.01 to 0.09) is given in figure 12 (right surface). Once again, we can notice homogeneous results for this filter in Figure 12. For instance, with batch 13 we can see a number of outliers ranging from 44 (1 %) to 78 (9 %), which corresponds to the results of top-40 to top-70. FIGURE 12. size of outliers with a top-k filter and number of outliers with a p% filter on dataset PHP Figure 13 gives a comparison of WOD (applied to the same data) with top-k and percentage filtering. In the left part of Figure 13, we compare WOD with a top-10 and a top-70 filter. For the first 8 batches, top-10 and WOD give the best result. Unfortunately, for batches 9 to 16, top-10 returns too few outliers (having maximum size 1). Therefore, this filter cannot be used for the whole stream. The best top-k results for batches 9 to 16 are given by a top-70. Unfortunately, its results for batches 1 to 8 are bad (values are too high, with outlier having size up to 28). Therefore, no value of k in this filter can be considered as a reference. The end-user would have to modify the value of k from one batch to another. This result is thus not acceptable and shows that top-k is unable to adjust to changes in the distribution of cluster sizes. On the other hand, thanks to its wavelet feature, WOD is able to automatically adjust and will always select a correct maximum size to detect atypical events.

In the right part of Figure 13, we focus on two percentage filters (i.e. 1% and 5%) and we compare them to WOD. Our observation is that WOD and 1% would give similar results. For instance, with batch 7, we know that WOD labels clusters having size less than or equal to 3 as outliers. That filtering gives a total of 9 clusters (where filter 1 % gives 8 outliers). We also can observe that most of the values given by filter 1 % on the first 8 batches are low. Filter 5 % gives better values for the first 8 batches (very similar to WOD) but it has bad results on the next 8 batches (up to 138 outliers). This is due to the variation of the distribution, as illustrated by Figure 9. 6.3. Discussion. These experiments illustrate the advantages of WOD over the traditional filters:

(1) WOD does not require any parameter tuning. It adjusts automatically, whatever the distribution shape and the number of clusters. In contrast, the end-user will have to try several percentage values before finding the good range (i.e. between FIGURE 13. Comparison with WOD for top-k and p% 3% and 9% the percentage filter gives good outliers for the first batches). Furthermore, the outlier detection provided by WOD will not degrade with a variation of distribution shape over time. In our case, the distribution is usually exponential.

Let us consider a change of usage, or a change of clustering method, resulting in a variation of the distribution shape. That new shape could be logarithmic, for instance, such as the distribution illustrated in Figure 8. Then, the percentage filter would have to be manually modified to fit that new distribution, whereas WOD would keep giving the good set of outliers without manual settings.

CONCLUSION

In this paper we have presented WOD, an outlier detection method that does not require any manual tuning. Our principle is first based on a distribution of clusters according to some characteristics such as their size, tightness, density or any other characteristic. Thanks to its wavelet feature, WOD is able to cut down this distribution into two sets, corresponding to clusters and outliers. The advantages of WOD are i) automatic adjustment to distribution shape variations and ii) relevant and accurate detection of outliers with very natural results. Our experiments, performed on real data, confirm this separation feature of WOD compared to well-known outlier detection principles such as the top-k outliers or the percentage filter.

3 FIGURE 1 .

 31 FIGURE 1. Different steps of the alignment method with sequences from example 1

  Clustering Input: U , the objects and M D, the Maximum Dissimilarity. Output: C, the set of as large clusters as possible, respecting M D. (1) i ← 0 ; C ← ∅ ; (2) p ← next unclassified object in DensityList ; (3) i + + ; c i ← p ; (4) C ← C + c i ; (5) q ← next unclassified object in N eighbors p ; (6) ∀o ∈ c i If d(o, q) > M D then return to step 2 ; (7) add q to c i ; (8) return to step 5 ; (9) If unclassified objects remain then return to step 2 ; (10) return C ; End algorithm Clustering

FIGURE 4 .

 4 FIGURE 4. Algorithm Clustering

FIGURE 8 .

 8 FIGURE 8. Automatic adjustment to the clustering results

  (right). The principle is to consider p ∈ [0..1], a percentage given by the end-user, d = maxV al -minV al the range of cluster sizes and y = (p × d) + minV al. Then, the filter aims to select only clusters having size s, such that s ≤ y. For instance, with s = {1, 3, 10, 11, 15, 20, 55, 100} a series of sizes and x = 0.1 we have d = 100 -1 = 99, y = 1 + (0.1 × 99) = 10 and the set of outliers will be o = {1, 3, 10}.

Figure 11

 11 Figure11gives a comparison of WOD (applied to the same data) with top-k and percentage filtering. The left graph reports the results when comparing WOD with a top-10 and a top-80 filter. Filter top-80 gives good results for approximately 50% of the batches, whereas filter-10 always gives very low values (size 1 or 2). Unfortunately, a value of 80 for this filter cannot be considered as a reference. For instance, in batch number 11, we notice a cluster having size 127 is considered an outlier. The maximum size of a cluster in batch 11 is 172 and there are 82 clusters. This result is thus not acceptable and shows that top-k is unable to adjust to changes in the distribution of cluster sizes. On the other hand, thanks to its wavelet feature, WOD is able to automatically adjust and will select 8 as a maximum size of an outlier.On the right graph of Figure11, we focus on three percentage filters with 1%, 4%, 9% and we compare them to WOD. For instance, with batch 11, we know that WOD labels clusters having size less than or equal to 8 as outliers. That filtering gives a total of 38 clusters (where filter 4 % gives 45 outliers). These clusters represent a total of 184 objects in a batch which contains 2294 objects. Our observation is that WOD and 4% would give similar results. However, we discuss the advantages of WOD on the percentage filter in subsection 6.3.

( 2 )

 2 WOD gives a natural separation between small and big values (according to theorem 1). Let us consider our previous illustration of a distribution s = {1, 3, 10, 11, 15, 20, 55, 100}. We know that on this distribution a 10% filter would give the following set of outliers : o = {1, 3, 10}. However, why not including 11 into o? Actually, 10 and 11 are very close values. On the other hand, with WOD we have o = {1, 3}, which is obviously a natural and realistic result.

  , s i )). s n is then inserted in the distance table, with respect to the decreasing order of distances values. For instance, in Figure

		n i=1 similM atrix(s, s i )
		s 1	16
		s 2	14
		s n	13
		s 3	11
		. . .
		s n-1	1
	FIGURE 2. Distances between sequences
	sequences is computed (	n i=1 similM atrix(s n

  us consider the following series of values: [1, 1, 2, 5, 9, 10, 13, 15]. Its Haar wavelet transform is illustrated by table 7.

	Level Approximations	Coefficients
	8	1, 1, 2, 5, 9, 10, 13, 15
	4	1, 3.5, 9.5, 14	0, -1.5, -0.5, -1
	2	2.25, 11.75	-1.25, -2.25
	1	7	-4.75
	FIGURE 7. Wavelet transform of [1, 1, 2, 5, 9, 10, 13, 15]

TABLE 1 .

 1 Batches, objects and clusters FIGURE 11. Comparing WOD with top-k and % filters on dataset navigations

	Batch	1	2	3	4	5	6	7	8
	Number of Objects 1391 2076 2234 1635 2174 1672 1955 2009
	Number of Clusters 154	92	118	98	128	116	119	111
	Batch	9	10	11	12	13	14	15
	Number of Objects 2455 2182 2857 2498 2294 2698 2090
	Number of Clusters 119	108	82	94	87	106	122