Private and Continual Release of Statistics
Abstract
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Nov 01, 2011
- Source ID
- 10.1145/2043621.2043626
Entities
People
- Dawn Song
- Elaine Shi
- T.-h. Hubert Chan
Organizations
- Division of Computing and Communication Foundations
- Office of Naval Research
- PARC
- University of California, Berkeley
- University of Hong Kong