Personalized Local Differential Privacy for Multi-Dimensional Range Queries Over Mobile User Data

Multi-dimensional range queries performed on the mobile user data records become increasingly important and popular in the fields of e-commerce, social media, transportation logistics, etc. Meanwhile, mobile users usually have different privacy requirements for different attributes of the records. A straightforward and effective approach is to first get low-dimensional range query outcomes by using existing LDP mechanisms at different privacy levels, and then derive high-dimensional range query results at each level, and finally aggregate the results from all levels. However, it incurs low utility of the query results, since the non-fixed privacy budgets and the correlation between dimensions (attributes) detrimentally impact the utility of LDP methods, ultimately rendering them ineffective in practice. In this paper, we propose a new Personalized LDP approach for Multi-dimensional Range queries (PLDP-MR) over mobile user data, consisting of the user grouping, data perturbing, data re-perturbing, and range query results aggregating steps. First, PLDP-MR offers flexible dual grouping based on user-selected privacy levels and relevant attributes to obtain the corresponding one-dimensional and two-dimensional grids. PLDP-MR optimizes the grid granularity to minimize errors from perturbing users' attribute data with different LDP noises at non-fixed privacy levels. Furthermore, PLDP-MR carefully re-perturbs the LDP-noisy data from mobile users at lower privacy levels (i.e., having the higher utility) to achieve LDP with higher privacy levels and supplement the data volume of the corresponding groups. Thus, the data utility is effectively improved without additional privacy losses. Finally, PLDP-MR aggregates the frequencies in all the one-dimensional and two-dimensional grids related to the multi-dimensional range query at all query intervals and all privacy levels to derive the final query result with considering the correlation between attributes. The aggregations use maximum entropy optimization and maximum likelihood methods to further enhance its utility. The privacy and utility of PLDP-MR are analyzed, and extensive experiments demonstrate its effectiveness.