A 3-dimensional Histogram Publishing Algorithm for Spatiotemporal Data Based on Differential Privacy
MingHao Yu, Wenfen Liu, Di Chen, Shu Gao · 2022
Geospatial data collected from location-based services (LBS) systems provide a wealth of location information when analyzing spatial information. However, publishing location data directly can lead to the disclosure of sensitive personal information. Aiming at the uneven distribution of location data and the correlation between the plane region and the time dimension, as well as the problem of lower availability of the published results of the existing differential privacy location data histogram publishing algorithms, this paper proposes a 3-dimensional Histogram Publishing Algorithm based on differential privacy (SC_DPHP). First, considering the influence of time while dividing the plane region, a pretreatment method combining the time range bisection iterative cutting and plane region meshing is proposed to obtain a 3-dimensional histogram of the spatiotemporal data; secondly, to improve the availability of the published results, we combine the spectral clustering method to cluster and group the count values of the spatial decomposition cell, and then each group is added to the noise by the Laplacian mechanism. Theoretical analysis and experimental results verify that the method improves the accuracy of published data range queries while protecting privacy.