Order-Invariant Cardinality Estimators Are Differentially Private
Authors: Charlie Dickens, Justin Thaler, Daniel Ting
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our analysis applies to essentially all popular cardinality estimation algorithms, and substantially generalizes and tightens privacy bounds from earlier works. Our approach is faster and exhibits a better utility-space tradeoff than prior art. ... We provide two experiments highlighting the practical benefits of our approach. |
| Researcher Affiliation | Collaboration | Charlie Dickens Yahoo charlie.dickens@yahooinc.com Justin Thaler Georgetown University justin.thaler@georgetown.edu Daniel Ting Meta dting@meta.com |
| Pseudocode | Yes | Algorithms 1: Differentially private cardinality estimation algorithms from black box sketches. ... Pseudocode for the modified algorithm... is given in Algorithm 1c. |
| Open Source Code | Yes | A small repository containing the experimental scripts and figure plotting has been provided. |
| Open Datasets | No | The paper describes abstract 'streams of samples' and does not refer to a specific named dataset, provide a link, or cite a source for public access. |
| Dataset Splits | No | The paper does not mention any validation dataset splits. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., GPU/CPU models, memory) used for running its experiments, only noting 'Wall-clock update time' measurements. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers (e.g., Python 3.x, PyTorch 1.x) needed to replicate the experiments. |
| Experiment Setup | Yes | Details of the experimental setup are in Appendix D. For Figure 1a, we simulate the algorithms (HLL, PHLL, QLL) for 210 updates for k {27, 28, . . . 212} buckets. ... For Figure 1b, we set the input cardinality at n = 220 and the privacy budget at ϵ = ln(2). We varied k {27, 28, . . . 212} and simulate the ϵ-DP methods, PHLL and QLL [22]. |