# DPSW-Sketch: A Differentially Private Sketch Framework for Frequency Estimation over Sliding Windows (Technical Report)

arXiv: https://arxiv.org/abs/2406.07953 · HTML: https://mlsanity.com/paper/2406.07953/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 43 references that are in the map.
- First posted on arXiv 12 Jun 2024.

## Builds on (most cited first, 16 of 16)

- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Federated Heavy Hitters Discovery with Differential Privacy](https://mlsanity.com/paper/1902.08534/) (2019)
- [Differentially Private Quantiles](https://mlsanity.com/paper/2102.08244/) (2021)
- [A Smooth Binary Mechanism for Efficient Private Continual Observation](https://mlsanity.com/paper/2306.09666/) (2023)
- [Efficient Private Statistics with Succinct Sketches](https://mlsanity.com/paper/1508.06110/) (2015)
- [Differentially Private Linear Sketches: Efficient Implementations and Applications](https://mlsanity.com/paper/2205.09873/) (2022)
- [Differentially Private Continual Releases of Streaming Frequency Moment Estimations](https://mlsanity.com/paper/2301.05605/) (2023)
- [Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming](https://mlsanity.com/paper/2104.01808/) (2021)
- [Change Detection for Local Explainability in Evolving Data Streams](https://mlsanity.com/paper/2209.02764/) (2022)
- [Improved Utility Analysis of Private CountSketch](https://mlsanity.com/paper/2205.08397/) (2022)
- [Archimedes Meets Privacy: On Privately Estimating Quantiles in High Dimensions Under Minimal Assumptions](https://mlsanity.com/paper/2208.07438/) (2022)
- [Private Continual Release of Real-Valued Data Streams](https://mlsanity.com/paper/1811.03197/) (2018)
- [Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch](https://mlsanity.com/paper/2301.02457/) (2023)
- [Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space](https://mlsanity.com/paper/2105.12363/) (2021)
- [Private Counting of Distinct and k-Occurring Items in Time Windows](https://mlsanity.com/paper/2211.11718/) (2022)
- [Sketch-Flip-Merge: Mergeable Sketches for Private Distinct Counting](https://mlsanity.com/paper/2302.02056/) (2023)

## Abstract (arXiv)

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., heavy hitters), in the sliding window model. We propose textscDPSW-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 textscDPSW-Sketch provides significantly better utility-privacy trade-offs than state-of-the-art methods.