  Mobile apps that use location data are pervasive, spanning domains such as
transportation, urban planning and healthcare. Important use cases for location
data rely on statistical queries, e.g., identifying hotspots where users work
and travel. Such queries can be answered efficiently by building histograms.
However, precise histograms can expose sensitive details about individual
users. Differential privacy (DP) is a mature and widely-adopted protection
model, but most approaches for DP-compliant histograms work in a
data-independent fashion, leading to poor accuracy. The few proposed
data-dependent techniques attempt to adjust histogram partitions based on
dataset characteristics, but they do not perform well due to the addition of
noise required to achieve DP. We identify density homogeneity as a main factor
driving the accuracy of DP-compliant histograms, and we build a data structure
that splits the space such that data density is homogeneous within each
resulting partition. We show through extensive experiments on large-scale
real-world data that the proposed approach achieves superior accuracy compared
to existing approaches.
