are guaranteed to not produce any closed sequences (see [16] for further information). 

The BackScan pruning has the advantage of often increasing the time performance over regular SPM algorithms such as PrefixSpan [16]. Because of limited space, the reader is invited to refer to [16] for more details on the BIDE algorithm. 

## 7 Extending Sequential Pattern Mining With Context Information

A fourth limitation that we encountered when applying the PrefixSpan algorithm is that it does not consider the context of each sequence. In a tutoring system context, it would be useful, for instance, to annotate sequences with success information and the expertise level of a user and to mine patterns containing this information. Our solution to this issue is to add dimensional information to sequences. Pinto et al. [12] originally proposed Multi-dimensional Sequential Pattern Mining (MDSPM), as an extension to SPM. A Multidimensional-Database (MD-Database) is defined as a sequence database having a set of dimensions D={D1, D2,… Dn}. Each sequence of a MDDatabase (an MD-Sequence) possesses a symbolic value for each dimension. This set of value is called an MD-Pattern and is noted {d1, d2… dn}. For example, consider the MD-Database depicted in the left part of figure 5. The MD-Sequence 1 has the MDPattern {"true", "novice"} for the dimensions "success" and "expertise level". The symbol "*", which means any values, can also be used in an MD-Pattern. This symbol subsumes all other dimension values. An MD-Pattern Px={dx1, dx2… dxn} is said to be contained in another MD-Pattern Py={dy1, dy2… dym} if there exists integers 1 ≤ i1 < i2
< … in ≤ m such that dx1 ⊆ dy1, dx2 ⊆ dy2 , . . . , dxn ⊆ dyn. The problem of MDSPM 
is to find all MD-Sequence appearing in a database with a support higher than *minsup*. Figure 5 shows an MD-Database with time information and some patterns that can be extracted from it, with a *minsup* of 2 sequences. 

| An MD-Database                                                                        | Mined MD-Sequences                                                                            |                                                                  |                                                             |           |
|---------------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------|------------------------------------------------------------------|-------------------------------------------------------------|-----------|
| ID                                                                                    | Dimensions                                                                                    | Sequences                                                        | Dimensions                                                  | Sequences |
| true, novice  true, expert  false, novice  false, interm.  true, novice  true, expert | <(0,a),(1,bc)>  <(0,d) >  <(0,a),(1,bc)>  <(0,a),(1,c), (2,d)>  <(0,d), (1,c)>  <(0,c), (1,d) | *, novice,  *, *  *, novice  true, *  true, novice  true, expert | <(0,a)>  <(0,a)>  <(0,a), (1,b)>  <(0,d)>  <(0,c)>  <(0,d)> |           |
| Æ                                                                                     |                                                                                               |                                                                  |                                                             |           |

Pinto et al. [17] proposed three algorithms for MDSPM. The first one cannot be applied in combination with the Hirate-Yamana algorithm, as it required embedding dimensions as additional actions in sequences. The two other algorithms, SeqDim and DimSeq are based on the idea that the problem of MDSPM can be broken in two steps: 
finding sequential patterns with an algorithm such as PrefixSpan, and finding MDPatterns with an itemset mining algorithm such as Apriori [18, 19]. The first algorithm, SeqDim is executed as follow. First, frequent sequences are found by SPM. Then, for each sequence, the containing MD-Sequences are used to mine frequent MD-Patterns 