Association Rules

• Clearly the space of all association rules is exponential
• However, exploit sparseness when Ts and Tc are set “high”
• Under certain conditions, all rules can be found in NEAR LINEAR TIME (a surprising property).
• Exploit structure of rules and threshold settings to prune space top-down
• if R2 is more specific than R1: then support decreases monotonically.

---