# Differentially Private Continual Releases of Streaming Frequency Moment Estimations

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jan 2023.

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

- [Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension](https://mlsanity.com/paper/2304.04397/) (2023)
- [Differentially Private Attention Computation](https://mlsanity.com/paper/2305.04701/) (2023)
- [Beyond Classical Attention: Quantum Attention for Scalable Computation](https://mlsanity.com/paper/2307.08045/) (2023)
- [A Unifying Framework for Differentially Private Sums under Continual Observation](https://mlsanity.com/paper/2307.08970/) (2023)
- [Online Differentially Private Synthetic Data Generation](https://mlsanity.com/paper/2402.08012/) (2024)
- [Binned Group Algebra Factorization for Differentially Private Continual Counting](https://mlsanity.com/paper/2504.04398/) (2025)
- [Concurrent Shuffle Differential Privacy Under Continual Observation](https://mlsanity.com/paper/2301.12535/) (2023)
- [Differential Privacy for Clustering Under Continual Observation](https://mlsanity.com/paper/2307.03430/) (2023)
- [Differentially Private Clustering in Data Streams](https://mlsanity.com/paper/2307.07449/) (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)

The streaming model of computation is a popular approach for working with large-scale data. In this setting, there is a stream of items and the goal is to compute the desired quantities (usually data statistics) while making a single pass through the stream and using as little space as possible. Motivated by the importance of data privacy, we develop differentially private streaming algorithms under the continual release setting, where the union of outputs of the algorithm at every timestamp must be differentially private. Specifically, we study the fundamental ℓp (p∈ [0,+∞)) frequency moment estimation problem under this setting, and give an varepsilon-DP algorithm that achieves (1+η)-relative approximation (forall η∈(0,1)) with polylog(Tn) additive error and uses polylog(Tn)· max(1, n1-2/p) space, where T is the length of the stream and n is the size of the universe of elements. Our space is near optimal up to poly-logarithmic factors even in the non-private setting. To obtain our results, we first reduce several primitives under the differentially private continual release model, such as counting distinct elements, heavy hitters and counting low frequency elements, to the simpler, counting/summing problems in the same setting. Based on these primitives, we develop a differentially private continual release level set estimation approach to address the ℓp frequency moment estimation problem. We also provide a simple extension of our results to the harder sliding window model, where the statistics must be maintained over the past W data items.