The sliding window model of computation captures scenarios in which data are
continually arriving in the form of a stream, and only the most recent $w$
items are used for analysis. In this setting, an algorithm needs to accurately
track some desired statistics over the sliding window using a small space. When
data streams contain sensitive information about individuals, the algorithm is
also urgently needed to provide a provable guarantee of privacy. In this paper,
we focus on the two fundamental problems of privately (1) estimating the
frequency of an arbitrary item and (2) identifying the most frequent items
(i.e., \emph{heavy hitters}), in the sliding window model. We propose
\textsc{DPSW-Sketch}, a sliding window framework based on the count-min sketch
that not only satisfies differential privacy over the stream but also
approximates the results for frequency and heavy-hitter queries within bounded
errors in sublinear time and space w.r.t.~$w$. Extensive experiments on five
real-world and synthetic datasets show that \textsc{DPSW-Sketch} provides
significantly better utility-privacy trade-offs than state-of-the-art methods.

在滑动窗口模型中，提出了 DPSW-Sketch，一种基于计数最小化技术的算法，能够满足隐私性要求，并且在子线性时间和空间内近似估计任意项目的频率和重要项，实验结果显示其在效用和隐私权之间取得显著的权衡。