Advanced Search
    Zhang Xiaojian, Jin Kaizhong, Meng Xiaofeng. Private Spatial Decomposition with Adaptive Grid[J]. Journal of Computer Research and Development, 2018, 55(6): 1143-1156. DOI: 10.7544/issn1000-1239.2018.20160963
    Citation: Zhang Xiaojian, Jin Kaizhong, Meng Xiaofeng. Private Spatial Decomposition with Adaptive Grid[J]. Journal of Computer Research and Development, 2018, 55(6): 1143-1156. DOI: 10.7544/issn1000-1239.2018.20160963

    Private Spatial Decomposition with Adaptive Grid

    • Grid-based differentially private spatial decomposition has attracted considerable research attention in recent years. The trade-off among the size of spatial data, data skew, and Laplace noise directly constrains the accuracy of decomposition. Most state-of-the-art methods based on grid cannot efficiently accommodate the three constraints. To address the above questions, this paper proposes a three-layer adaptive grid, called STAG, to decompose the spatial data with differential privacy. STAG employs Bernoulli random sampling method to retrieve the samples as decomposition data in the second level. According to the different query granularities in the second level, some cells whose counts are smaller than the given threshold will be filtered by exponential mechanism and high-pass filter techniques. For the cells whose counts are over the threshold, STAG uses Down-Split method to decompose them into fine-grained cells in the third level. For the filtered cells, STAG utilizes Up-Merge method to group them into coarse-grained cells with optimal grouping skill in the first level. STAG method is compared with the existing methods such as UG, AG, Kd-Stand, and Kd-Hybrid on the large-scale real datasets. The experimental results show that the STAG outperforms its competitors, achieves the accurate decomposition and results of range query.
    • loading

    Catalog

      Turn off MathJax
      Article Contents

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return