论文标题
订单不变的基数估计器在差异上是私有的
Order-Invariant Cardinality Estimators Are Differentially Private
论文作者
论文摘要
我们考虑在流算算法的基础估计的上下文中考虑隐私。我们表明，只要（a）算法与简单的下采样过程相结合，并且（b）输入流的基数为$ω（k/ε）$，则一大类算法都满足$ε$ -Differential私密性。在这里，$ k $是草图的某些参数，最多总是绘制的尺寸，但通常要小得多。我们还表明，即使没有修改，我们的类中的算法也满足$（ε，δ）$ - 差异隐私，其中$δ$与流基数呈指数增长。 我们的分析本质上适用于所有流行的基数估计算法，并大大概括并收紧了早期作品的隐私范围。
We consider privacy in the context of streaming algorithms for cardinality estimation. We show that a large class of algorithms all satisfy $ε$-differential privacy, so long as (a) the algorithm is combined with a simple down-sampling procedure, and (b) the cardinality of the input stream is $Ω(k/ε)$. 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 $(ε, δ)$-differential privacy, where $δ$ 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.
