• KSII Transactions on Internet and Information Systems
    Monthly Online Journal (eISSN: 1976-7277)

Spatial Statistic Data Release Based on Differential Privacy

Vol. 13, No. 10, October 30, 2019
10.3837/tiis.2019.10.023, Download Paper (Free):


With the continuous development of LBS (Location Based Service) applications, privacy protection has become an urgent problem to be solved. Differential privacy technology is based on strict mathematical theory that provides strong privacy guarantees where it supposes that the attacker has the worst-case background knowledge and that knowledge has been applied to different research directions such as data query, release, and mining. The difficulty of this research is how to ensure data availability while protecting privacy. Spatial multidimensional data are usually released by partitioning the domain into disjointed subsets, then generating a hierarchical index. The traditional data-dependent partition methods need to allocate a part of the privacy budgets for the partitioning process and split the budget among all the steps, which is inefficient. To address such issues, a novel two-step partition algorithm is proposed. First, we partition the original dataset into fixed grids, inject noise and synthesize a dataset according to the noisy count. Second, we perform IH-Tree (Improved H-Tree) partition on the synthetic dataset and use the resulting partition keys to split the original dataset. The algorithm can save the privacy budget allocated to the partitioning process and obtain a more accurate release. The algorithm has been tested on three real-world datasets and compares the accuracy with the state-of-the-art algorithms. The experimental results show that the relative errors of the range query are considerably reduced, especially on the large scale dataset.


Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2015)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.

Cite this article

[IEEE Style]
S. Cai, X. Lyu and D. Ban, "Spatial Statistic Data Release Based on Differential Privacy," KSII Transactions on Internet and Information Systems, vol. 13, no. 10, pp. 5244-5259, 2019. DOI: 10.3837/tiis.2019.10.023.

[ACM Style]
Sujin Cai, Xin Lyu, and Duohan Ban. 2019. Spatial Statistic Data Release Based on Differential Privacy. KSII Transactions on Internet and Information Systems, 13, 10, (2019), 5244-5259. DOI: 10.3837/tiis.2019.10.023.