Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model

2025/05/29 by Rachel Cummings, Alessandro Epasto, Cummings, Rachel +9
Computer Science · #Cryptography and Data Security #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Privacy-Preserving Technologies in Data

paper · pdf · doi:10.48550/arxiv.2505.23682

openalex publication_date 2025/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The turnstile continual release model of differential privacy captures scenarios where a privacy-preserving real-time analysis is sought for a dataset evolving through additions and deletions. In typical applications of real-time data analysis, both the length of the stream T and the size of the universe |U| from which data come can be extremely large. This motivates the study of private algorithms in the turnstile setting using space sublinear in both T and |U|. In this paper, we give the first sublinear space differentially private algorithms for the fundamental problem of counting distinct elements in the turnstile streaming model. Our algorithm achieves, on arbitrary streams, O_η(T^1/3) space and additive error, and a (1+η)-relative approximation for all η∈ (0,1). Our result significantly improves upon the space requirements of the state-of-the-art algorithms for this problem, which is linear, approaching the known Ω(T^1/4) additive error lower bound for arbitrary streams. Moreover, when a bound W on the number of times an item appears in the stream is known, our algorithm provides O_η(√(W)) additive error, using O_η(√(W)) space. This additive error asymptotically matches that of prior work which required instead linear space. Our results address an open question posed by [Jain, Kalemaj, Raskhodnikova, Sivakumar, Smith, Neurips23] about designing low-memory mechanisms for this problem. We complement these results with a space lower bound for this problem, which shows that any algorithm that uses similar techniques must use space Ω(T^1/3) on arbitrary streams.

Citations

• Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
• Private Data Stream Analysis for Universal Symmetric Norm Estimation
• Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation
• On Differential Privacy and Adaptive Data Analysis with Bounded Space
• Sketch-Flip-Merge: Mergeable Sketches for Private Distinct Counting
• Differentially Private Continual Releases of Streaming Frequency Moment Estimations
• Private Counting of Distinct and k-Occurring Items in Time Windows
• How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity
• Order-Invariant Cardinality Estimators Are Differentially Private
• Differentially Private Algorithms for Graphs Under Continual Observation
• Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space
• Efficient Differentially Private F₀ Linear Sketching
• Cardinality Estimators do not Preserve Privacy
• Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds
• Dynamic Graph Stream Algorithms in o(n) Space
• The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy
• Finding repeated elements

Related

• Private Counting of Distinct Elements in the Turnstile Model and Extensions
• Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation
• Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
• Differentially Private Continual Releases of Streaming Frequency Moment Estimations
• Bounded Space Differentially Private Quantiles