# Releasing Differentially Private Trajectories with Optimized Data Utility
## 5 Experimental Evaluations
### Comparative Evaluations
#### 5.5.1 Evaluation on Semantic Utility  
The semantic utility of three location privacy protection algorithms is evaluated by periodic pattern Jaccard coefficient and semantic annotation accuracy, respectively. Experimental results are shown in Figure 3. We summarize the experimental results about the semantic utility in terms of the periodic pattern Jaccard coefficient and then explain the reasons. As shown in Figure 3, (i) we observe that UDPT always performs better than its competitors, especially in terms of semantic annotation accuracy. (ii) In most cases, the semantic utility increases when a larger privacy budget is used. (iii) In particular, in the strictest privacy setting of \(\epsilon\in[0.1,1.0]\), all of the location privacy protection algorithms provide poor performance. (iv) All of the location privacy protection algorithms provide a better semantic utility on denser trajectory datasets, such as GeoLife, while performing poorer on sparser trajectory datasets, such as Gowalla and Brightkite. Our explanations of the experimental results are as follows. Figure 3: Comparison of UDPT against existing works in terms of semantic utility under different privacy budgets on three datasets. A higher ordinate indicates a better utility. (i) The outperformance of UDPT against its competitors can be attributed to the good preservation of periodic patterns as well as location categories. First, the CRF model that UDPT exploits is good at capturing the movement patterns implied in the actual trajectory, especially the long-term and periodic patterns. However, AdaTrace considers only the one-step transition patterns instead of the long-term patterns of the whole trajectory. Hence, periodic patterns cannot be well preserved by AdaTrace. Similarly, MLCE also performs poorly in terms of periodic patterns since it independently obfuscates each actual location and neglects the preservation of movement patterns of the whole trajectory. In addition, the reason for UDPT's significant outperformance is that, besides the good preservation of periodic patterns, temporal features that many semantic annotation tasks rely on are also well contained. In [8], the semantic annotation tasks exploit individual mobility features  
Figure 4: Comparison of UDPT against existing works in terms of geographic utility under different privacy budgets on three datasets. A higher ordinate implies a better utility. Figure 5: Comparison of UDPT against existing location privacy protection algorithms in terms of location privacy attacks metric under different privacy budgets on three datasets. A larger ordinate indicates a stronger prevention from attacks. in geographical and temporal aspects, e.g, individuals' co-occurrence, visit frequency of locations, the temporal distribution of check-in time in one week and one day, to capture the relatedness among locations. However, the temporal features are destroyed by AdaTrace, so the semantic annotator could learn the wrong match between the locations and the category tags, which further leads to low accuracy of the semantic annotation. Although MLCE holds the temporal features, other mobility features such as visit frequency of locations that the semantic annotator depends on are still lost. Consequently, MLCE performs a low semantic annotation accuracy. The result in (ii) is expected, because, according to the definition of differential privacy in Section 1, a larger budget usually brings about less noise and thus better data utility. Nonetheless, the noise will significantly increase when the privacy budget is smaller, especially for the \(\epsilon\in[0.1,1.0]\), which explains the result in (iii). The reason for (iv) is that, on the one hand, a trajectory dataset with numerous check-ins usually contains more enriched movement patterns, especially frequent and long-term patterns. In contrast, a sparse dataset, e.g., Brightkite, of which the average number of check-ins per individual is only 113, contains only sporadic visits, rather than repeated transitions between locations.