  In this paper, we tackle the problem of constructing a differentially private
synopsis for two-dimensional datasets such as geospatial datasets. The current
state-of-the-art methods work by performing recursive binary partitioning of
the data domains, and constructing a hierarchy of partitions. We show that the
key challenge in partition-based synopsis methods lies in choosing the right
partition granularity to balance the noise error and the non-uniformity error.
We study the uniform-grid approach, which applies an equi-width grid of a
certain size over the data domain and then issues independent count queries on
the grid cells. This method has received no attention in the literature,
probably due to the fact that no good method for choosing a grid size was
known. Based on an analysis of the two kinds of errors, we propose a method for
choosing the grid size. Experimental results validate our method, and show that
this approach performs as well as, and often times better than, the
state-of-the-art methods. We further introduce a novel adaptive-grid method.
The adaptive grid method lays a coarse-grained grid over the dataset, and then
further partitions each cell according to its noisy count. Both levels of
partitions are then used in answering queries over the dataset. This method
exploits the need to have finer granularity partitioning over dense regions
and, at the same time, coarse partitioning over sparse regions. Through
extensive experiments on real-world datasets, we show that this approach
consistently and significantly outperforms the uniform-grid method and other
state-of-the-art methods.
