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 w 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.

Approximate duplicate detection in data streams aims to determine whether an item is present within a small subsequence of the data stream. It is a fundamental query problem needed in several network applications, such as web crawling and Radio Frequency Identification (RFID) tag management. Most of the existing algorithms are not space-efficient as they overlook the distributional information of query frequency and membership likelihood. In this paper, we propose CEll Bloom Filter (CEBF) algorithm, a space-efficient data structure designed by adopting a block-wise updating strategy, to solve this problem, and two typical distributions are considered: two typical distributions: (1) uniform query frequency of items, and (2) uniform membership likelihood of items. For an arbitrary sliding window size n and an arbitrary average false positive rate $\epsilon \in (0,1)$, the proposed algorithm needs approximately $O(n{\log }_2(1/\epsilon ))$ bits, which is significantly less than the number of bits used in existing methods. Space lower bound is also derived for these two typical distributions, which demonstrates that the proposed algorithm is near-optimal in terms of space consumption. Experiments are conducted on both synthetic and real datasets, and the experimental results clearly demonstrate that the proposed method is clearly and significantly more effective and promising compared to existing other methods.

Continuously publishing histograms in data streams is crucial to many real-time applications, as it provides not only critical statistical information, but also reduces privacy leaking risk. As the importance of elements usually decreases over time in data streams, in this paper we model a data stream by a sequence of weighted sliding windows, and then study how to publish histograms over these windows continuously. The existing literature can hardly solve this problem in a real-time way, because they need to buffer all elements in each sliding window, resulting in high computational overhead and prohibitive storage burden. In this paper, we overcome this drawback by proposing an online algorithm denoted by Efficient Streaming Histogram Publishing (ESHP) to continuously publish histograms over weighted sliding windows. Specifically, our method first creates a novel sketching structure, called Approximate-Estimate Sketch (AESketch), to maintain the counting information of each histogram interval at every time instance; then, it creates histograms that satisfy the differential privacy requirement by smartly adding appropriate noise values into the sketching structure. Extensive experimental results and rigorous theoretical analysis demonstrate that the ESHP method can offer equivalent data utility with significantly lower computational overhead and storage costs when compared to other existing methods.