## 3 Materials and Methods
### System Model  
Here, we consider a spatio-temporal database with \(N\) records--that is, \(N\) moving objects in the \(xy\) plane. Each record \((x_{i}^{j},y_{i}^{j})\) represents the spatial coordinates of the mobile user \(j\) in time-stamp \(t_{i}^{j}\), or point \(i\) of its trajectory \(j\)[15]. From the location coordinates \((x,y)\), we can extract the corresponding dual points by employing the methods described in Section 3.1. Suppose a trajectories database \(T=\{T^{1},\ldots,T^{N}\}\) of equal length \(L\) in which each trajectory is represented via a sequence of \(L\) triples, that is, \(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})\}\). For each point \(i\) in trajectory \(j\), we define in four-dimensional space a vector \(DD_{i}^{j}=(U_{x_{ij}},a_{x_{ij}},U_{y_{ij}},a_{y_{ij}})\) which denotes the dual points array. Hence, we can redefine and store the trajectory \(j\) as \(T^{j}=\{DD_{1}^{j},D_{2}^{j},D_{3}^{j},\ldots,D_{L}^{j}\}\). The privacy preservation of \(k\)-NN query in trajectory databases is addressed with the use of two different methods. The first one is entitled dual-based \(k\)-NN (\(DukNN\)) which applies \(k\)-NN directly onto dual points, while the second one is called dual-based clustering \(k\)-NN (\(DuCLkNN\)). The main difference between these two methods lies in the fact that the latter is applied in clustered dual point data. In addition, the operations involved in addressing a \(k\)-NN query are thoroughly described in Algorithms 1 and 2, respectively. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Obij** & **Time Moment** & **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}]\) \\ \(\ldots\) & \(\ldots\) & \(\ldots\) \\ 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 3: Dual points \(k\)-anonymity sets for \(N\) mobile users in \(L=5\) time-stamps. ```
1:input The number of \(k\) nearest neighbors
2:input The number of mobile users \(N\)
3:input The dual points array of \(N\) users in \(L\) time-stamps
4:output\(k\) nearest neighbors indexes of \(N\) users in \(L\) time-stamps
5:for\(i=1\) to \(L\)do
6:for\(j=1\) to \(N\)do
7: Apply \(k\)-NN for the dual points of all users in order to identify the set of \(k\)-NN indexes \(I_{i}^{j}\) of user \(j\) in time-stamp \(i\)
8:endfor
9:endfor
```  
**Algorithm 1** DukNN  
```
1:input The number of \(k\) nearest neighbors
2:input The number of mobile users \(N\)
3:input The dual points array of \(N\) users in \(L\) time-stamps
4:output\(k\)-NN indexes of \(N\) users in \(L\) time-stamps
5:Apply \(K\)-Means of dual points \((U_{x},a_{x})\) of \(N\) users for the \(L\) time-stamps
6:for\(i=1:L\)do
7:for\(j=1:N\)do
8: Apply \(k\)-NN method between the dual point of user \(j\) and the dual point of users inside the cluster \(C_{i}^{j}\) of user \(j\) in time-stamp \(i\) and find the set of \(k\)-NN indexes \(I_{i}^{j}\)
9:endfor
10:endfor
```  
**Algorithm 2** DuCLkNN  
In the case of employing the Algorithm 1 in order to run a \(k\)-NN query, we must focus on a specific time-period during which we will have in our disposal the dual point of all users' locations. Given that each user stands in the same sub-trajectory during the study period, the privacy is preserved in that segment since the \(k\) nearest neighbors remain unchanged.