# Understanding SON algorithm - partition based Frequent itemsets mining

There are several variants of the Apriori algorithm that focus on improving efficiency. For example, the base idea of the SON algorithm is to partition the database D into n partitions. The SON algorithm has several steps:

• In phase I each partition pi generates local itemsets of all lengths as the output Li1,Li2, ... ,Lil.
• In merge phase the local itemsets of same lengths from all n partitions are combined to generate the global candidate itemsets.
• In phase II algorithm counts support value of each candidate and generates the global itemsets.

Ussually each partition has its own local mininal support value and is defined by min_support * number_of_transaction_in_partition, where min_support is minimal support threshold for transactions in D.

Now we take an example D and divide transactions into n=2 partitions. Global minimal support for Database D is min_support=2. Local minimal support for each partition will be local_min_support=2*4.

Database D
| TID  |   List of itemsets |
|------| ------------------ |
|  T1  |  I1, I2            |
|  T2  |  I3, I4            |
|  T3  |  I1, I5            |
|  T4  |  I2, I6            |

|  T5  |  I1, I2            |
|  T6  |  I3, I4            |
|  T7  |  I1, I7            |
|  T8  |  I2, I8            |

C1 table for partition 1 (local_min_support=2*4)
| Itemset  |   Support count|
|------    | -------------- |
|  I1      |  2             |
|  I2      |  2             |
|  I3      |  1             |
|  I4      |  1             |
|  I5      |  1             |
|  I6      |  1             |

C1 table for partition 2 (local_min_support=2*4)
| Itemset  |   Support count|
|------    | -------------- |
|  I1      |  2             |
|  I2      |  2             |
|  I3      |  1             |
|  I4      |  1             |
|  I7      |  1             |
|  I8      |  1             |


As you can see, the minimum local support in each partition is too high and the frequence 1-itemsets for each partition is empty. However, the frequency 1-itemsets in the database D with min_support=2 is not empty.

Can you please tell me what am I doing wrong?

I also find, that local minimum support is local_min_support=(1/n)*min_support. In this case this local minimal support will work, but in general still not. For example imagine you have Database D where n = 2 and min_support = 10. Then local minimum support for each partition becomes 10/2 = 5. Now we assume that the support_count of an item in partition1 and partition2 is 4 and 4, respectively. Because both support counts in partitions are smaller than locale min support go away, although they are frequent item sets in database D.