Thierry Petit
email: thierry.petit@mines-nantes.fr

Jean-Charles R Égin
email: jean-charles.regin@unice.fr

WSPC/INSTRUCTION FILE ictai2010 THE ORDERED DISTRIBUTE CONSTRAINT

In this paper we introduce a new cardinality constraint: Ordered Distribute. Given a set of variables, this constraint limits for each value v the number of times v or any value greater than v is taken. It extends the global cardinality constraint, that constrains only the number of times a value v is taken by a set of variables and does not consider at the same time the occurrences of all the values greater than v. We design an algorithm for achieving generalized arc-consistency on Ordered Distribute, with a time complexity linear in the sum of the number of variables and the number of values in the union of their domains. In addition, we give some experiments showing the advantage of this new constraint for problems where values represent levels whose overrunning has to be under control. Finally, we present three extensions of our constraint that can be particularly useful in practice.

Introduction

Constraint programming is a simple and generic paradigm, which allows to represent and solve hard problems. Problems are defined by variables that take their values into finite domains, and which are subject to constraints defining the allowed combinations of values for some subsets of variables.

Encoding problems with constraint programming often requires to define cost variables involved in an objective criteria. In this context, industrial problems generally involve some constraints on costs dedicated to the characterization of the solutions acceptable in practice. These particular constraints are independent from the objective criteria.

Representing these constraints, as well as solving efficiently the related problems, form an important issue. Recent works address this issue using global constraints. A global constraint is defined on a large number of variables, and it is associated with a filtering algorithm that removes the values which cannot satisfy the constraint. The Spread and Deviation constraints [START_REF] Pesant | Spread: A balancing constraint based on statistics[END_REF][START_REF] Schaus | The deviation constraint[END_REF] enforce the balancing of values within a set of variables. Balance is often important in assignment problems, for instance the daily assignment of newborn infant patient to nurses [START_REF] Mullinax | Assigning patients to nurses in neonatal intensive care[END_REF][START_REF] Schaus | Scalable load balancing in nurse to patient assignment problems[END_REF] .

In some applications, it is required to define for some subsets of variables several levels of values, and to limit for each level the maximum number of values over this level. Existing balancing constraints such as Spread or Deviation cannot be used because they globally limit the sum of the taken values. Furthermore, since often we manipulate values representing costs, a high value v is generally at least as undesirable as any of the values which are less than v. In this case, classical cardinality constraints such as Gcc [START_REF] Régin | Generalized arc consistency for global cardinality constraint[END_REF] are not well-suited because they limit the number of occurrences of each value taken separately.

In order to solve this issue, we introduce OrderedDistribute, a new constraint that fills in this gap by limiting, for each value v, the number of occurrences of v and all the values greater than v within a set of variables. Then, we describe an efficient filtering algorithm establishing arc consistency associated with it.

The paper is organized as follows. Section 2 gives the background useful to understand our contribution. Some motivations of our work are presented in Section 3. Section 4 discusses the reformulation of OrderedDistribute with existing arithmetic and cardinality constraints. In section 5, we propose a filtering algorithm establishing generalized arc-consistency in a linear time complexity. We illustrate in Section 6 the practical interest of our approach by some experiments. At last, we discuss the extension of OrderedDistribute with range variables representing the cardinalities as well as the aggregation of several instances of OrderedDistribute, and we conclude.

Background

A constraint network N is defined as a set of n variables X = {x 1 , . . . , x n }, a set of current domains D = {D(x 1 ), . . . , D(x n )} where D(x i ) is the finite set of possible values for variable x i , and a set C of constraints between variables. An assignment of values to variables in X is denoted by A(X), and for each x ∈ X, A(X, x) is the value of x in A(X). A(X) is valid iff ∀x i ∈ X, A(X, x i ) ∈ D(x i ). A constraint C(X) specifies the allowed combinations of values for a set of variables X, that is, it defines a subset R C (D) of the Cartesian product Π xi∈X D(x i ) of the domains of variables in X. A feasible assignment of C(X) is an assignment which is in R C (D). If A(X) is a feasible assignment of C(X) then we say that A(X) satisfies C(X). For convenience, given a value v and an assignment A(X), we denote by #(v, A(X)) the number of time v appears in A(X) and by #(≥ v, A(X)) the number of values w ≥ v that appear in A(X).

Let C be a constraint over the variables X. A support on C is an assignment which satisfies

C. A domain D(x) of x ∈ X is arc-consistent w.r.t. C iff ∀v ∈ D(x), v belongs to a valid support on C. C is (generalized) arc-consistent (GAC) iff ∀x i ∈ X, D(x i ) is arc-consistent w.r.t. C.

Motivations and Definition

To illustrate the need of the OrderedDistribute constraint, we present an example of cumulative scheduling where costs (i.e., values) are used to express over-loads of capacity and where constraints related to different levels of over-loads are defined.

Scheduling problems consist in ordering some activities. In cumulative scheduling, each activity requires for its execution the availability of a certain amount of renewable resource. In constraint programming, activities are represented by variables, and cumulative problems can be encoded thanks to a dedicated constraint,

Cumulative 1 .
Let A be a set of n non-preemptive activities (i.e. activities that cannot be interrupted). For each a ∈ A,

• start[a] is the variable representing its starting point in time.

• dur[a] is the variable representing its duration.

• res[a] (height of a) is the variable representing the discrete amount of resource consumed by activity a.

We consider cumulative problems where each activity consumes a resource.

It enforces the following constraints:

a In 5 , each variable cost[t] can correspond to an interval of consecutive points in time, not only one point in time. Without loss of generality and for sake of simplicity, we use a definition where the length of intervals is 1.

C1 : For each activity

a ∈ A, start[a] + dur[a] = end[a]. C2 : At each point in time t, h[t] ≤ relax capa. C3 : For each point in time t, cost[t] = max(0, h[t] -capa) C4 : obj = t∈{0,...,m-1} cost[t]
Over-loads are accepted in the SoftCumulativeSum constraint and the objective variable (obj) represents the sum of the overloads. Figure 1 contains an example of this constraint. However, for some problems, constraining the sum of the over-loads is not enough. Some additional constraints w.r.t. these over-loads should be satisfied. A frequent requirement is to distribute fairly over-loads within a long time period, while limiting the number of big over-loads for each short period of time.

For instance, assume that the resource is the number of employees in a team. Each day (8 hours), each person contributes to some activities. An over-load will entail, in practice, either that extra-employees are hired, or that some activities are performed by a number of employees less than the number which was initially planed (for instance, some employees may accept to do homework). Typically, small overloads (cost[t] = 1) correspond to the second case, while big ones (e.g., cost[t] > 3) require to hire extra-employees. Then, the number of each type of over-loads has to be limited, and these types are related one another. This means that the number of times a variable cost is greater than a given value has to be limited. Thus, we need to express that at most k variables can take a value v or greater. This is the purpose of the new constraint OrderedDistribute. We define it formally:

Definition 3.3. Let
• X be a set of variables • T be an array of increasing values that can be assigned to variables in X, with |T | ≥ 2.

• I max be an array of maximum possible number of occurrences of values in T , where I max [i] corresponding to the value T [i], and such that ∀i ∈ {1, . . . , |T | -1},

I max [i -1] ≥ I max [i].
An assignment A(X) satisfies the constraint

OrderedDistribute(X, T , I max ) iff (1) For each i ∈ {0, . . . , |T | -1}, the number of values v in A(X) s.t. v ≥ T [i] is at most equal to I max [i]. (2)
The number of times value T [0] appears in A(X) is at least equals to |X| -I max [1].

Observe that OrderedDistribute also implicitly affects minimum occurrences of values: given an index i < |T | -1, the number of times a value v ≤ T

[i] appears in A(x) is at least equal to |X| -I max [i + 1].
Example 3.1. We consider a human resource cumulative problem with 5 days of 8 hours, and a team of 8 employees. The following constraints are imposed w.r.t. over-loads.

(1) At most 5 over-loaded hours by day.

(2) At most 3 over-loads greater than or equal to 2.

(3) At most 1 over-load equal to 4. (no over-load should exceed 4 employees).

