Bottleneck of Frequent-pattern Mining Multiple database scans are costly Mining long patterns needs many passes of scanning and generates lots of candidates To find frequent itemset ijiD.1100 of scans: 100 # of candidates:(100)+(10)+..+(10 2100 1=1.27*1030 Bottleneck: candidate-generation-and-test Can we avoid candidate generation February 4, 2021 Data Mining: Concepts and Techniques 24February 4, 2021 Data Mining: Concepts and Techniques 24 Bottleneck of Frequent-pattern Mining ◼ Multiple database scans are costly ◼ Mining long patterns needs many passes of scanning and generates lots of candidates ◼ To find frequent itemset i1 i2…i100 ◼ # of scans: 100 ◼ # of Candidates: (100 1 ) + (100 2 ) + … + (1 1 0 0 0 0 ) = 2100- 1 = 1.27*1030 ! ◼ Bottleneck: candidate-generation-and-test ◼ Can we avoid candidate generation?