Reproduce “Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Rachel Cummings, Alessandro Epasto, Jieming Mao, Tamalika Mukherjee, Tingting Ou, Peilin Zhong
Researchers from Columbia University and Google Research introduce the first algorithms that enable differentially private, sublinear-space counting of distinct elements in the turnstile streaming model under continual release. The proposed methods achieve a (1+eta)-relative approximation with an additive error of O_tilde(sqrt(W)) for streams with bounded item occurrency W, and O_tilde(T^(1/3)) for arbitrary streams, significantly reducing memory requirements compared to existing linear-space solutions.
Key insights
- The stateless 'occurrency' measure provides a more tractable approach to bounding sensitivity for space-efficient differentially private distinct counting in the turnstile model.
- Careful integration and modification of existing data structures, such as KSET, including handling their deterministic failure modes, are crucial for ensuring privacy in sublinear-space streaming algorithms.
- A combination of multi-instance hashing, occurrency-based sensitivity bounding, and probabilistic blocklisting can provide robust differentially private guarantees with significantly reduced memory footprint in highly dynamic stream settings.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.