Research map / Federated learning and privacy / Differential privacy
Counting Distinct Elements Under Person-Level Differential Privacy
Thomas Steinke, Alexander Knop
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace uniform sampling with matching-based counting (ablation) | DP distinct count · Amazon Fashion, DP Max Utility | median distinct count: 899.1 -> 1319.1 | Improved |
| replace uniform sampling with matching-based counting (ablation) | DP distinct count · Amazon Industrial and Scientific | median distinct count: 24701.1 -> 36198.9 | Improved |
| replace uniform sampling with matching-based counting (ablation) | DP distinct count · Reddit | median distinct count: 95375.5 -> 102512.6 | Improved |
| replace uniform sampling with matching-based counting (ablation) | DP distinct count · IMDB | median distinct count: 50053.7 -> 98670.4 | Improved |
| use exact maximum matching instead of greedy maximal matching (ablation) | DP distinct count · Amazon Fashion | median distinct count: 1224.4 -> 1319.1 | Improved |
| use exact maximum matching instead of greedy maximal matching (ablation) | DP distinct count · Reddit, IMDB | median distinct count: 102289.6 -> 102512.6 | No clear effect |
| select bound with GEM (DP Max Utility) instead of 90th percentile contribution (ablation) | DP Matching · Amazon Fashion | median distinct count: 1444.7 -> 1319.1 | Mixed |
| select bound with GEM instead of 90th percentile contribution (ablation) | DP Matching · Amazon Industrial and Scientific | median distinct count: 36651.7 -> 36198.9 | Mixed |
| select bound with GEM instead of 90th percentile contribution (ablation) | DP Matching · IMDB | spread of estimate (10th-90th percentile): 98354.2-99164.2 -> 98555.6-98726.8 | Improved |
| select bound with GEM instead of 90th percentile contribution (ablation) | DP Matching · contribution bound size | median chosen bound: 75 -> 18.5 | Improved |
| add DP noise to counting after private bound selection (ablation) | DP Matching · Reddit | median distinct count: 102501.5 -> 102512.6 | No clear effect |
| make bound selection private (GEM) vs exact maximization of utility (ablation) | Matching · Amazon Fashion | median distinct count: 1428 -> 1317 | Hurt |
Closest papers by meaning
- The Flajolet-Martin Sketch Itself Preserves Differential Privacy: Private Counting with Minimal Space (NeurIPS 2020 · similarity 0.89)
- On Computing Pairwise Statistics with Local Differential Privacy (NeurIPS 2023 · similarity 0.88)
- Privately Counting Partially Ordered Data (ICLR 2025 · similarity 0.86)
- Private Continual Counting of Unbounded Streams (NeurIPS 2025 · similarity 0.86)
- Improved Bounds for Pure Private Agnostic Learning: Item-Level and User-Level Privacy (ICML 2024 · similarity 0.86)
- Instance-Specific Asymmetric Sensitivity in Differential Privacy (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
