## 3 The Optimized Agglomerative Approach
### Optimization on Traditional Agglomerative Approach
```
/*Phase 1 - Initialization*/
1:while not end of the database file
2: read the next transaction \(t\);
3:\(c_{i}\)\(\leftarrow\)\(t\); \(V\)\(\leftarrow\)\(c_{i}\);
4:endwhile /*Phase 2 - Iteration*/
5:do
6:\(\mathit{merged}\)=false; \(\mathit{GM}\)=0;
7:for\(i\)=0 to \(V\).size
8:for\(j\)=\(i\)+1 to \(V\).size
9:if(D\({}_{i}\)\(>\)\(\mathit{GM}\))
10:\(\mathit{GM}\)=D\({}_{i,j}\); clear(\(E\)); \(E\).add(\(i,j\));
11:\(\mathrm{clear}(\mathit{c}_{i}\overline{L}\) ); \(c_{i}\overline{L}\).add(\(j\)) ;
12:\(\mathrm{clear}(\mathit{c}_{j}\overline{L}\) ); \(c_{j}\overline{L}\).add(\(i\)) ;
13:else if(D\({}_{i}\)\(\
eq\)\(\mathit{GM}\))
14:\(E\).add(\(i,j\)); \(c_{i}\overline{L}\).add(\(j\)) ; \(c_{j}\overline{L}\).add(\(i\)) ;
15:endif
16:endfor
17:endfor
18:if(\(E\).size\(>\)0)
19:for each distinct \(c\) in \(E\)
20:\(\mathrm{Link}\)Merge(\(c\));
21:End For
22:\(\mathrm{clear}(E)\); \(\mathrm{clear}(M)\); \(\mathit{merged}\)=true;
23:endif
24:while(\(\mathit{merged}\))
```  
**Algorithm 1**Agg-CLOPE  
The implementation of Agg-CLOPE is listed in Algorithm 1. Similar to CLOPE, this algorithm also contains two phases. In the initialization phase, each transaction is read and placed into its own cluster to form vertices in \(G\) (Lines 1-4). In the iteration phase, the delta values are calculated between each two clusters. Each calculation performs a comparison to the current _GM_ value (Line 9 and Line 13). The content in \(E\) and current cluster's \(\overline{L}\) is cleared and renewed as the _GM_ value is assigned to the current maximum delta value (Lines 10-12), otherwise the current edge is appended in \(E\) and the current vertices are added to the opponent's \(\overline{L}\) (Line 14). If \(E\) is not empty, all the connective sub-graphs of G would be merged (Lines 18-23). Note that the main part of merge operation is done by LinkMerge, a recursive function shown in Algorithm 2. Agg-CLOPE would automatically terminate until no clusters to be merge, _i.e._, \(E\) is empty. Suppose the total number of transactions is \(N\), the current number of clusters is \(K\) and the average length of a transactions is \(A\). Obviously the initialization phase takes O(_N_) time. In the iteration phase, the calculation of delta values requires O(\(\frac{K\times K\times A}{2}\)) time, and the recursive function is O(_K_) that is the same as depth first search on graph \(G\). As \(K\) = \(N\) in the first round, it requires at least O(\(\frac{N^{2}\times A}{2}\)) + 2O(_N_), then the \(K\) value gradually shrinks in the next few rounds. The worst case would take \(N\) - 1 rounds, in each of which only two clusters are merged, resulting in O(\(\frac{N^{3}\times A}{3}\)) approximately. The best case takes only two rounds, where all the clusters are merged in the first round and no further operations are performed in the second round. However, compared with the time complexity of CLOPE-O(\(N\times K\times A\)), Agg-CLOPE is generally much slower to be its only and fatal defect. ```
0:\(c\) is a cluster(vertex) in cluster graph \(G\)
1:If(\(c\) is not merged)
2:for each \(k\) in \(c\). \(\overline{L}\)
3: LinkMerge(\(c_{k}\));
4:End For
5:End If
```  
**Algorithm 2** LinkMerge