Private and Continual Release of Statistics

被引：261

作者：

Chan, T. -H. Hubert ^{[1
]}

Shi, Elaine ^{[2
]}

Song, Dawn ^{[3
]}

机构：

[1] Univ Hong Kong, Hong Kong, Hong Kong, Peoples R China

[2] Palo Alto Res Ctr, Palo Alto, CA USA

[3] Univ Calif Berkeley, Berkeley, CA 94720 USA

来源：

ACM TRANSACTIONS ON INFORMATION AND SYSTEM SECURITY | 2011年 / 14卷 / 03期

基金：

美国国家科学基金会;

关键词：

Algorithms; Differential privacy; continual mechanism; streaming algorithm;

D O I：

10.1145/2043621.2043626

中图分类号：

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

学科分类号：

0812 ;

摘要：

We ask the question: how can Web sites and data aggregators continually release updated statistics, and meanwhile preserve each individual user's privacy? Suppose we are given a stream of 0's and 1's. We propose a differentially private continual counter that outputs at every time step the approximate number of 1's seen thus far. Our counter construction has error that is only poly-log in the number of time steps. We can extend the basic counter construction to allow Web sites to continually give top-k and hot items suggestions while preserving users' privacy.

引用

页数：24