An Hash tree stores all candidate k-itemsets and their counts. The root is empty and its children are the frequent 1-itemsets. Any node at depth = k will denote and frequent k-itemset. An example for an hash tree for C2 = 12, 13, 15, 23, 25, 35 is shown below
An internal node v at level m contains, bucket pointers. These tell which branch is the next one to be traversed. The hash of the mth item is used to decide this.
Only the frequent k-1 itemsets, who have common parents should be considered for the joining step. So checking all k-1 itemsets in Lk-1is avoided.
To determine if a k-1 itemset is frequent, we have to look only for those itemsets who have common parents, and thus avoid going through all k-1 itemsets in Lk-1.
 |
Enumeration is replaced by tree traversal, i.e. there is no need to enumerate all k-subsets of transactions. Such considerations are limit by tree traversal. |