ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2021, Vol. 58 ›› Issue (11): 2430-2443.doi: 10.7544/issn1000-1239.2021.20210589

Special Issue: 2021密码学与网络空间安全治理专题

Previous Articles     Next Articles

A Safe Storage and Release Method of Trajectory Data Satisfying Differential Privacy

Wu Wanqing, Zhao Yongxin, Wang Qiao, Di Chaofan   

  1. (College of Cyber Security and Computer, Hebei University, Baoding, Hebei 071000) (Key Laboratory of High Trusted Information System in Hebei Province (Hebei University), Baoding, Hebei 071000)
  • Online:2021-11-01
  • Supported by: 
    This work was supported by the Science and Technology Research Project of Hebei Higher Education (ZD2021011) and the Natural Science Foundation of Hebei Province (F2019201361).

Abstract: In recent years, although location-based service software facilitates people’s life, it brings the risk of privacy leakage. In order to solve this problem, we propose a trajectory data publishing method that is based on the noise prefix tree structure. In the first part, the trajectory equivalence class is constructed according to the space-time characteristics of the trajectory, and then the locus location points are divided by Hilbert curve to obtain the central points of the divided region. Finally, the obtained central points are converged into the new trajectory, so as to reduce the spatial complexity. The second part builds a prefix tree for storing location points according to the nature of the prefix tree, and stores the aggregated track location points into the prefix tree, which can improve query efficiency. In the third part, in order to protect the sensitive information stored in the nodes, this article will add Laplace noise to the nodes of the prefix tree, so that safer trajectory data can be released. Considering that the published data should be of high availability, this paper uses the arithmetic privacy budget allocation method to add Laplace noise to the node data, and limits the amount of noise by the threshold value of each layer, so as to finally publish trajectory data with high availability satisfying the differential privacy model. Through the experimental verification of real data sets, and comparing with the existing NTPT algorithm, our proposed TDPP algorithm is lower than the NTPT algorithm in different error values, and can provide better privacy protection. It is verified that the algorithm proposed in this paper improves data availability while ensuring data privacy.

Key words: differential privacy, location privacy, Hilbert curve, prefix tree, trajectory data

CLC Number: