Research And Implementation Of An Efficient K-anonymous Trajectory Privacy Protection Method Based On Generalization

Trajectory data itself contains rich spatio-temporal information.The analysis and mining of trajectory data can support a variety of applications.Therefore,many governments and scientific research institutions have strengthened the research on trajectory data.However,if a malicious attacker obtains other personal information related to the trajectory through trajectory data reasoning without authorization,the personal privacy of the data user will be completely exposed through that.Based on the universality of trajectory data publishing and the emergence of corresponding effective attack methods,the research content of this work mainly focuses on the trajectory privacy protection in offline data publishing.At present,the most common attack method is linking attack,and there have been some results that can identify specific individuals from given trajectories.K-anonymity has been proved to be an effective defense against linking attacks in traditional relational databases,and some studies have tried to apply this principle to trajectory data.These studies focus on using different means to meet the privacy protection requirements,but rarely consider the actual availability of the algorithm.In practical application,due to the particularity of trajectory,the trajectory data to be released is often large-scale,and the complexity of the algorithm directly affects the availability of the method.Although the existing methods based on uncertainty have good operation efficiency,they can not protect privacy well.While the method based on merge generalization has relatively better performance in privacy protection,it is very inefficient and difficult to be put into large-scale data applications.The trajectory K-anonymity algorithm for linking attack should have better privacy protection ability and minimize the loss of data utillity and availability.At the same time,work should focus on whether the method itself can run efficiently and minimize the running overhead.A good method should achieve a good balance in these three aspects,but the existing methods are rarely satisfied.In view of the above problems,this paper puts forward the following research contents:(1)The trajectory K-anonymity algorithm is usually composed of dividing the original trajectory set and anonymizing each group.In order to ensure the ability of privacy protection,this work selects the merging generalization.For protecting the data utility,this work need to have a method to measure the merging loss and design a method to divide the trajectory set into K clusters.In this work,a hierarchical grid structure is proposed,and a trajectory matching and index are designed to obtain the division of the original trajectory set with the smallest merging loss.(2)In order to improve the efficiency,the original method is optimized on the basis of hierarchical grid structure and index.Firstly,z-ordering is introduced to transform the coding,so that the similar square coding is closer and the transformation between levels is more convenient.Then the length based pruning is introduces to optimizes the search strategy,and transforms it into a top-down one-way comparison to reduce unnecessary matching queries.Finally,the merging and pruning strategy based on grid is used to optimize the trajectory merging process.(3)On large-scale data sets,by using multi-dimensional evaluation indicators,this work compares the performance of typical W4 M,GLOVE,KLT and the new algorithm GINDEX proposed in this paper in different performance aspects.GINDEX performs well in all aspects.To sum up,the algorithm GINDEX based on hierarchical grid structure and index proposed in this paper has superior performance of different orders of magnitude in operation efficiency.At the same time,it also has good privacy protection ability and minimize the loss of data validity and availability.