Data Mining: The Textbook

Partition’s recursive tid list intersection approach. Eclat is a lattice-partitioned memory-optimization of the algo-

• 
  Strictly speaking, Monet is the name of the vertical database, on top of which this (unnamed) algorithm was built.
  

112 CHAPTER 4. ASSOCIATION PATTERN MINING

Algorithm VerticalApriori(Transactions: T , Minimum Support: minsup) begin

k = 1;
F₁ = { All Frequent 1-itemsets };
Construct vertical tid lists of each frequent item; while F_k is not empty do begin
Generate C_k+1 by joining itemset-pairs in F_k;
Prune itemsets from C_k+1 that violate downward closure; Generate tid list of each candidate itemset in C_k+1 by intersecting
tid lists of the itemset-pair in F_k that was used to create it; Determine supports of itemsets in C_k+1 using lengths of their tid lists; F_k+1= Frequent itemsets of C_k+1 together with their tid lists; k = k + 1;

end;
return(∪^k F );

_{i=1 i}
Figure 4.7: The vertical Apriori algorithm of Savasere et al. [446]
rithm in Fig. 4.7. In Eclat [537], an independent Apriori-like breadth-first strategy is used on each of the sublattices of itemsets with a common prefix. These groups of itemsets are referred to as equivalence classes. Such an approach can reduce the memory requirements by partitioning the candidate space into groups that are processed independently in con-junction with the relevant vertical lists of their prefixes. This kind of candidate partitioning is similar to parallel versions of Apriori, such as the Candidate Distribution algorithm [54]. Instead of using the candidate partitioning to distribute various sublattices to different processors, the Eclat approach sequentially processes the sublattices one after another to reduce peak memory requirements. Therefore, Eclat can avoid the postprocessing overheads associated with Savasere et al.’s data partitioning approach, if the database is too large to be processed in core by