Differentially Private Heatmaps

We consider the task of producing heatmaps from users' aggregated data while protecting their privacy. We give a differentially private (DP) algorithm for this task and demonstrate its advantages over previous algorithms on real-world datasets. Our core algorithmic primitive is a DP procedure that takes in a set of distributions and produces an output that is close in Earth Mover's Distance (EMD) to the average of the inputs. We prove theoretical bounds on the error of our algorithm under a certain sparsity assumption and that these are essentially optimal.

Authors

• Badih Ghazi Google Research, Mountain View, CA
• Junfeng He Google Research, Mountain View, CA
• Kai Kohlhoff Google Research, Mountain View, CA
• Ravi Kumar
• Pasin Manurangsi
• Vidhya Navalpakkam Google Research, Mountain View, CA
• Nachiappan Valliappan Google Research, Mountain View, CA

Keywords

• ML: Clustering
• ML: Privacy-Aware ML