# Trajectory Clustering and k-NN for Robust Privacy Preserving Spatiotemporal Databases
## 2 Materials and Methods
### System Model
It was shown that an increasing dimensionality makes the data resistant to effective privacy and achieve the lower bound of \(k\)-anonymity, i.e., \(\frac{1}{k}\). However, in practice, we showed that some of the attributes of real data can be leveraged to greatly ameliorate the negative effects of the curse of dimensionality in privacy. To obtain an even more accurate classification, we considered two more attributes in computations, the angle and velocity. However, it is doubt if we can obtain a perfect classification by carefully defining a few of these features. In fact, after a certain point, which in our case was (\(x\),\(y\)) attributes, increasing the dimensions of the problem, by adding new features, degraded the performance of \(k\)-NN classifier. As shown in the following figures, as the dimensionality increased, the vulnerability performance, computed by Algorithm 5, improved until the optimal number of features was reached, i.e., 2. Further increasing of the dimensionality did not ameliorate vulnerability performance. In the following figures, we present the same procedure as previously, but considering a larger dataset of size \(N=2000\) trajectories. From cluster number perspective, the number of clusters \(cs\) obviously affected only MCL (Method-with-CLustering), where we see that vulnerability became a little worse as the clusters increased. This relates with the fact that, not only the average cluster size reduced but also their composition changed, and, thus, MCL (Method-with-CLustering, Algorithm 4) became more sensitive to the change of the nearest neighbors of mobile users inside the cluster. Focusing on the last combination of attributes of both experiments (see Figures 8 and 9), we observed that attributes suppression, in terms of \(k\) nearest neighbors indexes computation, made MCL (Method-with-CLustering, Algorithm 4) superior in terms of vulnerability (that is, lower values), \begin{table}
\begin{tabular}{c c c c} \hline \(cs\) & \(k\) & Clustering Attributes & \(k\)-NN Attributes \\ \hline
5,10 & 15 & \(x\) & \(x\) \\
5,10 & 15 & \(x,y\) & \(x,y\) \\
5,10 & 15 & \(x,y,g\) & \(x,y,g\) \\
5,10 & 15 & \(x,y,g,v\) & \(x,y,g,v\) \\
5,10,15 & 15,30 & \(x,y,g,v\) & \(x,*,*,*\) \\ \hline \end{tabular}
\end{table} 
Table 4: Parameters for the second experiment of \(N=2000\) trajectories. \begin{table}
\begin{tabular}{c c c c} \hline \(cs\) & \(k\) & Clustering Attributes & \(k\)-NN Attributes \\ \hline
2,5 & 5 & \(x\) & \(x\) \\
2,5 & 5 & \(x,y\) & \(x,y\) \\
2,5 & 5 & \(x,y,g,v\) & \(x,y,g,v\) \\
2,5,10 & 5 & \(x,y,g,v\) & \(x,*,*,*\) \\ \hline \end{tabular}
\end{table} 
Table 3: Parameters for the first experiment of \(N=400\) trajectories. which is the main issue in \(k\)-anonymity and thus in privacy preserving. Moreover, it is the combination that highlights MCL (Method-with-CLustering, Algorithm 4) as the clusters number increases. The fact that clustering is based on all available attributes empowers cluster homogeneity and reflects better the real word communities. More to the point, when the mobile users were camouflaged by \(k\) nearest neighbors based on one of the attributes, in that case \(x\), it is disclosed less information about them and their neighbors. Therefore, it is more difficult to break security, even if an intruder monitors history data and tries to link \(k-1\) public records of nearest neighbors. This case keeps vulnerability in relatively high level for low values of \(k\). It is obvious that, the more nearest neighbors are used to camouflage the mobile users inside the cluster, the lower the vulnerability becomes. In addition, in terms of computation cost, \(k\)-NN is more time effective when applied to less volume (inside cluster) and fewer dimension data. Moreover, we avoid the dimensionality effect in classification and, thus, in \(k\)-NN performance. Finally, in Figures 8 and 9, we also demonstrate the impact of parameter \(k\) in vulnerability (see Algorithm 5). We observed that increasing \(k\) benefited both methods.