ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2021, Vol. 58 ›› Issue (11): 2430-2443.doi: 10.7544/issn1000-1239.2021.20210589

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

• 信息安全 • 上一篇    下一篇



  1. (河北大学网络空间安全与计算机学院 河北保定 071000) (河北省高可信信息系统重点实验室(河北大学) 河北保定 071000) (
  • 出版日期: 2021-11-01
  • 基金资助: 

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).

摘要: 近些年基于位置服务的软件便利人们生活的同时,也带来了隐私泄露的风险.针对这一问题,提出一种基于噪声前缀树结构的轨迹数据发布方法.首先根据轨迹时空特性构建轨迹等价类,利用Hilbert曲线对轨迹位置点进行划分,得到划分区域的中心点,将得到的中心点聚合成新的轨迹,因此达到减少空间复杂度的目的.然后构建前缀树,并将聚合的轨迹位置点存入到前缀树中,可以有效地提高查询效率.最后为了保护节点中存储的敏感信息,利用等差隐私预算分配方式对前缀树节点中数据添加Laplace噪声,保证轨迹数据的安全性的同时也提高了数据可用性.通过真实数据集实验对比已有的方案,验证了所提出的算法在保证数据隐私性的同时,也提高了数据可用性.

关键词: 差分隐私, 位置隐私, Hilbert曲线, 前缀树, 轨迹数据

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