Skip to yearly menu bar Skip to main content


Poster

Sublinear Space Private Algorithms Under the Sliding Window Model

Jalaj Upadhyay

Pacific Ballroom #174

Keywords: [ Privacy-preserving Statistics and Machine Learning ]


Abstract: The Differential privacy overview of Apple states, Apple retains the collected data for a maximum of three months." Analysis of recent data is formalized by the {\em sliding window model}. This begs the question: what is the price of privacy in the sliding window model? In this paper, we study heavy hitters in the sliding window model with window size w. Previous works of Chan et al. (2012) estimates heavy hitters with an error of order θw for a constant θ>0. In this paper, we give an efficient differentially private algorithm to estimate heavy hitters in the sliding window model with O~(w3/4) additive error and using O~(w) space.

Live content is unavailable. Log in and register to view live content