Improving efficiency of Apriori

The basic Apriori algorithm is slow because it scans the database many times and generates and counts a huge number of candidate itemsets. Several techniques improve its efficiency.

1. Hash-based itemset counting (DHP): while counting 1-itemsets, hash every 2-itemset of each transaction into buckets of a hash table with bucket counts. A candidate 2-itemset whose bucket count is below min_sup cannot be frequent and is removed, which cuts C₂ greatly.
2. Transaction reduction: a transaction that contains no frequent k-itemset cannot contain any frequent (k+1)-itemset, so it is marked or removed from later scans.
3. Partitioning: divide the database into n partitions that fit in memory. Find the local frequent itemsets in each partition; any globally frequent itemset must be frequent in at least one partition. Only two scans of the database are needed (second scan counts the union of local frequent itemsets).
4. Sampling: mine a random sample with a lowered min_sup; verify with one scan of the whole database. It saves time but can miss some itemsets.
5. Dynamic itemset counting (DIC): add new candidate itemsets at any start point during a scan, once all their subsets are known to be frequent, to reduce the number of scans.
6. Vertical data format (Eclat): store the TID-list of each item and intersect TID-lists to get supports, so no repeated scans of the horizontal database are needed.
7. Pattern-growth (FP-growth): avoid candidate generation by using an FP-tree.
8. Also: higher min_sup, better data structures (hash trees for candidate counting), and parallel/distributed implementation.