Answering Multi-Dimensional Analytical Queries under Local Differential Privacy
Answering Multi-Dimensional Analytical Queries under Local Differential Privacy
复制标题
DOI：
10.1145/3299869.3319891
复制
发表时间：
2019-06
期刊：
影响因子：
--
通讯作者：
Tianhao Wang;Bolin Ding;Jingren Zhou;Cheng Hong;Zhicong Huang;Ninghui Li;S. Jha
中科院分区：
文献类型：
--
作者：
Tianhao Wang;Bolin Ding;Jingren Zhou;Cheng Hong;Zhicong Huang;Ninghui Li;S. Jha
多维分析（MDA）查询通常是针对事实表发出的，该事实表具有（分类或序数）维度的谓词，并且在一个或多个措施上进行了聚集。在本文中，我们研究了在当地差异隐私（LDP）下回答MDA查询的问题。在没有信任的代理的情况下，敏感维度是在发送给数据收集器之前以当地的隐私保护（LDP）方式编码的。数据收集器根据编码的维度估算MDA查询的答案。我们提出了几种LDP编码器和估计算法，以处理具有不同类型的谓词和聚合功能的大量MDA查询。我们的技术能够以紧密的误差界限回答这些查询，并在高维设置中良好地缩放（即，误差是尺寸的多组矩阵）。我们对真实和合成数据进行实验，以验证我们的理论结果，并将解决方案与基于边际估计的解决方案进行比较。
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.