Depth-First Tree Traversal

• 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.

Slide Links:

Slide Comments: