Online Streaming Sampling Publication Method Over Sliding Windows With Differential Privacy

The widespread adoption of 5 G networks and mobile devices has led to a surge in the generation of private data, creating massive data streams. Securing and continuously releasing histogram data over sliding windows in these streams has become a critical issue, as it enables understanding recent collective phenomena in data streams while preserving individual privacy. Existing state-of-the-art methods require buffering all data from each sliding window to reconstruct accurate histograms, which is unnecessary and significantly hampers efficiency. This paper proposes an online streaming sampling publication framework with differential privacy, named the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><u>P</u>ublishing <u>A</u>pproach with <u>S</u>liding window estimation-count sketch</i> (PAS), which constructs an approximate histogram without buffering each sliding window and subsequently generates publishable histograms. Specifically, we introduce a novel memory-efficient sketch structure called the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><u>S</u>liding Window <u>E</u>stimation-Count <u>S</u>ketch</i> (SES), which facilitates rapid retrieval of counts within sliding window intervals while providing guaranteed data protection. The output of this sketch structure approximates true counts while theoretically incorporating differentially private noise, thus ensuring <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(\epsilon , \delta )$</tex-math></inline-formula>-differential privacy. Moreover, to improve the speed of histogram generation and reduce processing time in PAS, we propose an adaptive histogram generation algorithm based on SES. Extensive experiments are conducted to demonstrate the effectiveness of the proposed methods in comparison with other publication methods.