SlideDP: A Time-Aware and Private Sketch for Cardinality Estimation over Sliding Windows

Cardinality estimation over sliding windows is a fundamental task in data stream analytics. While sketch-based methods offer efficient approximations with low memory usage, they inherently lack data privacy protection, making them vulnerable to inference attacks when shared across different parties or queried repeatedly. To address this issue, we propose SlideDP, a novel sketch that achieves accurate and efficient cardinality estimation under local differential privacy (LDP) in sliding window settings. SlideDP maintains a compact two-dimensional array, where each cell contains a 1-bit register and a small counter to jointly encode the presence and temporal validity of elements. Privacy is enforced via randomized response applied to each register, while a clock-based decay mechanism periodically decrements counters to track element expiration without requiring explicit timestamps. To reduce computational overhead, SlideDP incorporates ordered Poisson sampling for efficient updates. We further develop a concrete probabilistic model to support accurate estimation with theoretical guarantees. Experiments on both synthetic and real-world datasets show that SlideDP achieves accuracy comparable to non-private methods. In particular, when the window cardinality exceeds \(2^{15}\) , SlideDP maintains a relative error of approximately 5% using only 256KB of memory.