Order-Invariant Cardinality Estimators Are Differentially Private

November 8, 2022

Abstract

We consider privacy in the context of streaming algorithms for cardinality estimation. We show that a large class of algorithms all satisfy $\epsilon$-differential privacy, so long as (a) the algorithm is combined with a simple down-sampling procedure, and (b) the input stream cardinality is $\Omega(k/\epsilon)$. Here, $k$ is a certain parameter of the sketch that is always at most the sketch size in bits, but is typically much smaller. We also show that, even with no modification, algorithms in our class satisfy $(\epsilon, \delta)$-differential privacy, where $\delta$ falls exponentially with the stream cardinality. 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.

Download

Publication Type

Paper

Conference / Journal Name

Neurips

Authors

Charlie Dickens

Justing Thaler

Daniel Ting

BibTeX


@inproceedings{
    author = {},
    title = {‌Order-Invariant Cardinality Estimators Are Differentially Private‌},
    booktitle = {Proceedings of Neurips‌},
    year = {‌2022‌}
}