Skip to yearly menu bar Skip to main content


Order-Invariant Cardinality Estimators Are Differentially Private

Charlie Dickens · Justin Thaler · Daniel Ting

Hall J (level 1) #318

Keywords: [ cardinality estimation ] [ differential privacy ] [ streaming algorithms ] [ distinct elements ]

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.

Chat is not available.