Differentially Private Histograms under Continual Observation: Streaming Selection into the Unknown
This work addresses privacy challenges in streaming data analysis for applications like real-time monitoring, offering incremental improvements over prior DP streaming algorithms.
The paper tackles the problem of releasing differentially private histograms from data streams under continual observation, generalizing previous settings to allow events as subsets of possibly unknown item universes, and achieves privacy loss scaling polylogarithmically with stream length. It presents meta-algorithms and practical methods for top-k selection and unknown domains, with concrete privacy guarantees.
We generalize the continuous observation privacy setting from Dwork et al. '10 and Chan et al. '11 by allowing each event in a stream to be a subset of some (possibly unknown) universe of items. We design differentially private (DP) algorithms for histograms in several settings, including top-$k$ selection, with privacy loss that scales with polylog$(T)$, where $T$ is the maximum length of the input stream. We present a meta-algorithm that can use existing one-shot top-$k$ DP algorithms as a subroutine to continuously release private histograms from a stream. Further, we present more practical DP algorithms for two settings: 1) continuously releasing the top-$k$ counts from a histogram over a known domain when an event can consist of an arbitrary number of items, and 2) continuously releasing histograms over an unknown domain when an event has a limited number of items.