Research On The Protection Of Location Information Based On Differential Privacy

With the rapid development of global positioning system and wireless communication network,the location-based applications have gradually penetrated into people's lives.Statistical analysis of the data generated by these applications can bring great convenience to people,s lives.For example,real-time navigation,road condition analysis,personalized information push,etc.But at the same time,it may also cause users'privacy leakage.Therefore,while publishing location information,it is necessary to provide privacy protection for these data.Differential privacy is a robust privacy protection model,which can be applied to the privacy protection of location information.One partitions the domain into cells,and then obtains noisy counts for each cell in a way that satisfies differential privacy.It ensures that individual information will not compromised in response range queries.However,due to the characteristics of data distribution and the addition of noise,the query results have some errors,which affect the availability of data.In order to improve the availability of data,we propose two location data publishing schemes satisfying differential privacy:(1)This thesis proposed a differential privacy location-based data publishing method based on k-d tree.In this scheme,the results of AG algorithm are processed postoperatively.The uniformity of region based heuristic is used to choose the partition scheme and then the k-d tree index structure is performed on the data domain.In this paper,we use an information entropy-like metric Ic to describe the uniformity of data distribution in the domain to be partitioned,and a threshold is set adaptively according to the data distribution in this domain.This method groups similar cells into a partition,which solves the noise overlapping problem caused by AG algorithm and reduces the query error.(2)The top-down domain partition scheme makes insufficient use of the data distribution characteristics.When data points are highly concentrated in a small area,a coarse-grained partitioning will introduce large approximation errors.Therefore,a fine?grained partitioning strategy is used to partition the data domain.Then a differentially private K-means clustering based cells merging strategy is adopted to enhance the utility of released data further.The adjacent similar cells belonging to the same cluster are merged into blocks and the blocks are used as the basic units for data publishing(3)Finally,the simulation experiments based on the real datasets show that the two schemes improved the query accuracy to a certain extent compared with AG algorithm,while the location-based data publishing method based on differential privacy K-means is more suitable for the situation of uneven data distribution and behave better in the case of small query range.This paper contains 26 figures,16 tables,52 references.