  We consider the problem of publishing location datasets, in particular 2D
spatial pointsets, in a differentially private manner. Many existing mechanisms
focus on frequency counts of the points in some a priori partition of the
domain that is difficult to determine. We propose an approach that adds noise
directly to the point, or to a group of neighboring points. Our approach is
based on the observation that, the sensitivity of sorting, as a function on
sets of real numbers, can be bounded. Together with isotonic regression, the
dataset can be accurately reconstructed. To extend the mechanism to higher
dimension, we employ locality preserving function to map the dataset to a
bounded interval. Although there are fundamental limits on the performance of
locality preserving functions, fortunately, our problem only requires distance
preservation in the "easier" direction, and the well-known Hilbert
space-filling curve suffices to provide high accuracy. The publishing process
is simple from the publisher's point of view: the publisher just needs to map
the data, sort them, group them, add Laplace noise and publish the dataset. The
only parameter to determine is the group size which can be chosen based on
predicted generalization errors. Empirical study shows that the published
dataset can also exploited to answer other queries, for example, range query
and median query, accurately.
