Exercise 26.6 Let us develop a new algorithm for the computation of all large itemsets. Assume that we are given a relation D siInilar to the Purchases table shown in Figure 26.1. We partition the table horizontally into kparts D1 , ... , Dk .

1. Show that, if items et X is frequent in D, then it is frequent in at least one of the k parts.

2. Use this observation to develop an algorithm that computes all frequent item sets in two scans over .D. (Hint: In the first scan, compute the locally frequent itemsets for each part Di, i E{I,...,k}.)

3. Illustrate your algorithm using the Purchases table shown in Figure 26.1. The first partition consists of the two transactions with transid 111 and 112, the second partition consists of the two transactions with transid 113 and 114. Assumne that the minimum support is 70 percent.

transidcusti 201 201 date item gty 5/1/99 en 99 ink 1 111 201 5/1/99 milk 3 ?11 | 201 | 5/1/99 | juice l en 112 105 6/3/99 ink1 106 5/10/99 pen 1 201- nl 113 113 | 106 | 5/10/99 | Inilk | 1- 114 114 en ink 2 uice 201 114 20 6/1/99 water 1 Figure 26. The Purchases Relation transidcusti 201 201 date item gty 5/1/99 en 99 ink 1 111 201 5/1/99 milk 3 ?11 | 201 | 5/1/99 | juice l en 112 105 6/3/99 ink1 106 5/10/99 pen 1 201- nl 113 113 | 106 | 5/10/99 | Inilk | 1- 114 114 en ink 2 uice 201 114 20 6/1/99 water 1 Figure 26. The Purchases Relation