Private Counting of Distinct and k-Occurring Items in Time Windows
Private Counting of Distinct and k-Occurring Items in Time Windows
复制标题
时间窗口中不同和 k 次出现的项目的私有计数
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Jelani Nelson
中科院分区：
文献类型：
--
作者：
Badih Ghazi;Ravi Kumar;Pasin Manurangsi;Jelani Nelson
在这项工作中，我们研究的任务，估计不同的和$k$出现的项目在一个时间窗口的约束下的差分隐私（DP）。我们考虑几个变量取决于查询是否是一般的时间窗口（时间t_1 $和t_2 $之间），或被限制为累积（时间t_1 $和t_2 $之间），并取决于DP相邻关系是否是事件级或更严格的项目级。我们获得了近紧的上限和下限的DP算法的错误，这些问题。在此过程中，我们获得了一个事件级DP算法，用于在每个时间步估计在最后$W$更新中看到的不同项目的数量，误差为$W$;这回答了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).