Frequent Itemset Generation Strategies Reduce the number of candidates(M) Complete search M=2d Use pruning techniques to reduce M Reduce the number of transactions(N Reduce size of n as the size of itemset increases Reduce the number of comparisons(NM) Use efficient data structures to store the candidates or transactions No need to match every candidate against every transaction O Tan, Steinbach, Kumar Introduction to Data Mining 4/18/2004© Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 ‹#› Frequent Itemset Generation Strategies Reduce the number of candidates (M) – Complete search: M=2d – Use pruning techniques to reduce M Reduce the number of transactions (N) – Reduce size of N as the size of itemset increases Reduce the number of comparisons (NM) – Use efficient data structures to store the candidates or transactions – No need to match every candidate against every transaction