基于语义位置保护的轨迹隐私保护的k-CS算法

摘要

Since the data utility would be sharply reduced after privacy-preserving process and several attack models could not be resisted by traditional algorithms,such as,semantic location attacks and maximum moving speed attacks,a trajectory privacy-preserving algorithm based on semantic location preservation under road network constraints,called k-CS (k-Connected Sub-graph) algorithm,was proposed.Firstly,two attack models in road network space were proposed.Secondly,the privacy problem of semantic trajectory was defined as the k-CS anonymity problem,which was then proven NP-hard.Finally,an approximation algorithm was proposed to cluster nodes in the road network to construct anonymity zones,and semantic locations were replaced with the corresponding anonymity zones.Experiments were implemented to compare the proposed algorithm with the classical algorithm,called (k,δ)-anonymity.The experimental results show that,the k-CS algorithm performs better than (k,δ)-anonymity algorithm in data utility,query error and runtime.Specifically,k-CS algorithm reduces about 20％ in information loss than (k,δ)-anonymity,and k-CS algorithm deceased about 10％ in runtime than (k,δ)-anonymity algorithm.%针对轨迹数据隐私保护算法数据可用性低及易受语义位置攻击和最大运行速度攻击等问题,提出了一种在路网环境中基于语义轨迹的隐私保护算法-k-CS算法.首先,提出了两种路网环境中针对轨迹数据的攻击模型;然后,将路网环境中基于语义轨迹的隐私问题定义为k-CS匿名问题,并证明了该问题是一个NP难问题;最后,提出了一种基于图上顶点聚类的近似算法将图上的顶点进行匿名,将语义位置由相应的匿名区域取代.实验对所提算法和轨迹隐私保护经典算法(k,δ)-anonymity进行了对比,实验结果表明:k-CS算法在数据可用性、查询误差率、运行时间等方面优于(k,δ)-anonymity算法;平均信息丢失率比(k,δ)-anonymity算法降低了20％左右;算法运行时间比(k,δ)-anonymity算法减少近10％.