Differential privacy has recently emerged as the de facto standard for
private data release. This makes it possible to provide strong theoretical
guarantees on the privacy and utility of released data. While it is well-known
how to release data based on counts and simple functions under this guarantee,
it remains to provide general purpose techniques to release different kinds of
data. In this paper, we focus on spatial data such as locations and more
generally any data that can be indexed by a tree structure. Directly applying
existing differential privacy methods to this type of data simply generates
noise. Instead, we introduce a new class of "private spatial decompositions":
these adapt standard spatial indexing methods such as quadtrees and kd-trees to
provide a private description of the data distribution. Equipping such
structures with differential privacy requires several steps to ensure that they
provide meaningful privacy guarantees. Various primitives, such as choosing
splitting points and describing the distribution of points within a region,
must be done privately, and the guarantees of the different building blocks
composed to provide an overall guarantee. Consequently, we expose the design
space for private spatial decompositions, and analyze some key examples. Our
experimental study demonstrates that it is possible to build such
decompositions efficiently, and use them to answer a variety of queries
privately with high accuracy.

本文介绍了一种新的私有空间分解方法，将标准的空间分布方法与差分隐私相适应，提供了隐私保证，并分析了一些关键实例，实验研究证明可以高效地构建这种空间分解并用于各种查询。