SPAM traverses candidate sequences as defined by a lexicographic sequence tree.
Each sequence in this tree can be considered as either a sequence-extended sequence or as an itemset-extended sequence.
A sequence-extended sequence is generated by adding a new transaction consisting of a single item to the end of its parent’s sequence in the tree.
An itemset-extended sequence is generated by adding an item to the last itemset in the parent’s sequence, such that the item is greater than any item in that last itemset.
We refer to the transitions from a parent to sequence-extended and itemset-extended sequences as S-steps and I-steps respectively.