## 5 Proposed Method
### Step 1.2  
Once we have identified in the previous step the most frequent cell sets in trajectories, we can proceed to process the data by reversing the roles of items and bags in the Apriori algorithm. In this case, we will consider that trajectories correspond to items and geographical cells correspond to bags. In this way, at the end we will get the most frequent trajectory sets, that is, the sets of trajectories that share at least a given number of cells. This procedure can be described as follows:  
* The algorithm starts by first identifying all the individual trajectories which satisfy the minimum support, that is, those which are at least \(M\) cells long (\(M\) corresponds to the \(min\_sup\) parameter of the Apriori algorithm, one of the parameter of the corridor): this is the set \(L_{1}\). * From the elements of \(L_{1}\) with the Join step the set \(C_{2}\) is formed, correponding to all possible pairs of trajectories (candidate pairs of trajectories). Candidates are the itemsets containing all potentially frequent itemsets. Figure 3: Trajectories mapping into a grid with cells of 1300 m per side. * To form \(L_{2}\) the algorithm does the pruning, considering among the pairs of \(C_{2}\) only those that satisfy the \(min\_sup\) of cells (2-frequent trajectories). * By increasing the number of trajectories at each \(K^{th}\) iteration (\(K\geq 2\)) of Apriori, it generates candidate \(K\)-trajectories \(C_{K}\) from the frequent \((K-1)\)-itemsets \(L_{K-1}\) of the last iteration. Now only the frequent sets \(L_{K-1}\) and candidates \(C_{K}\) reside in memory, whereas other itemsets of previous iterations are discarded. * The algorithm stops at job \(K\) when it is no longer possible to find a set of frequent trajectories of size \(K+1\), (that is, when there are no \(K+1\) trajectories which cross at least \(M\) cells together). Compared to the previous step, in this step we fixed the desired minimum length of the corridors in terms of cells. Given that, the Apriori algorithm finds sets of trajectories that share at least a minimum number of cells. In the GeoLife case, this step consists of the application of the Apriori algorithm on a grid of 500 m (102 \(\times\) 96 cells), but turning the problem upside down: seeing the cells as baskets and the trajectories as items. By setting the minimum support parameter equal to 51 cells (which make a total length of 51 \(\times\) 500 m = 25.5 km ) and taking into account that the \"populated\" cells in the first slot, for example, are 4603 (cells crossed by trajectories), we have obtained a percentage of support greater than that of Step 1. Since we only considered the last level of the output of the Apriori algorithm, in this step we turned to analyze the subsets of cells that dot not appear in the last result of Apriori: the trajectories which do not participate in frequent itemsets of the longest cells. In addition, to optimize the execution time and vary the results, instead of using all the trajectories each time, we considered a subset of 1000 random trajectories. We chose to build a grid of cells 1 km wide, so the total number of cells are 51 (horizontal) \(\times\) 48 (vertical). We applied Apriori by following this convention: the role of \"baskets\" is played by trajectories and the role of \"itemsets\" is played by cells. As for the input of Apriori we chose a minimum support of 50 trajectories on the total number of the random set: the support of a cell is the percentage of trajectories in which that cell occurs. This support threshold being greater than the one chosen for Step 1 and Step 1.2 leads to an improvement in the execution time of the algorithm. In fact, the output in this case is the tuples of cells shared by at least 50 trajectories and so there are less candidate corridors that contain 50 subtrajectories compared to Step 1 where the minimum support was 15. Moreover, the reduction in the number of the sample of trajectories also contributes to bringing this advantage.