Answering Multi-Dimensional Analytical Queries under Local Differential Privacy

被引：58

作者：

Wang, Tianhao ^{[1
,2
]}

Ding, Bolin ^{[2
]}

Zhou, Jingren ^{[2
]}

Hong, Cheng ^{[2
]}

Huang, Zhicong ^{[2
]}

Li, Ninghui ^{[1
]}

Jha, Somesh ^{[3
]}

机构：

[1] Purdue Univ, W Lafayette, IN 47907 USA

[2] Alibaba Grp, Hangzhou, Zhejiang, Peoples R China

[3] Univ Wisconsin, Madison, WI 53706 USA

来源：

SIGMOD '19: PROCEEDINGS OF THE 2019 INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA | 2019年

关键词：

D O I：

10.1145/3299869.3319891

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：159 / 176

页数：18