  We study how to release summary statistics on a data stream subject to the
constraint of differential privacy. In particular, we focus on releasing the
family of symmetric norms, which are invariant under sign-flips and
coordinate-wise permutations on an input data stream and include $L_p$ norms,
$k$-support norms, top-$k$ norms, and the box norm as special cases. Although
it may be possible to design and analyze a separate mechanism for each
symmetric norm, we propose a general parametrizable framework that
differentially privately releases a number of sufficient statistics from which
the approximation of all symmetric norms can be simultaneously computed. Our
framework partitions the coordinates of the underlying frequency vector into
different levels based on their magnitude and releases approximate frequencies
for the "heavy" coordinates in important levels and releases approximate level
sizes for the "light" coordinates in important levels. Surprisingly, our
mechanism allows for the release of an arbitrary number of symmetric norm
approximations without any overhead or additional loss in privacy. Moreover,
our mechanism permits $(1+\alpha)$-approximation to each of the symmetric norms
and can be implemented using sublinear space in the streaming model for many
regimes of the accuracy and privacy parameters.

Data Structures and Algorithms