Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space
This provides a highly efficient solution for privacy-preserving data stream analysis, with broad applications in real-time monitoring and analytics.
The paper tackled the problem of estimating fractional frequency moments in data streams with differential privacy, showing that the existing $\mathbb{F}_p$ sketch algorithm is inherently private for $p$ in (0,1], achieving polylogarithmic space usage, which is exponentially better than prior DP methods and only a logarithmic factor worse than non-private optimal.
We prove that $\mathbb{F}_p$ sketch, a well-celebrated streaming algorithm for frequency moments estimation, is differentially private as is when $p\in(0, 1]$. $\mathbb{F}_p$ 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 $\mathbb{F}_p$ sketch can achieve reasonable accuracy with strong privacy guarantees.