A novel self-adaptive grid-partitioning noise optimization algorithm based on differential privacy

Computer Science and Information Systems

article

Liu Zhaobin¹  Lv Haoze¹  Li Minghui¹  Li Zhiyang¹  Huang Zhiyi² 

[1] School of Information Science and Technology, Dalian Maritime University;Department of Computer Science, University of Otago

关键词: Data Publication;    Privacy Protection;    Differential Privacy;    Noise Optimization.;   

DOI  :  10.2298/CSIS180901033L

学科分类：土木及结构工程学

来源: Computer Science and Information Systems

【 摘 要 】

As the development of the big data and Internet, the data sharing ofusers that contains lots of useful information are needed more frequently. In particular, with the widespread of smart devices, a great deal of location-based datainformation has been generated. To ensure that service providers can supply a completely optimal quality of service, users must provide exact location information.However, in that case, privacy disclosure accident is endless. As a result, peopleare paying attention to how to protect private data with location information. Ofall the solutions of this problem, the differential privacy theory is based on strictmathematics and provides precise definition and quantitative assessed methods forprivacy protection, it is widely used in location-based application. In this paper, wepropose a self-adaptive grid-partitioning algorithm based on differential privacy fornoise enhancement, providing more rigorous protection for location information.The algorithm first partitions into a uniform grid for spatial two dimensions dataand adds Laplace noise with uniform scale parameter in each grid, then select thegrid set to be optimized and recursively adaptively add noise to reduce the relativeerror of each grid, and make a second level of partition for each optimized grid inthe end. Firstly, this algorithm can adaptively add noise according to the calculatedcount values in the grid. On the other hand, the query error is reduced, as a result,the accuracy of partition count query (the query accuracy of the differential privatetwo-dimensional publication data) can be improved. And it is proved that the adaptive algorithm proposed in this paper has a significant increase in data availabilitythrough experiments.

【 授权许可】

CC BY-NC-ND