Answering Multi-Dimensional Analytical Queries under Local Differential Privacy
By Tianhao Wang, Bolin Ding, Jingren Zhou, Cheng Hong, Zhicong Huang, Ninghui Li, Somesh Jha. 2019
109 citations recorded by the source corpus.
Multi-dimensional analytical (MDA) queries are often issued against a fact table with predicates on (categorical or ordinal) dimensions and aggregations on one or more measures. In this paper, we study the problem of answering MDA queries under local differential privacy (LDP). In the absence of a trusted agent, sensitive dimensions are encoded in a privacy-preserving (LDP) way locally before being sent to the data collector. The data collector estimates the answers to MDA queries, based on the encoded dimensions. We propose several LDP encoders and estimation algorithms, to handle a large class of MDA queries with different types of predicates and aggregation functions. Our techniques are able to answer these queries with tight error bounds and scale well in high-dimensional settings (i.e., error is polylogarithmic in dimension sizes). We conduct experiments on real and synthetic data to verify our theoretical results, and compare our solution with marginal-estimation based solutions.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
Citations in the corpus
- Improving utility and security of the shuffler-based differential privacy (2019, background): “This desirable feature of LDP has led to wider deployment by industry [31, 1, 23, 53].”
- Practical and Robust Privacy Amplification with Multi-Party Differential Privacy (2019, background): “There also exist relaxed models that seem incompatible with the shuffler model, i.e., [10] considers the inferring probability as the adversary’s power; and [38] utilizes the linkage between each user’s sensitive and public attributes.”