Optimizing Hierarchical Queries for the Attribution Reporting API
Matt Dawson, Badih Ghazi, Pritish Kamath, Kapil Kumar, Ravi Kumar, Bo Luan, Pasin Manurangsi, Nishanth Mundru, Harikesh Nair, Adam Sealfon and Shengyu Zhu
We study the task of performing hierarchical queries based on summary reports from the Attribution Reporting API for ad conversion measurement. We demonstrate that using methods from optimization and the literature on differentially private algorithms can help cope with the noise introduced by privacy guardrails in the API. In particular, we present algorithms for (i) denoising the API outputs and ensuring consistency across different levels of the tree, and (ii) optimizing the privacy budget across different levels of the tree. We provide an experimental evaluation of the proposed algorithms on public datasets.