The Flajolet-Martin Sketch Itself Preserves Differential Privacy: Private Counting with Minimal Space
Authors: Adam Smith, Shuang Song, Abhradeep Guha Thakurta
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments: One important attribute of our algorithm is that the entire final value of the sketch including all 1/γ2 basic units but not the hash function descriptions is differentially private...In Section 3, we show that with ε = 1.0, all three estimators reach nearly the same relative error as the non-private estimator, which is below 2% using 4096 hash functions. |
| Researcher Affiliation | Collaboration | Adam Smith Boston University ads22@bu.edu Shuang Song Google Research, Brain Team shuangsong@google.com Abhradeep Thakurta Google Research, Brain Team athakurta@google.com |
| Pseudocode | Yes | Algorithm 1 AFM: Flajolet-Martin (FM) sketch for distinct elements |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code for the described methodology or links to a code repository. |
| Open Datasets | No | The paper mentions 'We consider datasets with true cardinality F0(D) ranging approximately from 2^12 to 2^20 ≈ 10^6.' but does not provide concrete access information, specific links, DOIs, repository names, or formal citations for any publicly available or open dataset. |
| Dataset Splits | No | The paper describes experiments and evaluation, but it does not specify any training, validation, or test dataset splits (e.g., percentages, sample counts, or references to predefined splits). |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., exact GPU/CPU models, processor types, or memory amounts) used for running its experiments. |
| Software Dependencies | No | The paper mentions 'For fair comparison, we implement all our algorithms in C++.' in Appendix E.1, but it does not provide specific ancillary software details such as library or solver names with version numbers. |
| Experiment Setup | Yes | We consider datasets with true cardinality F0(D) ranging approximately from 2^12 to 2^20 ≈ 10^6. |