论文标题
时间窗口中不同的和k型项目的私人计数
Private Counting of Distinct and k-Occurring Items in Time Windows
论文作者
论文摘要
在这项工作中，我们研究了在差异隐私（DP）的约束下，在时间窗口中估计不同和$ k $的项目数量的任务。我们考虑了几种变体，具体取决于查询是在一般时间窗口上（$ t_1 $和$ t_2 $），还是仅限于累积（在$ 1 $ 1 $和$ t_2 $之间），并且取决于DP相邻的关系是事件级别是事件级别，还是更严格的项目级别。对于这些问题，我们在DP算法的误差上获得了几乎紧密的上限和下限。在途中，我们获得了一个事件级的DP算法，用于在每个时间步骤中估算最后一个$ W $更新中看到的不同项目的数量，其中具有$ W $的错误polygarithmic；这回答了Bolot等人的一个公开问题。 （ICDT 2013）。
In this work, we study the task of estimating the numbers of distinct and $k$-occurring items in a time window under the constraint of differential privacy (DP). We consider several variants depending on whether the queries are on general time windows (between times $t_1$ and $t_2$), or are restricted to being cumulative (between times $1$ and $t_2$), and depending on whether the DP neighboring relation is event-level or the more stringent item-level. We obtain nearly tight upper and lower bounds on the errors of DP algorithms for these problems. En route, we obtain an event-level DP algorithm for estimating, at each time step, the number of distinct items seen over the last $W$ updates with error polylogarithmic in $W$; this answers an open question of Bolot et al. (ICDT 2013).
