supD(s) ≥ minsup and that s respect all time constraints. Four types of constraints are proposed by Hirate and Yamana [14]. The constraints C1 and C2 are the minimum and maximum time interval required between two adjacent actionsets of a sequence (gap size). The constraints C3 and C4 are the minimum and maximum time interval required between the head and tail of a sequence. For example, for the sequence <(0, a), (1, b c), 
(2, d)>, the time interval between the head and the tail is 2 and the time interval between the actionset (0, a) and (1, b c) is 1. 

Hirate and Yamana [14] have proposed an extension of the PrefixSpan algorithm for the problem of GPSM. We present it below –with slight modifications- as it is the basis of our work. The algorithm finds all frequent time-extended sequences in a database ISDB that respect minsup, C1, C2, C3 and C4, by performing a depth-first search. The algorithm is based on the property that if a sequence is not frequent, any sequence containing that sequence will not be frequent. The algorithm proceeds by recursively projecting a database into a set of smaller projected databases. This process allows growing patterns one action at a time by finding locally frequents actions. In the following, the notation ISDB|(t,i) represents the time-extended database resulting from the operation of projecting a time-extended database ISDB with a pair 
(timestamp, item). ISDB|(t, i) is calculated as follow. 

ISDB((t,i)) ISDB|(t,i) := Ø. FOR each sequence σ=<(t1,X1),(t2,X2)…(tn,Xn)> of ISDB. FOR each actionset (tx,Xx) of σ containing i. 

 IF Xx/{i} = Ø 
 s :=<(tx+1-tx,ax+1), … (tn-tx,Xn)> 
 ELSE 
 s :=<(0, Xx/{i}), (tx+1-tx, ax+1), … (tn-tx, Xn)> 
 IF s ≠ Ø and s satisfies C1, C2 and C4 Add s to ISDB|(t,i). Return ISDB|(t,i). 

The Hirate-Yamana algorithm (described below) discovers all frequent time-extended sequences. algoHirate(ISDB, minsup, C1, C2, C3, C4) R := ø. 

 Scan ISDB and find all frequent items with support higher than minsup. FOR each frequent item i, Add (0, i) to R. algoProjection(ISDB|(0, i), R, minsup,C1,C2,C3,C4). RETURN R; 
algoProjection(ISDB|prefix, R, minsup, C1, C2, C3, C4) Scan ISDB|prefix to find all pairs of item and timestamp, denoted (t, i) satisfying minsup, C1 and C2. 