Engineering Methods for Differentially Private Histograms: Efficiency Beyond Utility
Georgios Kellaris, Stavros Papadopoulos, Dimitris Papadias · IEEE Transactions on Knowledge and Data Engineering · 2018
Publishing histograms with$\epsilon$-differential privacyhas been studied extensively in the literature. Existing schemes aim at maximizing theutilityof the published data, while previous experimental evaluations analyze the privacy/utility trade-off. In this paper, we provide the first experimental evaluation of differentially private methods that goes beyond utility, emphasizing also on another important aspect, namelyefficiency. Towards this end, we first observe that all existing schemes are comprised of a small set of common blocks. We then optimize and choose the best implementation for each block, determine the combinations of blocks that capture the entire literature, and propose novel block combinations. We qualitatively assess the quality of the schemes based on the skyline of efficiency and utility, i.e., based on whether a method is dominated on both aspects or not. Using exhaustive experiments on four real datasets with different characteristics, we conclude that there are always trade-offs in terms of utility and efficiency. We demonstrate that the schemes derived from our novel block combinations provide the best trade-offs for time critical applications. Our work can serve as a guide to help practitionersengineera differentially private histogram scheme depending on their application requirements.