  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.
