Int J Performability Eng ›› 2019, Vol. 15 ›› Issue (8): 2145-2152.doi: 10.23940/ijpe.19.08.p14.21452152

Previous Articles     Next Articles

Adaptive Grid Decomposition Algorithm based on Standard Deviation Circle Radius

Guoqiang Zhoua,b,*, Xiulian Tanga, and Shui Qina   

  1. a School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing, 210000, China
    b State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, 210000, China
  • Submitted on ;
  • Contact: * E-mail address:

Abstract: The differential privacy preservation model based on spatial dataset meshing has been widely concerned, but the distribution characteristics of the dataset and user's query granularity are often ignored or not fully considered in the partitioning of the dataset. Aiming at deficiencies in existing mesh-based algorithms, a standard deviation circle radius adaptive grid decomposition (SDCAG) algorithm is proposed. Firstly, the standard deviation circle radius is introduced to quantitatively represent the distribution characteristics of datasets in order to calculate privacy preservation requirements. Secondly, filtering and bucketing are used to reduce the noise error. Finally, the improved query precision is implemented based on the post-processing. Experiments on the NYC dataset, the Beijing dataset, and the Checkin dataset show that the SDCAG algorithm is superior to similar algorithms in terms of query performance.

Key words: differential privacy, spatial dataset, standard deviation circle radius, adaptive grid, post-processing