# Towards Sparse Federated Analytics: Location Heatmaps under Distributed Differential Privacy with Secure Aggregation

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 76 references that are in the map.
- First posted on arXiv 3 Nov 2021.

## Builds on (most cited first, 30 of 31)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [A Hybrid Approach to Privacy-Preserving Federated Learning](https://mlsanity.com/paper/1812.03224/) (2018)
- [Practical Secure Aggregation for Federated Learning on User-Held Data](https://mlsanity.com/paper/1611.04482/) (2016)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation](https://mlsanity.com/paper/2102.06387/) (2021)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [The Privacy Blanket of the Shuffle Model](https://mlsanity.com/paper/1903.02837/) (2019)
- [The Skellam Mechanism for Differentially Private Federated Learning](https://mlsanity.com/paper/2110.04995/) (2021)
- [FastSecAgg: Scalable Secure Aggregation for Privacy-Preserving Federated Learning](https://mlsanity.com/paper/2009.11248/) (2020)
- [Discrete Distribution Estimation under Local Privacy](https://mlsanity.com/paper/1602.07387/) (2016)
- [Prochlo: Strong Privacy for Analytics in the Crowd](https://mlsanity.com/paper/1710.00901/) (2017)
- [Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation](https://mlsanity.com/paper/2001.03618/) (2020)
- [Private Summation in the Multi-Message Shuffle Model](https://mlsanity.com/paper/2002.00817/) (2020)
- [Privacy Odometers and Filters: Pay-as-you-Go Composition](https://mlsanity.com/paper/1605.08294/) (2016)
- [Federated Heavy Hitters Discovery with Differential Privacy](https://mlsanity.com/paper/1902.08534/) (2019)
- [Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacy](https://mlsanity.com/paper/1702.00610/) (2017)
- [Practical Locally Private Heavy Hitters](https://mlsanity.com/paper/1707.04982/) (2017)
- [PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions](https://mlsanity.com/paper/1601.03229/) (2016)
- [Heavy Hitters and the Structure of Local Privacy](https://mlsanity.com/paper/1711.04740/) (2017)
- [Separating Local & Shuffled Differential Privacy via Histograms](https://mlsanity.com/paper/1911.06879/) (2019)
- [Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead](https://mlsanity.com/paper/2106.04247/) (2021)
- [Private Aggregation from Fewer Anonymous Messages](https://mlsanity.com/paper/1909.11073/) (2019)
- [Pure Differentially Private Summation from Anonymous Messages](https://mlsanity.com/paper/2002.01919/) (2020)
- [Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs](https://mlsanity.com/paper/2008.07180/) (2020)
- [Connecting Robust Shuffle Privacy and Pan-Privacy](https://mlsanity.com/paper/2004.09481/) (2020)
- [Marginal Release Under Local Differential Privacy](https://mlsanity.com/paper/1711.02952/) (2017)
- [A Framework for Evaluating Epidemic Forecasts](https://mlsanity.com/paper/1703.09828/) (2017)
- [Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming](https://mlsanity.com/paper/2104.01808/) (2021)

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

- [PrE-Text: Training Language Models on Private Federated Data in the Age of LLMs](https://mlsanity.com/paper/2406.02958/) (2024)
- [Federated Select: A Primitive for Communication- and Memory-Efficient Federated Learning](https://mlsanity.com/paper/2208.09432/) (2022)
- [FedWalk: Communication Efficient Federated Unsupervised Node Embedding with Differential Privacy](https://mlsanity.com/paper/2205.15896/) (2022)
- [Location Leakage in Federated Signal Maps](https://mlsanity.com/paper/2112.03452/) (2021)
- [Differentially Private Heavy Hitter Detection using Federated Analytics](https://mlsanity.com/paper/2307.11749/) (2023)
- [PAPAYA Federated Analytics Stack: Engineering Privacy, Scalability and Practicality](https://mlsanity.com/paper/2412.02340/) (2024)
- [How to Securely Shuffle? A survey about Secure Shufflers for privacy-preserving computations](https://mlsanity.com/paper/2507.01487/) (2025)
- [Federated Computing -- Survey on Building Blocks, Extensions and Systems](https://mlsanity.com/paper/2404.02779/) (2024)
- [DP-Hype: Federated Differentially Private Hyperparameter Search](https://mlsanity.com/paper/2510.04902/) (2025)
- [TAPAS: Efficient Two-Server Asymmetric Private Aggregation Beyond Prio(+)](https://mlsanity.com/paper/2603.19949/) (2026)

## Abstract (arXiv)

We design a scalable algorithm to privately generate location heatmaps over decentralized data from millions of user devices. It aims to ensure differential privacy before data becomes visible to a service provider while maintaining high data accuracy and minimizing resource consumption on users' devices. To achieve this, we revisit distributed differential privacy based on recent results in secure multiparty computation, and we design a scalable and adaptive distributed differential privacy approach for location analytics. Evaluation on public location datasets shows that this approach successfully generates metropolitan-scale heatmaps from millions of user samples with a worst-case client communication overhead that is significantly smaller than existing state-of-the-art private protocols of similar accuracy.