Differentially Private Heatmaps

• DOI: 10.1609/aaai.v37i6.25933
• Publication Date: 2023-06-27T17:04:50Z
• Authors: Badih Ghazi; Junfeng He; Kai Kohlhoff; Ravi Kumar; Pasin Manurangsi; Vidhya Navalpakkam; Nachiappan Vallia...
• Keywords: Data set

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