Depth-First Tree Traversal (cont.)

• SPAM uses both S-step and I-step pruning to reduce the search space.

• Suppose we are currently at the node for sequence ({a}) and can reach sequences ({a},{a}),({a},{b}),({a},{c}) by S-steps. If it turns out that ({a},{c}) is not frequent, we know by the Apriori principle that ({a},{a},{c}), ({a},{b},{c}), ({a},{a,c}), and ({a},{b,c}) all cannot be frequent. We term this pruning mechanism S-step pruning.

• Likewise, we can reach ({a,b}) and ({a,c}) via I-steps from ({a}). If ({a,c}) is not frequent, then ({a,b,c}) must also not be frequent by the Apriori principle. We term this I-step pruning.

Slide Links:

Slide Comments: