Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space

2021/05/26 by Lun Wang, Wang, Lun, Iosif Pinelis +3 · 2 citations
Computer Science · #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Internet Traffic Analysis and Secure E-voting #Privacy-Preserving Technologies in Data

paper · pdf · doi:10.48550/arxiv.2105.12363

openalex publication_date 2021/05/26 · openalex created_date 2021/10/11 · openalex updated_date 2026/07/28

Abstract

We prove that \mathbbF_p sketch, a well-celebrated streaming algorithm for frequency moments estimation, is differentially private as is when p∈(0, 1]. \mathbbF_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 \mathbbF_p sketch can achieve reasonable accuracy with strong privacy guarantees.

Citations

• Finding frequent items in data streams
• Private False Discovery Rate Control

Cited by

• Unbiased Insights: Optimal Streaming Algorithms for ℓ_p Sampling, the Forget Model, and Beyond
• Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model

Related

• Differentially Private Continual Releases of Streaming Frequency Moment Estimations
• Private Federated Frequency Estimation: Adapting to the Hardness of the Instance
• Local Differentially Private Frequency Estimation based on Learned Sketches
• Tight Lower Bound for Linear Sketches of Moments
• Differentially Private Linear Sketches: Efficient Implementations and Applications