Int J Performability Eng ›› 2020, Vol. 16 ›› Issue (7): 1058-1066.doi: 10.23940/ijpe.20.07.p8.10581066

Previous Articles     Next Articles

Differential Privacy Spatial Decomposition via Flattening Kd-Tree

Guoqiang Gong, Cedric Lessoy, Chuan Lu*, and Ke Lv   

  1. School of Computer and Information, Three Gorges University, Yichang, 443002, China
  • Submitted on ; Revised on ; Accepted on
  • Contact: * E-mail address: 621030101@qq.com
  • About author:Guoqiang Gong is an Associate professor at the China Three Gorges University. His research interests include privacy preservation, advanced signal processing. Cedric Lessoy is a Master's candidate at the China Three Gorges University. His research interests include deep learning and social network data analysis. Chuan Lu is a Master's candidate at the China Three Gorges University. His research interests include social network and privacy protection. Ke LV is a Professor at the China Three Gorges University. His research interests include information processing and big data analysis.

Abstract: The key problem of using differential privacy is controlling sensitivity. Almost all papers focus on processing sensitivity, but the efficiency of the algorithm is also very important. Therefore, this paper hopes to improve efficiency as much as possible under the premise of ensuring utility. In this paper, decomposition and reconstruction via flattening kd-tree (DRF) is proposed based on differential privacy, which applies a flattening kd-tree to process the adjacency matrix. Firstly, by adjusting the vertex labeling, the set of labeling form dense areas and sparse areas as much as possible in the adjacency matrix. The adjacency matrix is then decomposed by flattening kd-tree, and each sub-region is anonymously operated using differential privacy. Finally, each subregion is reconstructed to obtain a complete anonymous graph. At the end of the article, experiments are conducted over real-world datasets. According to the results, DRF has a significant improvement in efficiency, the time complexity of DRF is (|??|), and DRF has a good performance in degree distribution, degree centrality and cutting query.

Key words: differential privacy, kd-tree, privacy preserving