基于前缀邻接表的高可用性差分隐私轨迹发布方法  

A utility-aware differential privacy trajectory publishing method based on prefix adjacency list

作　　者：吴逸嘉 于娟[1] 韩建民[1] 曹小倩 姚鑫 彭浩[1] WU Yijia;YU Juan;HAN Jianmin;CAO Xiaoqian;YAO Xin;PENG Hao(School of Computer Science and Technology,Zhejiang Normal University,Jinhua 321004,China)

机构地区：[1]浙江师范大学计算机科学与技术学院,浙江金华321004

出　　处：《浙江师范大学学报（自然科学版）》2023年第3期254-264,共11页Journal of Zhejiang Normal University:Natural Sciences

基　　金：国家自然科学基金资助项目(61702148,61672648)。

摘　　要：现有的差分隐私轨迹发布方法在存储轨迹序列特征时未充分考虑轨迹位置点前后的关联关系,查找序列特征较慢,轨迹重构的效率较低;另外,现有方法未充分捕获轨迹的时空特征,重构的轨迹数据可用性较差.为此,提出一种基于前缀邻接表的高可用性差分隐私轨迹发布方法.该方法在轨迹序列特征存储时采用了一种新的数据结构——前缀邻接表,该表记录了轨迹位置网格的轨迹前缀计数信息及下一位置网格的存储位置,有利于轨迹重构阶段的候选网格概率的计算,提高了轨迹重构效率.同时,该方法结合k阶马尔科夫链与目的地分布选取网格,在网格内采用了基于密度的位置点选择策略,进而重构出可用性更高的轨迹.实验结果表明,在同等隐私保护水平下,提出的方法在效率和数据可用性方面均优于现有的方法.For the existed differential privacy trajectory publishing methods had not fully considered the relationship between the trajectory position points when storing trajectory sequence features,so it was slow to find the sequence features and the efficiency of trajectory reconstruction was low.In addition,the existed methods had not adequately captured the spatiotemporal features of trajectories,resulted in poor utility of reconstructed trajectories.A utility-aware differentially private trajectory publishing method based on prefix adjacency list was proposed.The method adopted a new data structure—prefix adjacency list in the storage of trajectory sequence features.The prefix adjacency lists recorded the trajectories prefix count of grid for each trajectory and the location of next grid,which facilitated the calculation of the candidate grid probability in trajectories reconstruction stage and improved trajectories reconstruction efficiency.At the same time,the method combined korder Markov chain and destination grids distribution to predict the next grids.Furthermore the method adopted the density-based location point selection strategy in the grid to reconstruct trajectories with higher utility.Experimental results showed that under the same level of privacy protection,the proposed method was superior to the existed methods in terms of efficiency and data utility.

关 键 词：差分隐私 前缀邻接表 轨迹重构 轨迹可用性 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]