Research On Differential Privacy Protection Of Tree Index Location Data

With the popularity of mobile devices and location technologies,location-based services have been widely used to promote the sharing and collection of location data.However,it also provides convenience for the attacker to obtain the user's location data.Attackers can link other user's background knowledge,and easily infer user's sensitive information,which leads to the disclosure of user's privacy.Therefore,how to effectively protect the privacy of user location has become an important issue to be solved.This thesis focuses on the problem of location data privacy protection,using differential privacy technology to resist attackers' attacks on arbitrary background knowledge.Aiming at the problem that traditional differential privacy budgeting methods can not be individualized allocation,and the existing location privacy protection algorithm based on differential privacy has low query accuracy and operation efficiency,this thesis proposes differential privacy budget allocation method for data of tree index and location data range counting query privacy protection method based on differential privacy respectively.The feasibility and validity of the proposed scheme were verified by theoretical analysis and experiments.The main research contents of this thesis are as follows:(1)To solve the problem that the existing differential privacy budget allocation method can not individually distribute the privacy budget based on different needs of users,an arithmetic sequence privacy budget allocation method and a geometric sequence privacy budget allocation method were proposed.Firstly,spatial data was indexed by tree structure.Then,according to the different requirements of users for privacy protection or query precision,the difference or ratio of privacy budget allocated by two adjacent layers of tree structure is dynamically adjusted to flexibly change the way of privacy budget allocation,and the total privacy budget was reasonably allocated to each layer of tree structure.Finally,the method was compared with other existing privacy budget allocation methods.The experimental results showed that the proposed method is more flexible and can satisfy the user's self-selection and personalized allocation of privacy budget.(2)To solve the problem that the existing index structures satisfying differential privacy have low query accuracy and running efficiency due to the limitation of partition granularity or tree depth,an improved quad-tree structure was proposed.Firstly,the location data space was partitioned.Then,based on the conventional quad-tree,the location data was stored in the smallest rectangular node which contains it completely.The improved quad-tree structure was constructed so that each node can store location information.Finally,simulation experiments show that the algorithm has improved the query accuracy and operation efficiency,and effectively protects the user's location privacy.