# Trajectory Clustering and k-NN for Robust Privacy Preserving Spatiotemporal Databases
## 2 Materials and Methods
### System Model  
We consider \(N\) mobile users in \(\Re^{2}\). The configuration space, namely, the environment that objects are moving, may be the free space or a road network (constrained or unconstrained) [3]. In our case, we considered unconstrained road network, as described in Section 2.4, where mobile users are densely distributed and do not develop high speeds [12]. We excluded national or international road networks, since we cannot assume that users are moving with linear velocity on these networks. Each \((x_{i}^{j},y_{i}^{j})\) represents the position (Cartesian coordinates) of the mobile user \(j\) in time-stamp \(t_{i}^{j}\) or point \(i\) of its trajectory \(j\)[3]. For each point \(i\) in trajectory \(j\), we define in four-dimensional space a vector \(D_{i}^{j}=(x_{i}^{j},y_{i}^{j},g_{i}^{j},v_{i}^{j})\), \(i=1,2,\ldots,L\), which is described by the location coordinates \((x,y)\) and motion pattern \((g,v)\), respectively. For the first point of each trajectory, direction and velocity are defined with respect to point \((0,0)\). We approach the problem of privacy preserving on spatiotemporal databases with two methods. The first one is called Method-Without-CLustering (MWCL, Algorithm 3) and the second one is called Method-with-CLustering (MCL, Algorithm 4). In the latter, we apply on-line clustering, i.e., in each time-stamp \(t\), we group into clusters the mobile users based on their vector values \(D_{i}^{j}\) that moment. This vector is formulated depending on which of the following attributes \(x,y,g,v\), we choose to apply K-means and \(k\)-NN algorithms. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Objid** & **Time Instant** & **knns Indexes** \\ \hline
1 & 1 & \([id_{111},id_{112},\ldots,id_{11k}]\) \\
1 & 2 & \([id_{121},id_{122},\ldots,id_{12k}]\) \\
1 & 3 & \([id_{131},id_{132},\ldots,id_{13k}]\) \\
1 & 4 & \([id_{141},id_{142},\ldots,id_{14k}]\) \\
1 & 5 & \([id_{151},id_{152},\ldots,id_{15k}]\) \\
2 & 1 & \([id_{211},id_{212},\ldots,id_{21k}]\) \\
2 & 2 & \([id_{221},id_{222},\ldots,id_{22k}]\) \\
2 & 3 & \([id_{231},id_{232},\ldots,id_{23k}]\) \\
2 & 4 & \([id_{241},id_{242},\ldots,id_{24k}]\) \\
2 & 5 & \([id_{251},id_{252},\ldots,id_{25k}]\) \\... &... &... \\... &... &... \\ N & 1 & \([id_{N11},id_{N12},\ldots,id_{N1k}]\) \\ N & 2 & \([id_{N21},id_{N22},\ldots,id_{N2k}]\) \\ N & 3 & \([id_{N31},id_{N32},\ldots,id_{N3k}]\) \\ N & 4 & \([id_{N41},id_{N42},\ldots,id_{N4k}]\) \\ N & 5 & \([id_{N51},id_{N52},\ldots,id_{N5k}]\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: \(k\)-anonymity sets for \(N\) mobile users in \(L=5\) time-stamps. ```
1:Input:the number of \(k\) nearest neighbors, the number of mobile users \(N\), vectors \(D_{i}^{j}\) of \(N\) users in \(L\) time-stamps
2:Output:\(k\) nearest neighbors indexes of \(N\) users in \(L\) time-stamps
3:for\(i=1:L\)do
4:for\(J=1:N\)do
5: Compute vector \(D_{i}^{j}\) of user \(j\) in time instant \(i\)
6: Apply \(k\)-NN between the vector \(D_{i}^{j}\) and the vectors \(\{D_{i}^{j}\}_{j=1}^{N}\) of all users to find the set of \(k\)-NN indexes, \(I_{i}^{j}\), of user \(j\) in time-stamp \(i\)
7:endfor
8:endfor
```  
**Algorithm 3** MWCL. We define a location data security metric, which we call vulnerability. Vulnerability quantifies and measures the robustness of each method. Specifically, it expresses the rate with which \(k\) nearest neighbors of each mobile user changes. The vulnerability of each method is computed as the mean value of vulnerabilities of all users in \(L\) time-stamps. The less the neighbor indexes change (e.g., objd), the lower the value vulnerability takes. Suppose a collection of trajectories \(T=\{T^{1},\ldots,T^{N}\}\) (trajectories database) of equal length \(L\). Each trajectory consists of a sequence of time ordered positions a mobile user goes through as it moves from a start point to a specific destination. It is a vector of the form  
\[T^{j}=\{(x_{1}^{j},y_{1}^{j},t_{1}^{j}),(x_{2}^{j},y_{2}^{j},t_{2}^{j}),\ldots, (x_{L}^{j},y_{L}^{j},t_{L}^{j})\}.\]  
**Definition 5**.