Answering private multidimensional analytical queries with hierarchical structure
Zhenjie Zhang, 丹 周, 雅鑫 徐, 东岱 林, 守领 纪, 小峰 孟 · Scientia Sinica Informationis · 2023
Given a relational table T whose tuples are distributed among n users, we study differentially private algorithms for answering multidimensional analytical (MDA) queries over T. Existing solutions to this problem mostly employ hierarchical trees and optimal local hashing (OLH) mechanisms to index and perturb users' tuples, respectively. However, OLH with hierarchical trees, cannot prevent privacy leakage of root node combinations. To remedy the shortcomings of the existing solutions, this paper proposes a locally differentially private algorithm called hierarchical structure for MDA (H4MDA) to answer MDA queries. With H4MDA, we first propose a horizontal Generalized Random Response (HGRR) mechanism to perturb users' tuples, which refrains from combining root nodes to prevent privacy leaks. To take full advantage of the vertical structure of the tree, we further propose, in contrast to HGRR, a longitudinal GRR mechanism with fake data (LGRR-FD) to perturb users' tuples. The LGRR-FD reports the noise result with fake data to the collector to prevent the privacy disclosure of the leaf nodes. In addition, we propose another longitudinal GRR (LGRR) mechanism that discards the leaf node level to report the noise tuples. To improve the utility of MDA queries, based on LGRR reports, the collector uses the local consistency technique to reconstruct the leaf level visited by some MDA queries. A theoretical analysis and extensive experiments show that our algorithms can effectively improve the utility of MDA queries and outperform existing solutions.