# Trajectory Clustering and k-NN for Robust Privacy Preserving Spatiotemporal Databases
## 2 Materials and Methods
### System Model
The probability for a mobile user \(i\) to have at least \(l\) different neighbors, in a time-interval \(t_{i}\) (occurrence of a failure) is written as \[P(X_{t_{i}}>l)=1-P(X_{t_{i}}\leq l)=1-\leq\frac{\lambda^{l}e^{\lambda}}{l!}\]

\[\lim_{l\to k}P(X_{t_{i}}\geq l)=\lim_{l\to k}(1-\frac{\lambda^{l}e^{ \lambda}}{l!})\]

Due to the random moving assumption, it is highly certain that the indexes of all \(k\) nearest neighbors will change. Hence, the above probability will be very close to 1. If \(k\) is large enough, previous limit will tend to 1. ### Experimental Data and Environment

The experimental data used in this paper come from SMaRT Database GIS Tool in [[http://www.bikerides.gr/thesis2/](http://www.bikerides.gr/thesis2/)]([http://www.bikerides.gr/thesis2/](http://www.bikerides.gr/thesis2/)). We experimented on two trajectory datasets of 400 and 2000 bike riders, as shown in Figure 3, in the area of Corfu, with 100 trajectory points each. For each trajectory point, we have available the four dimension values for 100 time-stamps, i.e., the Cartesian coordinates (\(x\),\(y\)), the angle (\(g\)), and the velocity (\(v\)). The environment in which experiments were carried out has the following characteristics: Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00 GHz 3.00 GHz, 16 GB Memory, Windows 10 Education, 64-bit Operating System, x64-based processor and Matlab 2018a. ## 3 Discussion

In the last decade, the problem of privacy preserving of location data has been of particular concern to researchers. Hence, many research works have been conducted to reinforce the security level previous ones provide, such as the association of location data with pseudonyms. Figure 3: A _Matlab_ overview of mobile users trajectories’ points. In a recent work [17], the authors recommended an asymmetric Private Equality Testing protocol (PET) that allows two users to communicate with each other safely and without the involvement of a third party. PET requires two public-key exponentiation per each user and needs three rounds to complete. Both users compute their private input through hash functions and send it to each other. The output of protocol in the end of third round indicates the equality or not of two keys and as a result their communication. This protocol can be used by location-based social services to find the location of users who are in the same region or in a specific radius depending on the preference of user. The security of private inputs of involver lies in the use of _Computational Diffie-Hellman_ and _Discrete Log Problem_. In addition, asymmetry does not reveal whether the computation and equality of inputs are successful and that prevents observers to identify if the connection is established or not. More to the point, \(k\)-anonymity method has been used to reinforce and quantify location data privacy. If \(k\)-anonymity is achieved, a person cannot be distinguished from \(k-1\) other people [4]. In the context of \(k\)-anonymity, authors in [4] proposed an enhanced Dummy-Location Selection (DLS) algorithm for users in LBS. From a different perspective, authors in [14] aimed at the utility improvement of differentially private published datasets. More specifically, they showed that the amount of noise required to fulfill \(e\)-differential privacy can be reduced if noise is added to a \(k\)-anonymous version of the dataset, where \(k\)-anonymity is achieved through a specially designed micro-aggregation of all attributes. As a result of noise reduction, the general analytical utility of the anonymized output is increased. Moreover, authors in [18] attempted to protect users' private locations in location-based services adopting the spatial cloaking technique, which organizes users' exact locations into cloaked regions. This method satisfies the \(k\)-anonymity requirement within the cloaked region. They proposed a cloaking system model, which they called \"anonymity of motion vectors\" (AMV), that provides anonymity for spatial queries minimizing the cloaked region of a mobile user using motion vectors.