GSP algorithm

F1 = the set of frequent 1-sequence k=2, do while Fk-1 != Null; Generate candidate sets Ck (set of candidate k-sequences); For all input sequences s in the database D do Increment count of all a in Ck if s supports a End do Fk = {a ∈ Ck such that its frequency exceeds the threshold} k = k+1; End do Result = Set of all frequent sequences is the union of all Fk's The above algorithm looks like the Apriori algorithm. One main difference is however the generation of candidate sets. Let us assume that: ::A → B and A → C are two frequent 2-sequences. The items involved in these sequences are (A, B) and (A,C) respectively. The candidate generation in a usual Apriori style would give (A, B, C) as a 3-itemset, but in the present context we get the following 3-sequences as a result of joining the above 2- sequences ::A → B → C, A → C → B and A → BC The candidate–generation phase takes this into account. The GSP algorithm discovers frequent sequences, allowing for time constraints such as maximum gap and minimum gap among the sequence elements. Moreover, it supports the notion of a sliding window, i.e., of a time interval within which items are observed as belonging to the same event, even if they originate from different events. ==See also==