Optimal Locally Private Data Stream Analytics

Online data analytics with local privacy 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. This work demonstrates that private data analytics can be conducted online without excess utility loss, even at a constant factor. We present an optimal, streamable mechanism for local differentially private 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 during the input’s data-dependent phase. Through experiments with both synthetic and real-world datasets, our proposals have been shown to reduce error rates by 40% to 60% compared to SOTA approaches.