  Publishing histograms with $\epsilon$-differential privacy has been studied
extensively in the literature. Existing schemes aim at maximizing the utility
of 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, namely efficiency. 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 practitioners engineer a differentially private histogram scheme
depending on their application requirements.
