Description
Linear sketches have been widely adopted to process fast data streams, and they can be used to accurately answer frequency estimation, approximate top K items, and summarize data distributions. When data are sensitive, it is desirable to provide privacy guarantees for linear sketches to preserve private information while delivering useful results with theoretical bounds. To address these challenges, we propose differentially private linear sketches with high privacy-utility trade-offs for frequency, quantile, and top K approximations.