Differential Private Data Stream Analytics in the Local and Shuffle Models
Shaowei Wang, Jin Li, Yun Peng, Kongyang Chen, Wei Yang, Hui Lan Jiang, Jin Li · IEEE Transactions on Mobile Computing · 2025
We study online data analytics with differential privacy (DP) in decentralized settings. Specifically, online data analytics with local DP protection is widely adopted in real-world applications. Despite numerous endeavors in this field, significant gaps in utility and functionality remain when compared to its offline counterpart. We present an optimal, streamable mechanism:ExSub, for local DP sparse vector estimation. The mechanism enables a range of online analytics on streaming binary vectors, including multi-dimensional binary, categorical, or set-valued data. By leveraging the negative correlation of occurrence events in the sparse vector, we attain an optimal error rate under local privacy constraints, only requiring streamable computations. To surpass the error barrier of local privacy, we also studyExSubrandomizer in the newly emerging (single-message) shuffle model of DP, and provide nearly-tight privacy amplification bounds therein. Additionally, we leverage the online shuffle model that independently permutes users' messages at each timestamp, to design a simplified randomization strategy that can approximately reach Gaussian accuracy in central DP. Through experiments with both synthetic and real-world datasets,ExSubmechanism in the local model have been shown to reduce error by$40\%-60\%$compared to SOTA approaches. TheExSubin the shuffle model can further reduce over$85\%$error, and the online shuffle protocol reduces over$99.7\%$error.