Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space

We prove that mathbbFp sketch, a well-celebrated streaming algorithm for frequency moments estimation, is differentially private as is when p∈(0, 1]. mathbbFp sketch uses only polylogarithmic space, exponentially better than existing DP baselines and only worse than the optimal non-private baseline by a logarithmic factor. The evaluation shows that mathbbFp sketch can achieve reasonable accuracy with strong privacy guarantees.