# Efficient Private Statistics with Succinct Sketches

arXiv: https://arxiv.org/abs/1508.06110 · HTML: https://mlsanity.com/paper/1508.06110/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Aug 2015.

## Built on by (most cited first, 10 of 10)

- [Privacy-Preserving Machine Learning: Methods, Challenges and Directions](https://mlsanity.com/paper/2108.04417/) (2021)
- [RoFL: Robustness of Secure Federated Learning](https://mlsanity.com/paper/2107.03311/) (2021)
- [Aggregation Service for Federated Learning: An Efficient, Secure, and More Resilient Realization](https://mlsanity.com/paper/2202.01971/) (2022)
- [Flamingo: Multi-Round Single-Server Secure Aggregation with Applications to Private Federated Learning](https://mlsanity.com/paper/2308.09883/) (2023)
- [Privacy Risks Analysis and Mitigation in Federated Learning for Medical Images](https://mlsanity.com/paper/2311.06643/) (2023)
- [In-depth Analysis of Privacy Threats in Federated Learning for Medical Data](https://mlsanity.com/paper/2409.18907/) (2024)
- [Distributed Differentially Private Data Analytics via Secure Sketching](https://mlsanity.com/paper/2412.00497/) (2024)
- [Enhanced Privacy and Communication Efficiency in Non-IID Federated Learning with Adaptive Quantization and Differential Privacy](https://mlsanity.com/paper/2604.23426/) (2026)
- [Bayesian nonparametric estimation of coverage probabilities and distinct counts from sketched data](https://mlsanity.com/paper/2209.02135/) (2022)
- [DPSW-Sketch: A Differentially Private Sketch Framework for Frequency Estimation over Sliding Windows (Technical Report)](https://mlsanity.com/paper/2406.07953/) (2024)

## Abstract (arXiv)

Large-scale collection of contextual information is often essential in order to gather statistics, train machine learning models, and extract knowledge from data. The ability to do so in a em privacy-preserving way -- i.e., without collecting fine-grained user data -- enables a number of additional computational scenarios that would be hard, or outright impossible, to realize without strong privacy guarantees. In this paper, we present the design and implementation of practical techniques for privately gathering statistics from large data streams. We build on efficient cryptographic protocols for private aggregation and on data structures for succinct data representation, namely, Count-Min Sketch and Count Sketch. These allow us to reduce the communication and computation complexity incurred by each data source (e.g., end-users) from linear to logarithmic in the size of their input, while introducing a parametrized upper-bounded error that does not compromise the quality of the statistics. We then show how to use our techniques, efficiently, to instantiate real-world privacy-friendly systems, supporting recommendations for media streaming services, prediction of user locations, and computation of median statistics for Tor hidden services.