Trajectory privacy data publishing scheme based on local optimisation and R-tree

Figures & data

Table 1. Partial trajectory data sheet R.

User	Trajectory coordinate	Road Network Info
T1	1a, 3b, 4c, 5d, 6e	mall, school, supermarket, library
T1	1c, 2a, 3b, 5f, 6e, 7g	school, gallery, library
T3	2a, 4d, 5f, 6e, 7g, 9h	restaurant, library, gymnasium
T4	1b, 3b, 4f, 5d, 6c, 8h	school, supermarket, gymnasium
T5	2e, 3b, 4a, 5d, 6e, 8d	school, mall, library, supermarket

Figure 1. Location data sheet creation process.

Figure 2. Filtering available locations.

Figure 3. The filtered trajectory path.

Table 2. Pseudocode for local optimisation.

Input	Location data sheet R, trajectory data set D, upper limit of trajectory length in the possession of the attacker L, anonymity number K, confidence threshold C, time threshold E, trajectory number threshold V
Output	Violation dataset Q, locally optimised trajectory dataset New-D
1	R←Location data sheet of road network diagram;
2	X1←set of all distinct pairs in D;
3	i = 1,j = 0;
4	While i ≤ L and Xi ≠φ do
5	Scan D to compute |T(P)| and Conf(s|T(P));
6	for $\mathrm{\forall }$ p ∈P where |T (P)| > 0 do
7	if |T(P)| < K or Conf(s|T(P)) > C then
8	Add P to Qi;
9	else
10	Add P to Wi;
11	end if
12	end for
13	Xi + 1 ← Wi $\bowtie$ Wi;
14	for $\mathrm{\forall }$ P ∈ Xi + 1 do
15	if P is a super sequence of any v ∈ Qi then
16	Remove P from Xi + 1;
17	end if
18	end for
19	i++;
20	end while
21	Build the score sheet by Score(Q) = Optimise(pj) /Loss(pj);
22	Q←Choose the highest point;
23	If Q(t) > E or Q(tr) > V do
24	Q←Split Q into sub tracks;
25	else
26	Q'←Replace the position of Q with Location data sheet;
27	end if
28	Return New-D←D $\bowtie$ Q’.

Table 3. Pseudocode for constructing R-tree and adding noise.

Input	Locally optimised trajectory dataset New-D, Privacy Budget ε
Output	Protected Dataset D′
1	Suppose the root node is r; the node to be inserted into the trajectory is v;
2	If v is a leaf node
3	Return v;
4	Else if v is not a leaf node
5	Calculate the trajectory sequence similarity according to formula(6);
6	m←Node with high similarity;
7	If the similarity of the trajectory sequence is the same or 0
8	Calculate the average Fréchet distance according to formula (7);
9	m←Node with small average Fréchet distance;
10	End if
11	v←m;
12	End if
13	P←v;
14	If the number of index records of P reaches the maximum
15	Split node;
16	Update parent node information;
17	End if
18	Update parent node information;
19	Return R-Tree(D);
20	ε'=ε/|P|;
21	For i = 1 to p do
22	If data type is location data
23	T′(P)←T(P) + Noisy(ε'/2);
24	Else
25	c′(oth)←c(oth) + Noisy(ε'/2);
26	End if
27	End for
28	Return D'

Figure 4. Effect of different K values on the loss rate of trajectory data point.

Figure 5. Effect of different C values on the loss rate of trajectory data points.

Figure 6. Comparison of the average error of different algorithms.

Figure 7. Comparison of the average data point quality loss results of different algorithms.

Figure 8. When ε = 0.5, effect of trajectory data length on different scenarios.

Figure 9. When ε = 1, effect of trajectory data length on different scenarios.