Here is a fully detailed instance. We consider 40 activities with the following durations: [ Observe that an over-load of 4 is at least as undesirable as an over-load of 3, an over-load of 3 is at least as undesirable as an over-load of 2, and so on.

Figure 2 shows the over-loads in each day, in the cumulative profile corresponding to that instance. The sum of over-loads over the whole month is 48.

We can easily encode this problem by using the OrderedDistribute constraint defined with T = [0, 1, 2, 3, 4] and I max = [8, 5, 3, 3, 1] where T measures the overloads and I max limits the number of occurrences for each day. For instance, T [2] = 2 and I max [2] = 3 means that we can have at most 3 times an over-load of size 2 or more for each day. The following model, written in pseudo-code, represents this problem.

// ds are the durations, hs the heights // capa and relax capa the capacities IntDomainVar[] start, costVar; IntDomainVar obj; SoftCumulativeSum(start, costVar, obj, ds, hs, capa, relax capa); // additionnal constraints

T = [0, 1, 2, 3, 4]; Imax = [8, 5, 3, 3, 1];
for each day in a partition of costVar[]:

OrderedDistribute(day, T, Imax) // objective minimize(obj);

Here is a solution of the problem (each range [d i , e i [ indicates the points in time where activity a i starts and ends in the schedule):

More generally, OrderedDistribute may be useful in practice in several classes of problems:

• In bin-packing problems when objects have to be packed into containers. For instance, a fair distribution based on some degrees indicating frailty of the objects allows to limits the negative consequences (in terms of financial costs) of damaged containers. • In assignment problems when teams have to be balanced with respect to the hierarchical skills of the members. • In over-constrained problems, in which costs represent degrees of violation of constraints. b These costs are often strongly ordered. (Example 3.1 belongs to b A problem is over-constrained when it has no solution. To find compromising solutions that will this class.)

Reformulation of OrderedDistribute

Reformulating OrderedDistribute with existing cardinality constraints is not straightforward because limiting the maximum number of occurrences of a value v does not constrain the occurrences of all the values which are greater than v. It is necessary to augment such existing cardinality constraints with additional constraints like arithmetic ones.

The most famous cardinality constraint is the global cardinality constraint or

Gcc. It is defined as follows:

Definition 4.1. Let X be a set of variables, T be an array of values, and I be the array of allowed integer ranges for each value of T . An assignment A(X) satisfies the constraint Gcc(X, T , I) iff any value v = T [i] appears in A(X) a number of times which belongs to

I[i], i.e. #(T [i], A(X)) ∈ I[i], i = 0, . . . , |X| -1.
Generalized Arc Consistency (GAC, see Section 2) can be established efficiently on Gcc [START_REF] Régin | Generalized arc consistency for global cardinality constraint[END_REF][START_REF] Quimper | Improved algorithms for the global cardinality constraint[END_REF] .

When I are defined by boundaries of range variables (the card variables), the Gcc constraint becomes the cardVar-Gcc constraint [START_REF] Régin | The cardinality matrix constraint[END_REF] . A range variable is a variable which is represented by the minimum and the maximum values in its domain. Thus, the parameter I is replaced by the set of range variables Card, so as the signature is cardVar-Gcc(X, T , Card). Filtering algorithms for cardVar-Gcc can be found in [START_REF] Régin | The cardinality matrix constraint[END_REF][START_REF] Quimper | Improved algorithms for the global cardinality constraint[END_REF] . Unfortunately, their time complexity is cubic. Now, we can reformulate the OrderedDistribute constraint with a cardVar-Gcc constraint and some arithmetic constraints. Consider C =OrderedDistribute(X,T ,I max ). Let t = |T | -1 and n = |X|. We define CN (C) the constraint network corresponding to the OrderedDistribute constraint as follows:

• The variable set is X ∪ Card, where Card = {Card[0], ..., Card[t]} is a set of non negative integer variables. • The constraint set if defined by the constraints:

-∀k = 0...t, t i=k Card[i] ≤ I max [k] -∀k = 1...t, k-1 i=0 Card[i] ≥ n -I max [k] -cardVar-Gcc(X, T , Card)
We explicitly add the second type of constraints because as far as we know solvers are not able to deduce from two sum constraints n i=p+1 y i ≤ a and n i=1 y i = n that we have

p i=1 y i ≥ n -a.
be concretely applied in practice, these problems can be view as optimization problems in which some constraints may be violated.

It is easy to check that this constraint network reformulates the constraint C (i.e., they have the same set of solutions). Unfortunately, this reformulation is weak even if the strongest filtering algorithms are used for each constraint, as shown by the following example:

Example 4.1. Let X = [x 1 , x 2 , x 3 , x 4 , x 5 ] be 5 variables such that D(x 1 ) = D(x 2 ) = {0, 1}, D(x 3 ) = {0, 1,
2}, and D(x 4 ) = D(x 5 ) = {2, 3}. We consider the following constraints :

(1) At most 3 x i greater than or equal to 1.

(2) At most 2 x i greater than or equal to 2.

(3) At most 2 x i equal to 3. This example can be modeled by the constraint C =OrderedDistribute(X, T , I max ), with T = [0, 1, 2, 3] and I max = [5, 3, 2, 2]. The constraint network associated with C involves the constraints:

(1) Card[3] ≤ Imax[3] = 2 (2) Card[2] + Card[3] ≤ Imax[2] = 2 (3) Card[1] + Card[2] + Card[3] ≤ Imax[1] = 3 (4) Card[0] + Card[1] + Card[2] + Card[3] ≤ Imax[0] = 5 (5) Card[0] + Card[1] + Card[2] ≥ |X| -Imax[3] = (5 -2) = 3 (6) Card[0] + Card[1] ≥ |X| -Imax[2] = (5 -2) = 3 (7) Card[0] ≥ |X| -Imax[1] = (5 -3) = 2 (8) cardVar-Gcc(X, T , Card)
If the strongest filtering algorithms are used for CN (C) then the domains of the Card variables become D(Card [3]

) = {0, 1, 2}; D(Card[2]) = {0, 1, 2}; D(Card[1]) = {0, 1, 2, 3}; D(Card[0]) = {2, 3}.
No value is removed from the domain of variables of X, whereas it should. Variables x 4 and x 5 can only take a value in {2, 3} and at the same time the number of times any value greater than or equal to 2 can be taken is 2, because of the constraint number 2) in Example 4.1. Therefore, no other variable can take a value in {2, 3} and so value 2 can be safely removed from D(x 3 ). cardVar-Gcc does not remove such a value, because it considers, for instance, that x 4 and x 5 can take value 3 and then x 3 value 2. In addition, note that the filtering algorithms associated with some constraints used in this reformulation are costly in practice. Thus, we have two reasons for designing an efficient filtering algorithm for the OrderedDistribute constraint.

Filtering Algorithms

Filtering Algorithm Based on Flow

First, we can note that it is possible to design a filtering algorithm based on flow as for the Gcc constraint. An algorithm in O(n 2 k) for checking consistency and establishing arc consistency is presented in [START_REF] Petit | The ordered global cardinality constraint[END_REF] , where n = |X| and k = |T |. We will not detail the algorithm here, but we will give the main idea because it solves the issue with respect to the lack of filtering of the reformulation illustrated by Example 4.1. Moreover, it shows how some arithmetic constraints between cardinality variables can be integrated into a classical filtering algorithm for Gcc. This technique might also be useful to deal with generalizations of the OrderedDistribute constraint.

This filtering algorithm is based on the search for a flow of value n = |X| in a particular digraph. For convenience, we will denote by lb the lower bound capacity of an arc and by ub its upper bound capacity. Figure 3 is an example of such a digraph associated with an OrderedDistribute constraint.

Definition 5.1. Let C =OrderedDistribute(X, T , I max ), we define the digraph G(C) = (X G , U G ) as follows: • X G = {s, t} ∪ X ∪ T . • U G contains: -An arc (T [i], x) for each T [i] ∈ T and x ∈ X s.t. T [i] ∈ D(x). ub(T [i], x) = 1. -An arc (T [i], T [i + 1]) for each i ∈ {0, . . . , |T | -2} with ub(T [i], T [i + 1]) = I max [i + 1]. -An arc (x, t) for each x ∈ X with ub(x, t) = 1. -An arc (s, T [0]) with ub(s, T [0]) = |X|.
-An arc (t, s) with lb(t, s) = |X| and ub(t, s) = |X|.

The main idea is to link the values together. In this way, the flow value which reaches a value v of T must pass by all the values less than v and so it is possible to count for these values the quantity of flow corresponding to the assignments of variables to values greater than them. Proposition 5.1. Given C = OrderedDistribute(X, T , I max ) and its corresponding digraph G(C), the two following properties are equivalent:

• OrderedDistribute(X, T , I max ) has a solution.

• There exists a feasible flow from t to s in G(C).

Once a feasible flow of value n has been computed in G(C), arc consistency can be established with the same algorithm as for Gcc, so with a linear complexity.

Such a filtering technique requires to work with an additional data structure (the digraph associated with the constraint) and to compute and maintain a flow. In the next section we propose a simpler algorithm which is also more efficient in practice.

Linear Filtering Algorithm

We first come up a consistency check for OrderedDistribute, in a time complexity linear over the number of variables. Then, we come up with the linear GAC filtering algorithm. By Definition 3.3, we have the following lemma.

Lemma 5.1. If OrderedDistribute(X, T , I max ) has a solution then

I max [0] ≥ |X|.
We define the assignment with all minimum values of domains.

Definition 5.2. The min-domain assignment of a set of variables X is the unique assignment A(X) of values to variables in X s.t. ∀x ∈ X, A(X, x) is equal to the minimum value in D(x).

Obviously, it is always possible to build a min-domain assignment if there is no empty domain, but this assignment does not necessarily satisfy the constraint. Proposition 5.2. Let A(X) be the min-domain assignment of an instance C of OrderedDistribute. The two propositions are equivalent: [1] and ∀i = 0, ..., |T | -

(α) #(T [0], A(X)) ≥ |X| -I max
1: #(≥ T [i], A(X)) ≤ I max [i]. (β) C has a solution.
Proof. (⇒) Suppose that (α) is satisfied. By definition 3.3, A(X) is a solution of C. (⇐) Suppose that C has a solution. By contradiction: assume that the min-domain assignment A(X) of C does not satisfy (α). Two cases are (mutually) possible: (i) The number of times T [0] is assigned to a variable in A(X) is strictly less than |X| -I max [1]. By Definition 5.2, any variable x s.t.

T [0] ∈ D(x) is assigned to T [0] in A(X).
Therefore, no other assignment can have a greater number of occurrences of T [0] and thus satisfies C, a contradiction. (ii) Assume that a value

T [i] is s.t. #(≥ T [i], A(X)) > I max [i]
. By definition 5.2, if a value greater than T [0] is assigned to a variable x in A(X), this value is the minimum of D(x). Variables x in A(X) that take value T [i] cannot take a value strictly less than T [i]. No assignment exists with a lower value for #(≥ T [i], A(X)). C has no solution, a contradiction. From Proposition 5.2 and Definition 5.2, the feasibility of an OrderedDistribute can be checked in O(n), where n = |X|. We present now this dedicated filtering algorithm for OrderedDistribute.

Algorithm 1: isSatisfiable(OrderedDistribute(X, T , Imax)): boolean 1 if #(T [0], A(X)) < |X| -Imax[1] then 2 return false; 3 foreach T [i] ∈ T do 4 if #(≥ T [i], A(X)) > Imax[i] then return false;
Next Corollary gives a sufficient condition for having all the values consistent with OrderedDistribute.

Corollary 5.1. Let C =OrderedDistribute(X, T , I max ), if ∀i ∈ {0, . . . , |T | -1}, #(≥ T [i], A(X)) < I max [i] then ∀x ∈ X, ∀v ∈ D(x), (x, v) is consistent with C. Proof. The assignment A (X) obtained by replacing A(X, x) by v in A(X) is s.t. ∀T [i] ∈ T, #(≥ T [i], A (X)) ≤ I max [i]. By Definition 3.3, A (X) is a solution of C.
Now, we can establish the corollary defining precisely the consistent values. Intuitively, there are two reasons for a value v ∈ D(x) not to be consistent. The first one is that its variable x must be assigned to T [0] to satisfy the minimum requirement and v > T [0]. The second one is that, a maximum of occurrences is reached for a value w ≤ v when all variables take their minimum value and x is assigned to a value u < w. Thus x cannot be assigned to v because in this case the number of value assigned to a value equal or greater than w are strictly greater than I max [k] with w = T [k]. We denote by X ⊥ the set of variables whose domain contains T

[0]: X ⊥ = {x ∈ X s.t. T [0] ∈ D(x)}.
Corollary 5.2. Let C be a feasible OrderedDistribute(X, T , I max ) and A(X) be the min-domain assignment. A value v ∈ D(x) is not consistent with C if and only if one of the two following property is satisfied:

(α) x ∈ X ⊥ , v > T [0] and |X ⊥ | = |X| -I max [1]. (β) ∃T [i] ∈ T, #(≥ T [i], A(X)) = I max [i] and A(X, x) < I max [i] and v ≥ T [i].
Proof. (α) is immediate. (β) By definition, if in A(X) a value is assigned to a variable x, this value is the minimum of D(x). Therefore, if

T [i] satisfies #(≥ T [i], A(X)) = I max [i], then given x ∈ X with A(X, x) < I max [i], there exists no assignment A (X) s.t. A (X, x) ≥ I max [i] and #(≥ T [i], A (X)) ≤ I max [i].
Algorithm 2: Filter(OrderedDistribute(X, T , Imax))

1 if ¬ isSatisfiable(OrderedDistribute(X, T , Imax)) then 2 return; 3 A(X) ← min-domain assignment of X ; 4 X ⊥ ← {x ∈ X s.t. T [0] ∈ D(x)} ; 5 if |X ⊥ | = |X| -Imax[1] then 6 foreach x ∈ X ⊥ do 7 D(x) ← {T [0]} ; 8 T= ← {T [i] ∈ T s.t. #(≥ T [i], A(X)) = Imax[i]} ; 9 X ← X ; 10 while T= = ∅ ∧ X = ∅ do 11

Pick and remove the minimum value T

[i] in T= ; 12 foreach x ∈ X s.t. A(X, x) < Imax[i] do 13 Remove from D(x) the set {v ∈ D(x), v ≥ T [i]} ; 14 X ← X \ {x} ;
From Corollary 5.2 we obtain Algorithm 2. Values removed from a domain D(x) are necessarily strictly greater than A(X, x). It is necessary to evaluate each of these values (line 10) because some new variables can be reached when evaluating higher values in T = (defined in line 8), thanks to the condition of line 12.

This algorithm enforces GAC. Indeed, assume that a value T [i] ∈ D(x) is not consistent with the constraint after the run of the algorithm. This means that assigning T [i] to x entails in any complete assignment of X the existence of a value T [j] such that #(≥ T [j], A(X)) > I max [j] and j ≤ i; especially in the mindomain assignment A(X). By construction of T = and from line 13 of the algorithm, when T [j] ∈ T = was considered, T [i] was removed from D(x) by the algorithm, a contradiction. We can adapt Algorithm 2 to make it incremental, by maintaining at least the following data:

• The min-domain assignment A(X).

• An array T # ≥ counting, for each value T [i], the number of values w ≥ T [i] that appear in A(X).

However, even in this case, each time the counter of a value in T # ≥ becomes such that T # ≥ [i] = I max [i] it will be necessary to scan the variables in order to remove all the values greater than T # ≥ [i] for all variables having a value in A(X) strictly less than I max [i]. Thus, time complexity remains in O(|X| + |T |), and it can be amortized on a given branch of the search tree only w.r.t. |T |, which is not very relevant : Algorithm 2 has a linear time complexity and there is generally a few number of cost values. The practical time cost for updating the stored data A(X) and T # ≥ and the trail seems to be prohibitive. For the experiments we implemented Algorithm 2 with the version presented in this section.

Experiments

We experimented our global constraint on instances of the problem described in Example 3.1, which is derived from 5 , using the Java-based constraint programming engine Choco c .

We compared two representations of OrderedDistribute.

• In the first one, we use the new global constraint we have defined. We name this model GlocalCt-Model.

c http://www.emn.fr/z-info/choco-solver/index.html

• In the second one the constraint is replaced by a constraint network equivalent to the one proposed in Section 4. We name this model CN-model.

We tried for each model several search strategies. With the first model (GlobalCt-Model), the best results are obtained if, first, we first assign the minimum value to the start variable having the minimum-sized domain and then the same for cost variables. With the second model (CN-Model), the search strategy dom/wdeg 2 was the most efficient.

Instances involve n = 55 activities, m = 40 hours, durations between 1 and 4, resource consumption between 1 and 4, capa = 8, relax capa = 12. Costs at each point in time are from 0 to 4, the imposed distribution is for each day of 8 hours : At most 5 costs ≥ 1, at most 3 costs ≥ 2, at most 1 cost equal to 4.

CN-Model

GlobalCt -/ > 10 min / --/ > 10 min / -Table 1 gives the results obtained for instances such that no solution exists without over-loads (if there is no over-load then OrderedDistribute is not useful). Time limit is 10 minutes. The two unsolved problems have no solution satisfying the ordered cardinality constraints, but proving this unsatisfiability requires more than 10 minutes.

These results show that the use of a generic heuristic dom/wdeg which is wellsuited does not compensate the lack of filtering of the model CN-Model, except for a few number of instances which are easy to solve.

With OrderedDistribute (GlobatCt-Model), 16 of the 20 instances are solved and proved to be optimal in less than one minute (15 of them in less than 12 seconds), while the other model proves optimality only for 8 of the 20 instances. This latter model is not able to find a solution in a time less than 10 minutes for the 12 remaining instances. A few instances remain hard for the two models, since the optimum value cannot be found in less than 10 minutes. This is not surprising since searching for the minimum sum of over-loads in a soft cumulative problem (and proving optimality) is known to be a difficult problem.

OrderedDistribute with Range Variables

A natural extension of OrderedDistribute is to consider that maximum number of occurrences of values are not scalar integers but a set of range variables. We distinguish two cases.

• The first one is obtained by replacing in Definition 3.3 the integer array I max by an array of range variables R: the number of values greater than or equal to a given value v should be less than the value of its range variable in R. • The second one is similar to the first one except that the number of values greater than or equal to a given value v should be equal to the value of its range variable in R.

OrderedDistributeRangeLeq

Definition 7.1. In a OrderedDistributeRangeLeq(X, T , R), we use the parameters described in Definition 3.3 except that R is a set of range variables. Given an assignment A(X), OrderedDistribute(X, T , R) is satisfied iff the two following constraints are satisfied.

(

) #(T [0], A(X)) ≥ |X| -R[1]. ( 1
) ∀i = 0, . . . , |T | -1, #(≥ T [i], A(X)) ≤ R[i] 2
The consistency check remains the same than the one of OrderedDistribute except that we replace I max by the sequence of maximum values in domains of variables in R. The filtering algorithm remains the same concerning variables in X.

OrderedDistributeRangeEq

In this section, we study the case where the number of values greater than or equal to a given value v should be equal to the value of its corresponding range variable.

Definition 7.2. In a OrderedDistributeRangeEq(X, T , R), we use the parameters described in Definition 3.3 except that R is a set of range variables. Given an assignment A(X), OrderedDistribute(X, T , R) is satisfied iff the two following constraints are satisfied.

(

) #(T [0], A(X)) ≥ |X| -R[1]. ( 1
) ∀i = 0, . . . , |T | -1, #(≥ T [i], A(X)) = R[i] 2
The filtering differs from OrderedDistributeRangeLeq. We need to compute the exact upper bounds of domains of variables in R (lower bounds are given by A(X) similarly to OrderedDistributeRangeLeq). Next example shows that such a computation does not simply consists in sorting the variables x i ∈ X by non decreasing max(D(x i )), then remove the first |X| -R [1] ones, and then count for each v ∈ T the number of values greater than v in domains of remaining x i 's. Consider C = OrderedDistributeRangeEq(X, T , R). We search for each value v = T [i] the assignment satisfying C and having the maximum number of values greater than or equal to v. We show that it is enough to solve this problem in general. We propose to simplify the problem by only considering two values per domain of each variable. Notation 1. Let v be a value in T . For any variable in X let min(x) be the minimum value of the domain and w(v, x) be the value of D(x) which is the nearest of v by excess (i.e. w(v, x) ≥ v and ∃u ∈ D(x) with w(v, x) ≥ u ≥ v). Property 1. Let v be a value in T and A(X) be any assignment satifying C with #(≥ v, A(X)) = j. Then, the assignment A (X) defined from A(X) as follows:

• A (X, x) = min(x) iff A(X, x) < v one variable (if the min value is taken then the obtained assignment has less value greater than v than when w is taken).

Thus, consider that the current variable that has to be assigned within the greedy algorithm is x, with D(x) = {min(x), w(v, x)}. Suppose that we assign min(x) to x. We will show that we can obtain an equivalent or "better" solution (which maximizes the number of values greater than v) by taking w(v, x). After assigning min(x) to x, the greedy algorithm is continued and an assignment A(X) is computed. This assignment satisfies the OrderedDistribute constraint. Now, if we impose A(X, x) = w(v, x) and if the assignment remains a solution then the current solution is improved and it is better to assign x with w(v, x). Therefore, we consider that this swap between min(x) and w(v, x) is not possible. Consider Y the set of variables assigned after x. Note that, by definition of the greedy algorithm any variable y ∈ Y satisfies min(y) ≤ min(x). Then, we have two possible cases:

• There exists a variable y ∈ Y with w(v, y) ≥ w(v, x). Then, Lemma 7.1 can be applied. This means that we can safely assign w(v, x) to x. • Each variable y ∈ Y satisfies w(v, y) < w(v, x). We consider the one with the w value which is the closest to w(v, x) (that is, we define z ∈ Y satisfying ∃y ∈ Y -{z} with w(v, z) < w(v, y) < w(v, x)). At the moment where x has been assigned, min(x) and w(v, x) were in its domain, therefore we had #(≥ w(v, x), Ap(X)) < R[k] and T [k] = w(v, x), where Ap(X) was a partial assignment. By the absence of variable of Y with w(v, y) = w(v, x) and by the definition of z it means that this property still holds for A(X). Therefore, Lemma 7.2 can be applied and we can safely assign x to w(v, x).

Thus, in all the cases it is safe to assign x to w(v, x) and this leads to an equivalent or better solution.

Property 2. The greedy algorithm can be applied for each value v of T with an overall time complexity in O(nk + k 2 ).

Proof. (Sketch) The complexity for one value v depends on the computation of w(v, x) for each variable and the double sorts (check of consistency can be done in constant time each time a variable is fixed). Consider n = |X| and k = |T |. Each sort can be performed in O(k) by a counting sort. The computation of w(v, x) can be done for each variable in O(log(k)). So for one value v we obtain a complexity in O(n log(k) + k). However, when running the greedy algorithm for each value v we can amortize some computations: All the w values for a variable x can be computed in O(k) by traversing the domain while v is increased. Since there are k values to consider, the overall complexity is O(nk + k 2 ).

Aggregations of OrderedDistribute

The main usage of OrderedDistribute is depicted by Example 3.1 and Figure 2: In order to obtain a particular distribution of costs, cost variables are partitioned and an instance of OrderedDistribute is set on each subset of variables corresponding to a class of the partition. In the Example, a day is represented by a sequence of 8 cost variables representing over-loads during the 8 hours of this day. For each day an instance of OrderedDistribute is set on the over-loads variables.

Additionally, an objective is usually defined over the whole set of cost variables, represented by an objective variable obj and an objective constraint. In the Example, we wish to minimize the sum of over-loads during a week of five days, that is, 40 cost variables.

We focus in this section on two classical cases for this objective constraint: either minimize the sum of costs, obj = x∈X x, or minimize the maximum value assigned to a variable, that is, obj = max x∈X x. Consider a sequence X of variables, partitioned in subsequences such that an instance of OrderedDistribute is set on each subsequence. Let us first focus on the case where the objective is a sum. The sum of minimum values in domains of variables in X provide a lower bound LB for the obj variable. From this lower bound, we can update arguments of each instance of OrderedDistribute before calling the filtering algorithm.

• If max(D(obj)) minus LB plus the sum (min(D(x i )) of variables x i involved in the current instance of OrderedDistribute is greater than I max [1], then we can safely decrease I max [1]: The maximum number of values greater than or equal T [1] in a solution satisfying the objective constraint (more precisely, in a solution with an objective value less than or equal to max(D(obj))) is max(D(obj)) minus LB plus the sum (min(D(x i )) of variables x i involved in the current instance of OrderedDistribute. The same reasoning can be applied on I max [2], and so on, until the condition is not satisfied (recall that, by Definition 3.3, values in the array I max decrease as the index increases).

• Since we make no hypothesis with respect to the implementation of the objective constraint, quantity I max [v] of values v which cannot be assigned to any variable in X without exceeding max(obj) can be set to 0. Algorithm 4 implements the same idea for the objective constraint obj = max x∈X x, using the same conventions. This case is simpler since one has just to avoid exceeding the maximum value of the objective variable obj. Note that Algorithm 3 and Algorithm 4 can work with sets of variables and arrays I max which are different from an instance of OrderedDistribute to another one (not the same number of variables and not the same restrictions on occurrences).

Conclusion

In this paper we presented a new global constraint, OrderedDistribute, which solves a practical modelling issue with respect to problems involving cost variables with strongly ordered domains. This constraint is complementary to global constraints based on statistics, such as Spread or Deviation. OrderedDistribute addresses those problems where variables can be carved in disjoint subsets, to control in a very precise way the number of occurrences of cost values within each subset. We provided a linear GAC filtering algorithm for OrderedDistribute. We experimented successfully our global constraint on a cumulative problem with over-loads.

Fig. 1 .

 1 Fig. 1. Example of SoftCumulativeSum with a ground schedule with 3 fixed activities: a 1 starts at 0 and ends at 3, and res[a 1 ] = 2. a 2 starts at 2 and ends at 7, and res[a 2 ] = 2. a 3 starts at 5 and ends at 8, and res[a 3 ] = 3. There is 3 over-loads: cost[2] = 1, cost[5] = 2, cost[6] = 2.

Fig. 3 .

 3 Fig. 3. Example of a digraph representing an OrderedDistribute(X, T , Imax). Arcs between values and variables have a lower bound equal to 0 and an upper bound equal to 1.

5

  return true; Thanks to this procedure, time complexity of a flow-based algorithm (see Section 5.1) can be decreased to O(nk), where k = |T |. This time complexity can be improved again, by using an algorithm which does not require to work with an additionnal data structure.

Proposition 5 . 3 .

 53 The time complexity of this algorithm is O(n+k), where n = |X| and k = |T |, provided that given v ∈ D(x), we can remove all values greater than v in O(1).Proof. (Sketch) Values in T = (line 11) and in A(X) (line 12) can be sorted in increasing order in linear time by a counting sort since T is bounded. The total number of times lines 12 -14 of the algorithm are executed is upper-bounded by |X|: if a variable is reached then it is removed from X by line 14. Thus the time complexity is in O(|T | + |X|) Proposition 5.3 states that GAC can be enforced on OrderedDistribute with a time complexity linear in the sum of the number of variables and the number of values in the union of their domains. Regarding the literature, we can note that some other simple generalizations of Gcc are NP-Hard 7 .

Example 7 . 1 .

 71 Let X = {x 1 , . . . , x 5 } such that D(x 1 ) = D(x 2 ) = {0, 4}, D(x 3 ) = {0, 3, 4}, D(x 4 ) = D(x 5 ) = {1, 2, 3}. T = [0, 1, 2, 3, 4]. Assume that D(R[4]) = [0, 1] and D(R[1]) = [0, |X|],and that we wish to prune D(R[3]), which is currently [0, 5]. The maximum possible value for R[3] is 4 because x 1 and x 2 cannot take both value 4.

Algorithm 3 : 2 U

 32 AgFilterSum(OrderedDistribute OD[],obj, X) 1 LB ← x∈X min(D(x)) ; B ← max(D(obj));

3 for j = 0 to |OD| -1 do 4 ∆ 7 k ← 1 ; 8 while

 34718 ← U B -LB + x∈OD[j].X min(D(x)) ; 5 if OD[j].Imax[1] > ∆ then 6 for i = 1 to |OD[j].Imax| -1 do OD[j].Imax[i] ← min(OD[j].Imax[i], ∆) ; /* Decrease too big OD[j].Imax[i] */; k ≤ |OD[j].T | -1 ∧ OD[j].T [k] ≤ ∆ do k ← k + 1;

9

  for i = k to |OD[j].Imax| -1 do OD[j].Imax[i] ← 0 ; /* Setto 0 maximum occurrences of values in OD[j].T strictly greater than ∆ */; 10 Filter(OD[j]);

Algorithm 3

 3 implements these two principles. The set of instances of OrderedDistribute are stored in an array OD[] of size |OD|, indexed from 0 to |OD| -1. Arguments of one particular OrderedDistribute at index j of the OD OrderedDistribute array are denoted respectively by OD[j].X, OD[j].I max , and OD[j].T . To simplify notations, Algorithm 3 considers that each OD[j].I max is storable: values which have been modified at this node are automatically re-assigned to the previous value when a backtrack occurs.

Algorithm 4 : 1 U 3 k ← 1 ; 4 while

 41314 AgFilteringMax(OrderedDistribute OD[],obj, X) B ← max(D(obj)); 2 for j = 0 to |OD| -1 do k ≤ |OD.T | -1 ∧ OD.T [k] ≤ U B do k ← k + 1; 5 for i = k to |OD.Imax| -1 do OD[j].Imax[i] ← 0 ; /* Set to 0 maximum occurrences of values in OD[j].T strictly greater than U B */; 6 Filter(OD[j]);

  When the time horizon (maximum latest completion time among all activities) is fixed, the problem may have no solution if no over-loads on the resource capacity are tolerated. In 5 , authors introduced a relaxed version of Cumulative devoted to this class of problems. Definition 3.2. The constraint SoftCumulativeSum relaxes Cumulative by introducing:• A time horizon th.• A relaxed capacity of the resource denoted by relax capa with capa ≤ relax capa. • An integer variable cost[t] for each point in time a t < th.• An integer variable obj.

Definition 3.1. Given one resource with a capacity limited by capa and a set A of n activities, at each point in time t the cumulated height h[t] of the activities overlapping t is h[t] = a∈A,start[a]≤t<end[a] res[a]. The Cumulative(A, capa) constraint 1 enforces that: C1 : For each activity a ∈ A, start[a] + dur[a] = end[a]. C2 : At each point in time t, h[t] ≤ capa.

  It differs from OrderedDistribute w.r.t. lower bounds of domains variables in R: They may become not consistent with OrderedDistributeRangeLeq according to the current domains of variables in X. For instance, for a value T [i] it may not remain enough values less than T [i] in domains of variables X to impose #(≥ T [i], A(X)) ≤ 0, so as 0 can be removed from R[i]. Minimum values for variables in R can be updated directly by counting, for each T [i], the number of variables in A(X) greater than or equal to T [i]. This can be done incrementally while A(X) is built (note that A(X) remains the same after the filtering of variables in X). At last, increasing explicitly a lower-bound of a variable R[i] has no consequence except a fail if min(D(R[i])) > max(D(R[i])). Thus, GAC can be achieved on OrderedDistributeRangeLeq in O(n + k) time, with n = |X| and k = |T |.

• A (X, x) = w(v, x) iff A(X, x) ≥ v satisfies the constraint C and satisfies #(≥ v, A (X)) = j.

Proof. Clearly we have #(≥ v, A (X)) = j. In addition, since each value of A(X) is replaced by a smaller value it is clear that if A(X) satisfies C then A (X) also.

We propose the following greedy algorithm:

(1) We order in L the variables by their non increasing min value. We break tie by non decreasing w value. (2) We repeat the following process until L is empty:

We take the first variable x of L and remove it from L; and we assign w(v, x) to x if it does not violate C; otherwise we assign min(x) to x.

(3) The obtained assignment maximizes the number of values greater than v.

To prove correctness of this algorithm we introduce two lemmas. Let A(X) be any assignment satisfying C and two variables x 1 and x 2 : Lemma 7.1. Assume w(v, x 1 ) = A(X, x 1 ) and min(x 2 ) = A(X, x 2 ). If min(x 1 ) ≤ min(x 2 ) and w(v, x 1 ) ≥ w(v, x 2 ) then the assignment A (X) with min(x 1 ) = A (X, x 1 ) and w(v, x 2 ) = A (X, x 2 ) and ∀y ∈ X -{x 1 , x 2 } : A (X, y) = A(X, y) satisfies C and has the same number of values greater than or equal to v as A(X).

Proof. A (X) has obviously the same number of values greater than or equal to v as A(X). A(X) contains the set of value V and the values w(v, x 1 ) and min(x 2 ); and A (X) contains the set of value V and the values min(x 1 ) and w(v, x 2 ). Since min(x 1 ) ≤ min(x 2 ) and w(v, x 2 ) ≤ w(v, x 1 ) then if A(X) satisfies C then A (X) also. X,y) satisfies C and has the same number of values greater than or equal to v as A(X).

Proof. A (X) has obviously the same number of values greater than or equal to v as A(X). A(X) contains the set of value V and the values w(v, x 1 ) and min(x 2 ); and A (X) contains the set of value V and the values min(x 1 ) and w(v, x 2 ). We have w(v, x 1 ) < w(v, x 2 ) and #(≥ w(v, x 2 ), A(X)) < R[k] and T [k] = w(v, x 2 ) hence by exchanging w(v, x 2 ) and w(v, x 1 ) the assignment remains a solution.

We prove by induction that it is enough to assign w(v, x) to x when x has to be assigned and D(x) = {min(x), w(v, x)}. It is obviously true when there is only


Chongsheng Zhang
email: chongsheng.zhang@inria.fr

Xiangliang Zhang
email: xiangliang.zhang@kaust.edu.sa

Florent Masseglia
email: florent.masseglia@inria.fr

Modeling and Clustering Users with Evolving Profiles in Usage Streams

Existing data stream models commonly assume that users' records or profiles in data streams will not be updated once they arrive. In many applications such as web usage, however, the users' records/profiles may evolve along time. This kind of streaming transactions are referred to as bi-streaming data -the data evolves temporally in two dimensions, the flowing of transactions as with the traditional data streams, and the evolving of users' profiles inside the streams, which makes bi-streaming data different from traditional data streams. The two-dimensional evolving of bi-streaming data brings difficulties on modeling and clustering for exploring the users' behaviours. This paper will propose three models to summarize bi-streaming data, which are the batch model, the Evolving Objects (EO) model and the Dynamic Data Stream (DDS) model. Through creating, updating and deleting user profiles, the models summarize the behaviours of each user as an object. Based on these models, clustering algorithms are employed to identify the user groups. The proposed models are tested on a real-world data set showing that the DDS model can summarize the bi-streaming data efficiently and effectively, providing better basis for clustering user profiles than the other two models.

Introduction

Data streams are increasingly growing in volume and diversity with the extensive use of web, sensors and mobile devices. These days, many companies need to handle or process large volume of streaming data. Moreover, they expect the streaming data to be timely analyzed such that the real-time results are reported to make prompt responses.

Several data stream models have been proposed to approximately represent the data for accelerating the mining of data streams [START_REF] Abadi | Aurora: a new model and architecture for data stream management[END_REF][START_REF] Datar | Maintaining stream statistics over sliding windows[END_REF][START_REF] Chen | Multi-dimensional regression analysis of time-series data streams[END_REF][START_REF] Babcock | Models and issues in data stream systems[END_REF][START_REF] Zhu | Statstream: statistical monitoring of thousands of data streams in real time[END_REF]. The data streams managed by these models have a common characteristic that their transactions are deemed independent. That is to say, each arriving transaction is a complete description of the observed objects. In some real cases, however, the transactions/records may be related to others arriving before or after them. For instance, when users access internet through mobile phones, they are unable to visit several pages within a very short period due to the operation inconvenience. Thus, their requests are separated into several transactions occurring in non-successive time steps. This kind of data streams is referred to as Bistreaming data, differing from the traditional streaming data with independent transactions. We give the definition of Bi-streaming data and its summarization model in Definition 1 with the application goal of exploring the user behaviours. Definition 1. Bi-streaming data and summarization model. Bi-streaming data is a time-ordered sequence that consists of transactions/records, each of which was made by a user with unique identifier. Transactions having the same user can be grouped together and summarized in form of (ID, content), where ID is the identifier of the user, and content is an abstract of all the transactions associated with the user.

In bi-streaming data, every arriving transaction can be an incomplete description of a user. From the user's point of view, his/her behaviour described by the associated transactions is evolving along time. From the streaming's point of view, the usage of system is evolving by adding/updating/deleting users. Summarizing the bi-streaming data into user groups structures a 2-dimensional streaming data, the streaming groups (ID, content) t along t and the streaming abstraction content t for each user ID.

To be clear, we give an instance of a bi-streaming data and its summarization in Table 1. Table 1. An example of bi-streaming data and its summarization. Example 1. Suppose that we are working with a data streams DS of online web usage. The set of transactions {T 1 ...T 12 } shown in Table 1 (a) is a proportion of DS. Each transaction T x contains a time stamp t i , a unique user identifier (ID) and a requested page. For instance, T 1 < C When more data are arriving at t i (i > 12), the set of navigation of users will be updated correspondingly. With the purpose of modeling the user behaviours and clustering the users for mining social groups, the summarization of users in terms of navigations will be analyzed. However, the summarization of users at time t i is incomplete which is an important characteristic stated in the definition of bi-streaming data. The incompleteness of the user's summarization makes it unsuitable to use the traditional data streaming models, which either treat the transactions one by one or wait until the descriptions of users' behaviours are complete. The former solution will cause the missing of interesting usage patterns, while the latter one requires the storage of a large amount of data, disabling the expected real-time analysis.

To solve the above problem, we propose 3 different approaches to model and summarize the bi-streaming streams, the Batch model, the Evolving Objects (EO) model and the Dynamic Data Stream (DDS) model. The 3 models provide the summarization of bi-streaming data by using different strategies and having different requirements on the computational resources. Based on the summarization, we cluster the users into social groups by Affinity Propagation that is a new clustering method with advantages in optimizing the clustering distortion [START_REF] Frey | Clustering by passing messages between data points[END_REF], and by Streaming Affinity Propagation (StrAP) that is an efficient and effective online clustering algorithm [START_REF] Zhang | Toward autonomic grids: analyzing the job flow with affinity streaming[END_REF]. The proposed models were applied on the real world 21.8 GB data set from France Telecom. The experimental results show that the summarization based on the DDS model is better than that of the other two models.

The rest of the paper is organized as follows. We discuss the related work of data stream models and algorithms in section 2. We introduce the Batch model, the EO model and the DDS model in section 3. The analysis of the models is presented in section 4. Section 5 describes the clustering algorithms used on top of the model. Section 6 gives the data sets and parameter setting in the validation. The application validation results are reported in section 7. Finally we conclude in section 8.

Related Work

In this section we make a short survey on existing data streams models. Also, we review related work on data stream mining.

Data stream models. There are five commonly adopted data stream models: batch processing model [START_REF] Giannella | Mining Frequent Patterns in Data Streams at Multiple Time Granularities[END_REF], sliding window model [START_REF] Abadi | Aurora: a new model and architecture for data stream management[END_REF][START_REF] Datar | Maintaining stream statistics over sliding windows[END_REF], tilted-time window model [START_REF] Chen | Multi-dimensional regression analysis of time-series data streams[END_REF], landmark window model [START_REF] Babcock | Models and issues in data stream systems[END_REF], and damped stream model [START_REF] Zhu | Statstream: statistical monitoring of thousands of data streams in real time[END_REF]. In batch model, the streaming data are divided orderly into several batches, then mining algorithms are run on each batch. The sliding window model only keeps a fixed size of recent data in memory, and replace the old transactions by the new arriving ones. The tilted-time window model provides different levels of resolutions compressing the old data and maintaining the new data in details. Unlike sliding window model which kicks the obsolete data out of the window as new data arrives, the landmark model keeps all the data which arrive after the landmark time. Instead of discarding the old data that live out of a window or arrived before the landmark time, the damped stream model decays the weights of the previous transactions according to their freshness.

Querying bi-streaming data. Regarding the query of bi-streaming data, Haghani et al. [START_REF] Haghani | Evaluating top-k queries over incomplete data streams[END_REF] investigated the issue of continuously monitoring the top-k individual objects. In this bi-streaming data, the numerical values of the same object are arriving intermittently in different transactions. To rank the objects, all the transactions related to one object within the current sliding window are added. The objects with k largest summation value are reported. In order to efficiently select the top-k objects, Haghani et al. focus on lowering the memory usage by pruning irrelevant objects.

Mining uncertain data streams. Unlike the incomplete but deterministic transactions in bi-streaming, transactions in uncertain data streams can have one of several possible values [START_REF] Dalvi | Management of probabilistic data: foundations and challenges[END_REF]. Assuming that the standard error of each data point is available, Aggarwal et al. in [START_REF] Aggarwal | A framework for clustering uncertain data streams[END_REF] develop a method for clustering uncertain data streams through the use of an uncertain micro-cluster model, which is comprised of a number of summary structures. When deciding the assignment of data points to clusters, the error level of uncertainty of the data points is included to measure the similarity between the point and the cluster centroid.

Out-of-order data streams. In out-of-order data streams, the arriving time of transaction does not necessarily follow their generation timestamps [START_REF] Cormode | Time-decaying aggregates in out-of-order streams[END_REF]. For time decaying aggregate computations, thanks to the q-digest data structure which summarizes the frequency distribution, the weighted value of the late arrivals are approximately estimated and accounted for in aggregation.

Mining evolving user profiles. Iglesias et al. proposed an online classifier that learns from streaming command-line data (the UNIX csh command), and recognizes the profile class of a computer user, e.g., novice programmers, experienced programmers, computer scientist, or non-programmers [START_REF] Iglesias | Creating evolving user behavior profiles automatically[END_REF]. The behaviour of each user is described by a histogram distribution of n relevant subsequence of commands. When a new user brings in the new set of subsequences, n will be increased and all users are described in a higher dimension. This is so-called evolving user profiles. A user is classified into the class to which he/she has the closest similarity measured by cosine distance. The evolving user profiles in this data stream [START_REF] Iglesias | Creating evolving user behavior profiles automatically[END_REF] are different from that of bi-streaming data. Each transaction of the former stream is a complete sequence of one user command, while one transaction of the bi-streaming data is only a part of one user's behaviour.

Modeling Bi-streaming Data

In this section, we will elaborate on the models for managing and mining the bi-streaming data. As stated before, bi-streaming data is a special data stream where it is common for several transactions to share the same identifiers. How to manage the bi-streaming data is an important issue which will influence the data stream mining results, e.g., clustering, frequent patterns mining. We hence propose 3 different models for handling the bi-streaming data, the Batch model, the Evolving Objects (EO) model and the Dynamic Data Stream (DDS) Model.

Batch Model

In order to summarize the behaviour of one user described in non-successive transactions, one intuitive way is to 1. collect the arriving transactions in a buffer until the buffer is full 2. for each user in the buffer find all transactions related to this user summarize these transactions create an object for this user with key=UserID and content=summarized transactions 3. release the buffer 4. start to collect the transactions and go to step 1 again.

Figure 1 demonstrates the batch model applied on an example of bi-streaming data shown in Table 1.

Evolving Objects Model

Evolving Objects (EO) model is based on a window sliding along the bi-streaming data. We create and maintain an object for each user by observing the transactions included in the current sliding window. Instead of re-constructing all objects at next buffer in the batch model, we maintain the objects in evolving objects model when reading every new transaction. Building the evolving objects model includes the following steps:

1. slide the window forward along the bi-streaming data 2. delete the items/contents in the expired transactions from the corresponding objects in the EO model 3. for each new transaction, check whether the identifier of this transaction exists in the model if yes, add the items/content of the new transaction to the existing object otherwise, create a new object with the items of the new transaction then insert it to the EO model Figure 3 is an example of applying EO model on bi-streaming data shown in Table 1.

Example 3. In Figure 3, the current sliding window with size 8 includes (T 2 ...T 9 ). Before this, we created new objects for the two users when T 1 and T 2 were in the window. As the window was not full, there was no out-of-date transaction to be deleted. Then T 3 came, we checked the model and found that its identifier C 1 was already there. So we updated the content of C 1 from {A} to {A, C}. Likewise, we update the model until we read transaction T 9 in the current sliding window. At this point the window is full and we have to remove the oldest transaction out of the sliding window. Transaction T 1 is the oldest transaction and removed. Consequently, we should update the object of its owner, by updating the content of C 1 from {A, C, H} to {C, H}. Then we add {F } to the object of current transaction's owner C 2 . The final model obtained by EO model is the same as that built by the Batch model. Actually, EO model is an incremental implementation of the Batch model.

Dynamic Data Stream Model

Dynamic Data Stream (DDS) model has two main components: an Objects List (window) and a Map with user ID as the key. Figure 4 shows the data structure of our proposed DDS model. The Objects List maintains the objects in a list, and each object in the list carries the item set for the corresponding user. For simplicity, we refer to the left end of list with old objects as the head of the list and the right end with recent objects as the tail of the list. The objects that come earlier and have no updates recently would be in the head of the list and those recently arrived or updated will be close to the tail of the list. When there is not enough space, old objects will be removed from the head of the list. In order to quickly check whether the identifier already exists in the current list/window, we keep a map, whose keys are the identifiers of the according objects in the list. Since the identifiers are unique, we can promptly find the according object (with the help of the map) in the list without scanning the data again.

In DDS model, the new/recently updated objects will always be appended or moved to the tail of the list and be connected after the object which is currently at the tail of the list. Consequently, the tail should be the entry for us to add new objects and head is the exit for us to remove the old objects out of the list.

Generally, when a new transaction arrives, we update the DDS model by the following process:

1. check whether the identifier of this new transaction exists in the object list if yes, add the items/content of the new transaction to the content of the existing object otherwise, create a new object 2. move the updated (or add the new) object to the tail of the list 3. check whether there is no enough space if yes, delete the object in the head of list.

Figure 5 illustrates the process of building DDS models from the bi-streaming data shown in Table 1. Example 4. After reading the first transaction T 1 < C 1 , t 1 , A > from the bistreaming data in Table 1, we insert the first object O 1 < C 1 , {A} > at the tail of the list. Similarly, after T 2 arrives, we insert another object O 2 < C 4 , {A} > after O 1 . So far, object O 2 is the latest object in the list and object O 1 is the head of the list. When T 3 comes, we will not make a new object, because with the help of the map we find the identifier of T 3 is C 1 , the same as the key of object O 1 < C 1 , {A} >. For taking T 3 into the list, we update the content of the

O 1 from O 1 < C 1 , {A} > to O 1 < C 1 , {A, C} >,
and move it from its current position (head of the list) to the tail of the list. After this updating, object O 1 is the latest object in the tail of list and object O 2 is oldest and becomes the head of the list.

Given limited memory, elder objects in the head of list will be removed. Let the memory limit for the model be 8 transactions. After reading T 9 , we have to remove an old object C 3 , which is currently the head (oldest one) of the list. The final objects in the list will be, in accordance with the order from new objects to old objects, < C 2 , {D, E, F } >, < C 1 , {A, C, H} >, < C 4 , {A, C} >.

The Analysis of Bi-streaming Models

In this section we analyze the advantages and disadvantages of the 3 candidates of bi-streaming models, the batch model, EO model and DDS model, in terms of pattern preservation, CPU cost and memory usage.

Preservation of Usage Patterns

Let us review the data managed in Figures 1, 3 and5. Given the same transaction data (Table 1) and parameters (buffer size or window size to be 8), we obtain the same object list and content from batch and EO model, which are different from the results in DDS model. Looking into the content of user C 1 , we see that his/her behaviours are better preserved in DDS model than the other two models, as DDS model describes the behaviour of C 1 as {A, C, H}, whereas the batch and EO models describe C 1 as {C, H}. In addition, user C 3 , an out-of-date user, is not kept in DDS model but it is held by batch and EO models.

Comparing to the batch and EO models, DDS model specializes in keeping more complete profiles of frequently updated users. This property is due to the fact that DDS model moves the updated objects to tail of the list and pushes the old and seldom updated objects to the head of the list for deleting. DDS model can accumulate the users' patterns and keep users with longer patterns (active users with more dynamic behaviours). These patterns are useful in many applications. For instance, they can be used to analyze the web usage data with high bounce rate 1 .

The batch model has a very simple data structure, but it may truncate the intrinsic patterns hidden between batches by segmenting of the data in buffer size. The same drawback exists in EO model. However EO model offers dynamically organized objects while the batch model does not neaten the data until the batch is ready.

CPU Cost

To analyze the efficiency of each candidate model, we consider the price to pay for the operations of search, insertion, deletion, and update on the model as computational overhead.

Batch model waits until the buffer is full of transaction. Whenever reading a new transaction, we insert it to the transaction list in buffer. When the buffer is full, we build a map such that we can merge the transactions with same identifiers. On average for each transaction, the total cost is the search cost plus the insertion cost plus the updating cost.

EO model keeps the transactions in a sliding window, meanwhile maintains and updates the summarized objects in extra data structures on the fly. On the one hand, the advantage is that the arranged objects are always available for analysis. On the other hand, every time when a new transaction comes, we should not just list it in the sliding window, but we also search the map and update the corresponding objects. For any operation, we insert the transaction in window list. Next we search the map to check whether the same identifier already exists in the map. If it is a new object in EO model, we insert a new key in the map and create a new associated object for the key. If the identifier exists in EO model, we update the corresponding object in the map. EO model requires frequent deletion when the sliding window is full and new transaction arrives. Moreover, we have to search the according object before deletion and update it after deletion.

When reading a new transaction in DDS model, we first look up the map to check whether the according identifier already exists in the map. As each identifier is unique, the cost for the search over the map is O(1). Next, we will have 3 possible operations on the object associated with the identifier: insertion, update and deletion. If it is a new identifier, we will insert a key in the map. Moreover, we will create a new object and insert it in the tail of the list. The total cost for insertion is the search cost plus the insertion cost. If it is an existing identifier, then we will update the according object in the list and move it to the tail of the list. If we are going to remove an object from the list, we simply delete it from the list, but we do not need to search the map, because we always remove the oldest one from the head of the list. Therefore, comparing to EO model, DDS model requires less deletion and the deletion is much more economical with no additional actions of look up and update.

As a conclusion, DDS model has lower CPU cost than the batch model and EO model.

Memory Usage

The memory cost for each model is listed in Table 2. The memory usage of batch model has two parts. One part is the memory for keeping the batch transactions. The other is the memory required for establishing a mapping table to identify then merge the transactions with the same identifiers. In EO model, we not only have to keep the data in the sliding window, but we also need to maintain a map and extra arranged objects for all the identifiers. As a result, the memory usage is two times of the data size added by the map size. In DDS model, the objects are directly linked in the list. Thanks to the map we can easily reach the objects through the corresponding key. As we do not have to keep other extra data structures, the total memory usage is the size of the data added by that of the map.

The conclusion is that Batch and DDS models have the same memory usage. EO model, however, uses almost two times more memory than them. The above introduced 3 models, the batch, EO and DDS models, manage the bistreaming data through organizing the transactions by their identifiers. Based on the summarization by models, the common data mining tasks can be conducted, e.g., clustering, frequent pattern mining. In this paper, we apply the models for clustering applications. Note that we do not intend to evaluate the pros and cons of the clustering algorithms. Rather, we aim at evaluating different bi-streaming models for providing the best summarization, which is the foundation of mining clusters or frequent patterns.

The clustering methods we used are Affinity Propagation (AP) [START_REF] Frey | Clustering by passing messages between data points[END_REF] and Streaming Affinity Propagation (StrAP) [START_REF] Zhang | Toward autonomic grids: analyzing the job flow with affinity streaming[END_REF]. AP is a clustering method based on messages-passing. Comparing with other clustering methods, e.g., k-medoids, it has the advantages in terms of clustering quality, stability and annulling of setting the number of clusters k. StrAP is an online clustering method. It has the merits of (1) seamlessly updating the clustering model; (2) adapting to changes of data distribution; (3) intelligible compressed data model.

StrAP has been successfully used in clustering the traditional data streams [START_REF] Zhang | Toward autonomic grids: analyzing the job flow with affinity streaming[END_REF]. However, it cannot be directly used for clustering the bi-streaming data, because each transaction is not independent and not complete. Our proposed bistreaming models summarize the flow of transactions to be the flow of objects, which consist of an UserID and the related patterns of this user. In order to cluster the user behaviours, we can apply StrAP on the flow of objects that produced in EO and DDS model. We can also apply AP on the current set of objects at a given time stamp.

Clustering algorithm AP and StrAP require to measure the similarity between pairs of objects. Intuitively, we use the percentage of common elements between two objects as their similarity. AP and StrAP do not need the setting of the number of clusters before using. The only parameter for users to set is the "preference" of each object to be the center of a cluster. In the experiments, we empirically set this parameter to be the median value of all pair-wise similarities. For all different bi-streaming models, we use the same clustering algorithm with the same parameter.

In this section, we will describe the real-world data set we used, the experimental setting and the evaluation criteria in the application of the proposed 3 bi-streaming models and clustering.

Data Sets

The real-world data sets we employed are the usage records of mobile users from France Telecom. The full data set is of 21.8 GB size and contains nearly 60,000,000 lines of mobile users' browsing records from May to July of 2008. Each record (transaction) has 7 fields, including 3 numerical variables, 3 categorical variables and one date time variable. In our experimental validation, we used three relevant fields: 1) the identifier of the user; 2) the category of page that the user visited; and 3) the corresponding time when the user requested the page.

Besides the full data set, we generated a smaller data set by filtering out the records, whose corresponding users requested less than 2 pages in the real data set. After the preprocessing, the final trimmed data is about 4.7 GB. And the attributes used are the same as the real data set.

As we stated in Definition 1 in the Introduction, this browsing records of mobile users are typically bi-streaming data. Each record has an identifier of the user, and a visited page that is only a part of this user's request. Ordering all the records by their timestamps, we apply the proposed 3 candidate models to build the up-to-date model of this bi-streaming data.

Experimental Settings

The main parameter in proposed models is the window size (buffer size in the batch model), which represents how many transactions we will keep in memory. To ensure the fairness of evaluation, we use the same window size for all the 3 models. Thus, the number of transactions kept in each model is the same. In our experiments, the setting of window size varies from 10,000 to 120,000. The sensitivities of window size is analyzed in section 7.1.

In order to evaluate the performance of the proposed models and the clustering results obtained thereafter, we set up a reference model, which approximates the ideal situation of modeling bi-streaming data. Since we cannot afford to keep and analyze all the data in memory ideally, the next best way is to build a compromised reference model by holding as more data as possible in the Batch model, e.g., setting the buffer size as 3 times the window size of EO and DDS model. For instance, suppose that the results are going to be evaluated at transaction T n and the sliding window capacity is S in EO and DDS model, the number of transactions kept in reference model will be S × 3, counting back from T n until it has 3 times of the transactions.

Evaluation Criteria

The bi-streaming models are firstly measured in efficiency, i.e., the algorithm running time on each model. The effectiveness of bi-streaming models is assessed by the quality of clustering results obtained on top of the summarization models. The performance of proposed models are compared to that of the reference model, which uses 3 times more transactions in the batch model as we introduced in section 6.2. We adopted the following validation criteria for measuring the clustering quality:

1. Cluster Stability [START_REF] Meilȃ | The uniqueness of a good optimum for k-means[END_REF]. Cluster stability can be considered as a kind of precision. It measures the "goodness" of a clustering with respect to the reference. A larger stability value implies a better clustering. Suppose that we have a clustering C a with K a clusters and a reference clustering C r with K r clusters from the same set of N objects. We construct a N × K a probability matrix M a for clustering C a . Each element M a(i, j) = 0 if object i is not in cluster C a (j) and M a(i, j) = 1/ |C a (j)| if object i is in cluster C a (j) which has |C a (j)| members. Similarly, we construct a N × K r matrix M r for clustering C r .

Let M be the multiplication of M a T (the transpose of M a) and M r, M = M a T × M r. The stability value of clustering C a w.r.t. reference C r is defined as:

StabilityValue(C a , C r ) = trace(M * M ′ )/min(K a , K b )
where trace is the sum of diagonal elements of the matrix. The larger the StabilityValue is, the closer the clustering C a and the reference are, therefore the better the clustering C a is. 2. Entropy [START_REF] Aliguliyev | Performance evaluation of density-based clustering methods[END_REF]. This measure is based on information theory. The entropy value addresses the consistency level of clustering with regard to the reference. The larger the entropy, the worse the clustering compared to the reference. For example in the above clustering C a and reference clustering C r , if the objects which originally belong to the same cluster in C a (i) are scattered across the clusters in C r , the entropy of this cluster will be high.

We define the entropy of C a (i) (i th cluster of C a ) to be

E(C a (i)) = - 1 log(K r ) Kr j=1 |C a (i) ∩ C r (j)| |C a (i)| log |C a (i) ∩ C r (j)| |C a (i)|
The entropy of clustering C a w.r.t. reference C r is defined as the sum of the entropy values of all the clusters in C a :

E(C a ) = Ka i=1 |C a (i)| N E(C a (i))
7 Experimental Results of Modeling and Clustering the Real-world Data This section will report the experimental results comparing the performance of the proposed models. We implemented all the models and algorithms in C++ and conducted every experiment on the same computer with one Intel 2.33 GHz processor, 3 GB main memory, running Fedora 7 operating system. Figure 6 shows the user behaviours clustering results obtained by using AP on top of the DDS model and EO model, which were used to modeling the real-world bi-streaming data of mobile users. The X-axes of Figure 6 are the randomly selected clustering results. The clustering results are evaluated by the criteria as we introduced in section 6.3, Stability (Figure 6 (a) (b)), Entropy (Figure 6 (c) (d)) and the Average length of objects (Figure 6 (e) (f)). The performance of DDS model and EO model is tested on a wide range setting of window size (noted as wsize) parameter, from 10,000 to 120,000.

Figure 7 shows the results applied on the trimmed bi-streaming data, which delete the records, whose corresponding users requested less than 2 pages in the real data set. Similar to Figure 6, the clustering results of user behaviours are evaluated by Stability (a), Entropy (b) and Average length of objects (c). The window size of DDS model and EO model is set to a medium value 80,000.

In Figure 6 (a)(b) and Figure 7 (a), we see that the clustering stability based on DDS model is always better than that based on EO model. Figure 6 (c)(d As a conclusion from Figure 6 and Figure 7, DDS model preserves longer user behaviour patterns, guarantees better modeling of bi-streaming data and supports more stable and well-partitioned clustering results of user behaviours.

Clustering user behaviours by StrAP based on bi-streaming model

In the above section, we cluster the user behaviours by randomly selecting several steps due to the huge volume of data. In order to cluster the user behaviours on the whole streaming process, we employ an online clustering method called StrAP, as we introduced in section 5. Table 3 shows the comparison of the stability and entropy values of evaluating StrAP online clustering results based on DDS model and EO model. Instead of showing the curves of stability and entropy, we give the number of steps when the stability and entropy based on DDS model is larger (or smaller) than that based on EO model. To investigate the sensitivities of DDS and EO model w.r.t. the window size, the parameter wsize is set to various values from 40,000 to 120,000. Comparing the stability and entropy in Table 3, we see that DDS model has higher stability (second column) and lower entropy (fifth column) than EO model at most of the steps. We then can conclude that the DDS model supports better than EO model on clustering the user behaviours by online fashion. This conclusion is consistent with that we made in previous section 7. 1. We also see that DDS model is becoming better and better than EO model when the window size is increasing (the number of steps in the second and fifth column of Table 3 is increasing). This is because DDS model will take more transactions into account thus the users have more room and opportunity to accumulate their complete usage patterns when the window size increases.

Efficiency of clustering user behaviours based on bi-streaming model

For the large volume streaming data, the efficiency of processing is very important as it determines whether we can get a timely summarization and identify the useful patterns from the data. Figure 8 exhibits the running time of clustering user behaviours (using AP (a) and using StrAP (b)) on different models, the Batch, RO, DDS and reference model. The x-axis is the window size increasing from 10,000 to 120,000. Generally, the running time of clustering increases as the window size becomes larger. DDS model always runs faster than EO model in both Figure 8 (a) using AP and (b) using StrAP.

In Figure 8 (a), although batch model uses slightly less time than DDS model when the window size is small, DDS model works better than Batch model as the window size is increasing. This phenomena can be explained on two aspects. First, in DDS model we prefer the up-to-date objects to the out-of-date ones. Therefore there will be less objects in DDS model than in batch model. It then takes less time for the clustering. Second, batch model has to wait until the buffer is ready. By contrast, DDS model deals with new transactions on the fly. In total, all these results verify that clustering on DDS model is more efficient than clustering on EO model.

Conclusion

In this paper, we have investigated the problems of modeling and clustering a special type of streaming data -bi-streaming data. In order to summarize the bi-streaming data for clustering the users, we proposed three different models, the batch model, the EO model and the DDS model. Based on the models of bi-streaming data, clustering was carried out to discover user groups through employing a clustering method AP and an online clustering method StrAP. We tested the proposed models on a real-world data set which are the records of page request from mobile users of France Telecom. Experimental results showed that the DDS model outperformed the batch and EO models in both clustering quality and efficiency. Future work will be directed towards the classification and frequent pattern mining over bi-streaming data.

C1

  (a) is the streaming of user requested pages and (b)is the summary of navigation of each user Transaction T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 User Id C1 C4 C1 C2 C3 C4 C1 C2 C2 C4 C5 C6 Time t1 t1 t2 t3 t3 t3 t4 t4 t5 t6 t7 t7 Page A A C D B C H E F H B B

Fig. 1 .

 1 Fig. 1. Building Batch Model from the Bi-streaming Data

Fig. 2 .

 2 Fig. 2. Data Structure of Evolving Objects (EO) Model

Figure 2

 2 Figure 2 presents the data structure of EO model. Besides the transactions list and the map with user ID as the key, extra data structures are used to store the summarized items of each user.Building the evolving objects model includes the following steps:

Fig. 3 .

 3 Fig. 3. Evolving Objects (EO) Model

Fig. 4 .

 4 Fig. 4. Data Structure of the Dynamic Data Stream (DDS) Model

Fig. 5 .

 5 Fig. 5. Building DDS Model from the Bi-streaming Data

7. 1

 1 Clustering user behaviours by AP based on bi-streaming modelDue to the large volumes of the real-world data, we cannot afford to output all the clusters and validation details at each step. Instead, we randomly select several steps to evaluate the clustering results and details. From each bi-streaming model, we randomly select about 160-200 clusters and evaluate them by comparing with the reference model. As analyzed in section 4, the modeling results of the EO model and Batch models are the same. Hence, we will only compare the clustering results of DDS model and EO model with the reference model in the following experiments.

  ) and Figure 7 (b) show that the clustering results based on DDS model has lower entropy (better performance) than that based on EO model. Comparing the average length of objects obtained in DDS model, EO model and reference model shown in Figure 6 (e)(f) and Figure 7 (c), we find that DDS model preserves longer user behaviour patterns than EO model, and as expected has shorter patterns than the reference model that used 3 times more transactions.

Fig. 6 .

 6 Fig. 6. Evaluation of user behaviours clustering results in terms of Stability (a,b), Entropy (c,d) and Average length of objects (e,f), when AP was used on top of the DDS model and EO model applied on the real-world bi-streaming data of mobile users

Fig. 7 .

 7 Fig. 7. Evaluation of user behaviours clustering results in terms of Stability (a), Entropy (b) and Average length of objects (c), when AP was used on top of the DDS model and EO model applied on the trimmed bi-streaming data of mobile users with wsize=80,000

Fig. 8 .

 8 Fig. 8. Running time of clustering user behaviours based on different models, (a) using AP and (b) using StrAP

Figure 8 (

 8 Figure 8 (b) is the CPU time of using StrAP on different models. It should be noted that when AP is used for clustering the user behaviours, only several randomly selected steps are considered in both the DDS and batch model. Conversely, when StrAP is applied, the data managed by DDS model is always under processing; but the data managed by batch model is only processed at the end of each batch AP. Therefore, as shown in Figure 8 (b), StrAP costs more time on DDS model than that AP spends on Batch model.In total, all these results verify that clustering on DDS model is more efficient than clustering on EO model.

Table 2 .

 2 Memory cost of 3 candidate models

	Candidates memory for modeling memory for data Overall memory usage
	Batch	map size	data size	map size + data size
	EO	map size+data size	data size	map size + 2*data size
	DDS	map size	data size	map size + data size
	5 Clustering Users based on the Bi-streaming Model

Table 3 .

 3 Comparison of the stability and entropy of StrAP clustering results based on DDS model and EO model

		Stability: Number of steps	Entropy: Number of steps
	wsize S(DDS) > S(EO) S(DDS) < S(EO) E(DDS) > E(EO) E(DDS) < E(EO)
	40,000	140	49	60	129
	60,000	153	27	19	161
	100,000	145	13	7	151
	120,000	156	6	3	158

http : //en.wikipedia.org/wiki/Bounce rate

Average length of objects. The average length of objects shows the average number of accumulated patterns over all objects. A longer accumulated patterns means a more intact preservation and summarization of users' behaviours.