基于轨迹位置形状相似性的隐私保护算法

Privacy preserving algorithm based on trajectory location and shape similarity

为了降低轨迹数据发布产生的隐私泄露风险,提出了多种轨迹匿名算法。然而,现有的轨迹匿名算法在计算轨迹相似性时忽略了轨迹的形状因素对轨迹相似性的影响,因此产生的匿名轨迹集合的可用性相对较低。针对这一问题,提出了一种新的轨迹相似性度量模型,在考虑轨迹的时间和空间要素的同时,加入了轨迹的形状因素,可以在多项式时间内计算定义在不同时间跨度上的轨迹的距离,能够更加准确、快速地度量轨迹之间的相似性;在此基础上,提出了一种基于轨迹位置形状相似性的隐私保护算法,最大限度地提高了聚类内部轨迹的相似性,并且使用真实的原始位置信息形成数据"面罩",满足了轨迹k-匿名,在有效地保护轨迹数据的同时,提高了轨迹数据的可用性;最后,在合成轨迹数据集和真实轨迹数据集上的实验结果表明,本算法花费更少的时间代价,具有更高的数据可用性。

In order to reduce the privacy disclosure risks when trajectory data is released, a variety of trajectories anonymity methods were proposed. However, while calculating similarity of trajectories, the existing methods ignore the impact that the shape factor of trajectory has on similarity of trajectories, and therefore the produced set of trajectory anonymity has a lower utility. To solve this problem, a trajectory similarity measure model was presented, considered not only the time and space elements of the trajectory, but also the shape factor of trajectory. It is computable in polynomial time, and can calculate the distance of trajectories not defined over the same time span. On this basis, a greedy clustering and data mask based trajectory anonymization algorithm was presented, which maximized the trajectory similarity in the clusters, and formed data ＂mask＂ which is formed by fully accurate true original locations information to meet the trajectory k-anonymity. Finally, experimental results on a synthetic data set and a real-life data set were presented; our method offer better utility and cost less time than comparable previous proposals in the literature.