Partitioning Technique for Frequent Itemset Generation

1. Principle

The partition algorithm (Savasere, Omiecinski and Navathe) avoids the repeated database scans of Apriori by splitting the database into pieces that fit in main memory and scanning the data only twice.

Phase 1 - local mining (one pass, partition by partition):

1. Divide the transaction database $D$ into $n$ non-overlapping partitions $D_1, D_2, \dots, D_n$, each small enough to fit in memory.
2. In each partition $D_i$, find the itemsets whose support in that partition is at least $minsup \times |D_i|$ (using Apriori or a hash tree, entirely in memory).
3. Take the union of all locally frequent itemsets as the candidate set $C^*$ for Phase 2.

Why no globally frequent itemset is missed: if an itemset $X$ were infrequent in every partition, then

$$count_i(X) < minsup \cdot |D_i| \ \ \forall i \ \Longrightarrow \ \sum_i count_i(X) < minsup \cdot \sum_i |D_i| = minsup \cdot |D|$$

so $X$ would also be globally infrequent. Contrapositively, every globally frequent itemset must be frequent in at least one partition - Phase 1 cannot drop a true frequent itemset (no false negatives).

Phase 2 - global counting (one single pass over the whole DB): scan $D$ once, count the support of each candidate in $C^*$, and keep only those whose total support is at least $minsup \times |D|$. These are the globally frequent itemsets.

Partition the database D into D1, D2, ..., Dn
for each partition Di:
    find locally frequent itemsets (support >= minsup * |Di|)
    C* = union of all locally frequent itemsets
scan the whole database once:
    count support of every candidate in C*
    L = { X in C* : support(X) >= minsup * |D| }

2. Why it is more efficient than the Apriori algorithm

1. Only two passes over the data, no matter how long the frequent itemsets are; Apriori needs one full scan per level ($k+1$ scans for itemsets of size $k$) plus candidate generation/pruning at every level.
2. Phase 1 works in memory on a small partition, so expensive candidate-set handling and repeated disk I/O of the whole database are avoided.
3. Parallelism and scalability: partitions can be processed simultaneously on different processors, and a database larger than memory can be handled because only one partition is resident at a time.
4. Candidate set $C^*$ is generally much smaller than the level-wise candidate set of Apriori, so the single counting pass in Phase 2 is cheap.

Trade-off: the union of local frequent itemsets may contain a few globally infrequent itemsets (false positives), which Phase 2 filters out; this is a small price for cutting the number of full database scans from many to two.