[SOUND]. Now I am going to introduce you another algorithm called SPADE, which is sequential pattern mining based on vertical data format. You probably still remember the vertical data format based frequent pattern mining algorithm called ECLAD. Here for the same set of authors, they actually develop an interesting algorithm for sequential pattern mining. Okay. The idea is pretty simple. If you take the Sequence, you do a little detailed study, you get a Sequence ID, Element ID, and set of Items. So, what you can see is, for the first Sequence ID, 1. Element ID 1, you find item a. Element ID 2, you find a, b, c so on, okay. Then we can transform this into vertical format. That means we just look at the, where a occurs and where the b occurs. So the a occurs, you probably can see, it happens in Sequence 1, ElementID 1. In Sequence 1, Element 2, and also Sequence 1, Element 3. So you get this one the same. You can get Sequence ID 2, 3, 4. Similarly for b, you can find where the b comes, is Sequence 1, Element 2. So you get 1, 2. Then how we can combine them into frequent sequences, like a then b, or b then a. If you say a then b, you, you will be requiring a is in front of b, or a's Element ID is in front b's Element ID. That means for the same Sequence ID 1, if EID 1 is smaller than EID 2 of b, then you get 1 Sequence E ab. Similarly, for b then a, what you get is these Element ID of b should be smaller than Element ID of a. For the same reason you can get all of them for the lines 2, okay. So for lines 3 what you need is, you just get lines 2 frequent 1s. Then you do drawing. How do you do drawing? You probably can see these Element ID Sequence ID should be the same. The Element ID, this b shared with this b, they are both 2. So you can join them together, you get 1, 2, 3 here. And you join the other together, you can get a 1, 3, 4 because it, Element 2, you get a, you get a b, you can get a again. So, the two lines and you actually can find all of them, okay. So that's a reason you can use Apriori based principle to find all the frequent subsequences. This algorithm was developed by Zaki in 2001 called SPADE. It's Sequential Pattern Discovery using Equivalent Class. [MUSIC]