Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model
Rachel CummingsColumbia University [email protected] Alessandro EpastoGoogle Research [email protected] Jieming MaoGoogle Research [email protected], Tamalika MukherjeeColumbia University [email protected], Tingting OuColumbia University [email protected] Peilin ZhongGoogle Research peilinz@g · 2025
Read Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model by Rachel CummingsColumbia University [email protected] Alessandro EpastoGoogle Research [email protected] Jieming MaoGoogle Research [email protected], Tamalika MukherjeeColumbia University [email protected], Tingting OuColumbia University [email protected] Peilin ZhongGoogle Research peilinz@g (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-23682.txt.
Description
Rachel Cummings and five co-authors designed privacy-preserving algorithms in twenty twenty-five for counting distinct elements in streams that gain and lose items. Real-time analytics increasingly demand differential privacy under continual release, where data evolve through insertions and deletions. The catch: streams and universes are huge, so memory must stay far below linear.
The authors give the first sublinear-space private algorithms for distinct counting in this turnstile model. Their method uses roughly cubic-root-of-length space with matching additive error, plus a relative approximation — approaching the known error lower bound while prior methods needed linear space. When each item's frequency is bounded, error and space both drop to about the square root of that bound. A matching space lower bound closes the question.
Catalog record
| CREATOR | Rachel CummingsColumbia University [email protected] Alessandro EpastoGoogle Research [email protected] Jieming MaoGoogle Research [email protected], Tamalika MukherjeeColumbia University [email protected], Tingting OuColumbia University [email protected] Peilin ZhongGoogle Research peilinz@g |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 121 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-23682