Timezone: »

Order-Invariant Cardinality Estimators Are Differentially Private
Charlie Dickens · Justin Thaler · Daniel Ting

Tue Nov 29 09:00 AM -- 11:00 AM (PST) @ Hall J #318
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.

Author Information

Charlie Dickens (Yahoo)
Justin Thaler (Georgetown University)
Daniel Ting (Meta)

More from the Same Authors