Efficient Privacy-Preserving Streaming Histogram Publication via Sampling-Based Shuffled Method

The rapid growth of web technologies and the industrial Internet has resulted in massive data streams that are essential for real time decision-making applications. A critical challenge lies in dynamically publishing histograms for the most recent <i>w</i> elements within sliding windows while ensuring individual privacy protection. Although Shuffle Differential Privacy (SDP) provides strong privacy guarantees, existing methods for SDP histograms face huge time and space overhead, as they require caching all sliding window elements. This limitation hinders their practicality in large-scale, real time settings. To overcome these limitations, this paper proposes Sampling-based Shuffle Differential Privacy (SSDP), an efficient algorithm for the publication of privacy-preserving histogram. Central to SSDP is the Online Sampling Sketch Structure (OSSS), which dynamically captures essential data patterns from streaming windows through adaptive sampling, enabling approximate histogram generation with dramatically reduced time and space complexities. To counter advanced privacy threats, SSDP integrates targeted noise injection and a hash-optimized Generalized Randomized Response (GRR) mechanism, providing robust defenses against shuffling and publisher collusion attacks. Moreover, a correlated unbiased estimation mechanism enhances both privacy preservation and data utility. Extensive experiments on real-world datasets demonstrate the superiority of SSDP, achieving up to 40% reduction in processing time compared to state-of-the-art methods, with minimal loss in utility.