# Trajectory Clustering and k-NN for Robust Privacy Preserving Spatiotemporal Databases
## 2 Materials and Methods
### Problem Definition  
We studied the problem of privacy preserving considering spatiotemporal databases of \(N\) records with \(d\) attributes each. The spatiotemporal data are the location data of a number of mobile users along with the time-stamp of each position, as shown in Table 1. Through SMaRT system, we have in our disposal trajectory data, which give us information about angle direction and velocity amplitude. Therefore, for each record, i.e., mobile user, we know the values of four attributes. We employ a popular anonymization approach, called \(k\)-anonymity, such that any organization or adversary can deduce information about the mobile user identity by observing its location attributes. With \(k\)-anonymity, attributes can be suppressed, namely their values can be replaced by \"*\", or generalized [13] until each row is identical with at least \(k-1\) other rows. At this point, the database is said to be \(k\)-anonymous and, thus, prevents database linkages. In our case, we select to anonymize location data attributes by employing a classification method that enables us to construct the \(k\)-anonymity set of each user per time-stamp. The rationale behind anonymity preserving lies in the preserving of the \(k\) nearest neighbors from one position to another. To this end, we investigated the problem considering two approaches. In the first approach, the anonymization is handled as a clustering problem, in which the \(d\)-dimensional space of attributes is partitioned into homogeneous groups so that each group contains at least \(k\) records, namely the minimum number of records in a cluster, to satisfy \(k\)-anonymity. To achieve it, as a first approach, which will be elaborated in the future, we adopt the K-means clustering method. The \(k\)-anonymity set of each user is formed based on the cluster it belongs to. In the second approach, the anonymity set is formed again by the \(k\) nearest neighbors indexes but without considering \(d\) attributes space partitioning. The maximum number of clusters is \(K=\lfloor\frac{N}{k}\rfloor\), where \(N\) is the total number of records in the dataset and \(k<<N\) is the anonymity parameter for \(k\)-anonymization. For \(L\) trajectory points, which correspond to \(L\) time-stamps, we compute for each mobile user, \(i\) its \(k\) nearest neighbors indexes and record them in a vector of the form \(k_{nn}s_{it}=[id_{it1}id_{it2}\ldots id_{itk}]\) for \(t=1,2,\ldots,L\). An example of such sets for \(N\) mobile users is shown in Table 2. For each user, we measure how many of the \(k\) nearest neighbors remained the same from one position to another. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Objid** & **Time-Stamp** & **Time to Next, Point** & **x** & **y** & **Angle** & **Velocity** \\ \hline
1 & 2013-03-09 10:00:01 & 0 & 21,082 & 56,436 & 1.23 & 0 \\
1 & 2013-03-09 10:00:04 & 3 & 21,099 & 56,432 & 1.16 & 4.5 \\
1 & 2013-03-09 10:00:11 & 7 & 21,221 & 56,484 & 1.51 & 14.6 \\
1 & 2013-03-09 10:00:19 & 8 & 21,331 & 56,524 & 1.95 & 11.3 \\
1 & 2013-03-09 10:00:21 & 2 & 21,402 & 56,495 & 0 & 29.5 \\
2 & 2013-03-09 10:00:03 & 0 & 35,587 & 59,829 & \(-\)2.76 & 0 \\
2 & 2013-03-09 10:00:08 & 5 & 35,568 & 59,782 & 2.94 & 7.8 \\
2 & 2013-03-09 10:00:16 & 8 & 35,580 & 59,723 & \(-\)2.07 & 5.8 \\
2 & 2013-03-09 10:00:25 & 9 & 35,530 & 59,668 & \(-\)1.52 & 6.4 \\
2 & 2013-03-09 10:00:34 & 9 & 35,476 & 59,671 & \(-\)2.85 & 4.6 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: An example of spatiotemporal database for \(d=4\). **Definition 4**. : _(\(k\)-anonymity). A spatiotemporal database is \(k\)-anonymous with respect to a set of attributes \(d\) if at most one of the \(k\) nearest neighbor has changed from one time-stamp to another so that each mobile user cannot be distinguished from its \(k-1\) neighbors._  
According to the authors of [14], \(k\)-anonymity is able to prevent mobile users' identity from being unveiled. This means that the probability of a user re-identification between its \(k\) neighbors is only possible with \(\frac{1}{k}\).