# Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space

arXiv: https://arxiv.org/abs/2105.12363 · HTML: https://mlsanity.com/paper/2105.12363/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2021.

## Built on by (most cited first, 2 of 2)

- [On Differential Privacy and Adaptive Data Analysis with Bounded Space](https://mlsanity.com/paper/2302.05707/) (2023)
- [DPSW-Sketch: A Differentially Private Sketch Framework for Frequency Estimation over Sliding Windows (Technical Report)](https://mlsanity.com/paper/2406.07953/) (2024)

## Abstract (arXiv)

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.