面向轨迹数据发布的个性化差分隐私保护机制

The widespread of smart phones and mobile internet facilitates people's lives. Meanwhile, a large number of users' trajectory data are collected and analyzed to provide better location-based services. Publishing the trajectory data can benefit the applications such as the intelligent transportation management, infrastructure planning, and road congestion prediction and detection. As the trajectory data contains users' sensitive information, the publication of the original trajectory data may lead to the privacy leakage risks. To solve this problem, researchers have proposed privacy-preserving schemes to obfuscate the original trajectory data. These schemes are mainly on the basis of partition-based privacy models, such as k-anonymity and confidence bounding. Thus, they cannot resist the inference analysis of attackers with background knowledge. As a de facto standard, differential privacy guarantees the privacy level of the released data set, and privacy leakage risk is not affected by the background knowledge of the attackers. However, the existing differentially private schemes provide the users with the same privacy level, while the users usually have various privacy preferences. These schemes may narrow down the scope of available trajectory data, since some users' privacy preference cannot be guaranteed. In this paper, we propose a sample based personalized differential privacy mechanism for trajectory data publication, which provides users with different privacy budget. Firstly, a location clustering algorithm is designed based on the linear indexes generated by the Hilbert curve. Inspired by the space filling curve, we partition the location set and employ the Hilbert curve to traverse the space regions to generate linear indexes of the location set. Different from traditional two-dimensional data clustering algorithms, this algorithm takes linear indexes as input to generate clusters in one-dimensional space. The algorithm can maintain the distance and distribution characteristics of the locations in the trajectory data set. By linearly scanning the indexes, the location clusters can be effectively obtained. In addition, the algorithm does not need to set the same number of clusters on the location sets at different timestamps, but generates different numbers of clusters according to the different distributions of the location sets. Secondly, a generalization method is proposed to meet personalized differential privacy. This method takes into account the different privacy preferences of individuals, and generates the representative element of each location cluster in a personalized differential privacy way. Specifically, the method determines the selection probability of each location according to its privacy budget, and samples the locations in the clusters at each timestamp. Then, the exponential mechanism is employed to select the representative location of each cluster to ensure that the trajectory generalization process satisfies the personalized differential privacy. The privacy analysis confirms that the proposed mechanism satisfies the definition of personalized differential privacy. The experiments on real trajectory data set show that the proposed mechanism achieves better tradeoff between privacy protection and data utility, compared with the standard differential privacy mechanism. Moreover, the generated representative locations are taken from the original location set, thus it will not lead to the generation of meaningless representative locations, ensuring that the generalized trajectory data set can resist filtering attacks.