# Trajectory Clustering and k-NN for Robust Privacy Preserving Spatiotemporal Databases
## 2 Materials and Methods
### System Model
: _Vulnerability Algorithm 5: Given a mobile user \(j\), a set \(I_{i}^{j}\) with the \(k\) nearest neighbors indexes in time-stamp \(i\), \(V_{i}^{j}\) is defined as_  
\[V_{i}^{j}=\frac{1}{|I_{i}^{j}\cap I_{i-1}^{j}|}\]  
_where \(0\leq V_{i}^{j}\leq 1\), \(|I_{i}^{j}\cap I_{i-1}^{j}|\), and the number of \(k\) indexes remain the same._```
1:Inputsets\(I_{i}^{j}\) with the \(k\) nearest neighbors indexes, number of mobile users \(N\) and time period \(L\)
2:Initialization:\(V_{1}^{j}=\frac{1}{k}\)
3:Output:Vulnerability values of \(N\) mobile users in \(L\) time-stamps
4:for\(i=2:L\)do
5:for\(j=1:N\)do
6:\(V_{i}^{j}=\frac{1}{|I_{i}^{j}|_{l=1}^{L}|}\)
7:endfor
8:endfor
```

**Algorithm 5** Vulnerability. ### Privacy Preserving Analysis

The rising advances in video tracking technology has attracted the scientific attention of understanding of social behavior of swarming animals. The video tracking method can automatically measure an individual's motion states using videos from different camera views [15]. Swarming behavior is connected with collective behavior, which usually happens in large groups of animals such as birds, mosquitos, and other insects [16]. Researchers employ mathematical models to simulate and understand the swarm behavior. The simplest mathematical models generally consider that individual animals move in the same direction as their neighbors, remain close to them (thus, neighbors remain constant) and avoid collisions with these neighbors. In our study, mobile users constitute the \"swarming animals\" who have collective motion behavior and either organize into groups or not, as described in the previous section. It is worth making privacy preserving analysis in the case that mobile objects are moving randomly (thus, independently of each other) from one position to another. In both approaches (either applying on-line clustering or not), we observe that mobile users' nearest neighbor indexes change and, thus, the vulnerability of both methods increases. In the case of random motion, mobile users' behavior is similar to that of a swarm of bees or flies. Their direction (angle) is linear and velocity amplitude is approximately constant. Similar motion characteristics have users in a road network, but they do not move randomly. Generally, a mobile object in a dense road network is moving on a piece-wise linear random path with a constant speed. Let \(X_{t_{i}}\) be a sequence of independent random variables that relate to the neighbors of a mobile user \(i\) which changes in a time interval \(t_{i}\). To maintain low levels of vulnerability, much less than 1 and close to 0, users' motion behavior should not change considerably so that their \(k\) nearest neighbors remains the same from one time-stamp to another. This results in the following theorem:

Theorem 1: _The probability that the nearest neighbors do not remain the same within a time interval \((0,t_{i}]\) and at least 1 of them change such that users can be distinguishable from an adversary, tends to 1 if objects move randomly._

\[\lim_{l\to k}P(X_{t_{i}}\geq l)=1\]

Proof: We conducted a Poisson experiment. We consider that the number of successes that are resulting from the Poisson experiment termed as a Poisson random variable with average number of successes \(\lambda\) and \(k\) a positive integer which relates with \(k\)-anonymity level. 1. The outcomes of the experiment were discrete. Specifically, they concerned the nearest neighbor's sustainability and are classified as either success (neighbors remained the same are at least \(k-1\)) or failure (number of neighbors remained the same are at most \(k-2\), which is less than \(k-1\)). 2. \(\lambda\) is the average or expected number of successes within a time interval \(t_{i}\) for a mobile user \(i\), \(E(X_{t_{i}})\) and assumed to be known and constant throughout the experiment. 3. Poisson describes the distribution of events. Each event is independent of the other events. 4.