Differentially private approximate distinct-counting sketches

A method, comprising:

• determining a first non-private probabilistic cardinality estimator for a first dataset;
• converting the first non-private probabilistic cardinality estimator to a first private probabilistic cardinality estimator for the first dataset with a first noise level;
• merging the first private probabilistic cardinality estimator for the first dataset with a second probabilistic cardinality estimator for a second dataset with a second noise level to produce a merged probabilistic cardinality estimator for the first dataset and the second dataset combined together based at least in part on the first noise level and the second noise level;
• and
• estimating a number of unique elements in the first dataset and the second dataset combined together based on the merged probabilistic cardinality estimator for the first dataset and the second dataset combined together.

A computer program product embodied in a non-transitory computer readable medium and comprising computer instructions for:

• determining a first non-private probabilistic cardinality estimator for a first dataset;
• converting the first non-private probabilistic cardinality estimator to a first private probabilistic cardinality estimator for the first dataset with a first noise level;
• merging the first private probabilistic cardinality estimator for the first dataset with a second probabilistic cardinality estimator for a second dataset with a second noise level to produce a merged probabilistic cardinality estimator for the first dataset and the second dataset combined together based at least in part on the first noise level and the second noise level;
• and
• estimating a number of unique elements in the first dataset and the second dataset combined together based on the merged probabilistic cardinality estimator for the first dataset and the second dataset combined together.