结合四叉树划分的差分隐私位置发布算法

Differential Privacy Location Publishing Algorithm Combined with Quadtree Partition

差分隐私技术是一种与背景知识无关的强隐私保护模型,其通过应用随机算法对真实位置添加噪声进行干扰后发布,然而在位置发布时大多会忽略了位置稀疏程度对位置差分隐私保护算法的影响.针对此问题,本文在已有发布算法的基础上,提出了一种位置差分隐私发布算法DPLIP:首先针对用户兴趣区外的扰乱位置点,采用映射函数对其进行处理,以减小噪声注入量;其次按照四叉树结构对用户兴趣区进行划分,并以各个节点权重占总权重的比值作为区域划分的依据;最后结合划分后区域的位置点稀疏程度对该区域位置点添加噪音,然后从真实位置和扰乱位置中随机选取位置点进行发布.实验结果表明:相同隐私预算的前提下,DPLIP算法能有效的提高可行性和数据可用性.

Differential privacy technology is a strong privacy protection model which has nothing to do with background knowledge.It uses random mechanism to add noise to the real location and then publish it.However,the impact of location sparsity on the location differential privacy protection mechanism is mostly ignored when publishing location.To solve this problem,this paper proposes a location differential privacy publishing mechanism DPLIP based on the existing publishing mechanism:firstly,aiming at the disturbed location outside the user's interest area,the mapping function is used to deal with it to reduce the amount of noise injection;secondly,the user's interest area is divided according to the quadtree structure,and the ratio of each node's weight to the total weight is taken as the region At last,the noise is added to the location points of the area according to the sparsity degree of the location points,and then the location points are randomly selected from the real location and disturbed location for publishing.The experimental results show that DPLIP mechanism can effectively improve the feasibility and data availability under the same privacy budget.