Private and Continual Release of Statistics

TitlePrivate and Continual Release of Statistics
Publication TypeJournal Articles
Year of Publication2011
AuthorsChan HT-H, Elaine Shi, Song D
JournalACM Transactions on Information and System Security (TISSEC)
Pagination26:1 - 26:24
Date Published2011
ISBN Number1094-9224
Keywordscontinual mechanism, Differential privacy, streaming algorithm

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.