Differentially Private Grids for Geospatial Data

abstract

在本文中，我们解决了为二维数据集(如地理空间数据集)构建差异私有概要的问题。目前最先进的方法通过执行数据域的递归二进制分区和构造分区的层次结构来工作。我们表明，基于分区的概要方法的关键挑战在于选择正确的分区粒度来平衡噪声误差和非均匀性误差。我们研究了均匀网格方法，即在数据域上应用一定大小的等宽网格，然后在网格单元上发出独立的计数查询。这种方法在文献中没有得到重视，可能是由于没有已知的选择网格大小的好方法。在对这两种误差进行分析的基础上，提出了网格尺寸的选择方法。实验结果验证了我们的方法，并表明这种方法的性能与最先进的方法一样好，而且往往比最先进的方法更好。

我们进一步介绍了一种新的自适应网格方法。自适应网格方法在数据集上铺设粗粒度网格，然后根据其噪声计数进一步划分每个单元格。然后，这两层分区都用于回答对数据集的查询。该方法利用了在密集区域上进行细粒度分区的需求，同时在稀疏区域上进行粗粒度分区。通过在真实世界数据集上的大量实验，我们表明这种方法始终且显著优于均匀网格方法和其他最先进的方法。

intro

我们每天都在与位置感知设备打交道。这些设备包括有gps功能的手机和平板电脑，以及导航系统。每个设备都可以向中央服务器报告大量的位置数据。这些位置信息通常被称为地理空间数据，如果处理和分析得当，可以带来巨大的好处。对于许多企业来说，基于位置的信息视图可以增强业务智能并实现更明智的决策。对于许多研究人员来说，地理空间数据可以增加一个有趣的维度。例如，来自手机的位置信息可以帮助各种对人口如何定居和聚集感兴趣的社会研究。此外，车载导航系统的定位可以帮助提供常见交通拥堵区域的信息。

如果共享，这些地理空间数据可以对研究和其他用途产生重大影响。然而，共享这些信息可能会带来重大的隐私问题。**本文研究了以私密方式发布静态地理空间数据的问题。**特别地，我们介绍了在满足差异隐私的同时发布二维数据集概要的方法。

差别隐私[1]最近已经成为隐私保护数据发布的事实上的标准，因为它能够提供强大的最坏情况下的隐私保证。我们在下面的框架中考虑二维的、不同私有的概要方法。给定一个数据集和数据集中元组所在的二维域，我们将每个元组视为二维空间中的一个点。将域划分为单元，然后以满足差异隐私的方式获取每个单元的噪声计数。差异私有概要由这些细胞的边界和它们的噪声计数组成。然后可以使用该概要生成合成数据集，或直接回答查询。

一般来说，在回答查询时，这种不同私有的概要方法有两个错误来源。第一个来源是为满足差异隐私而添加的噪声。此噪声具有预定义的方差，并且与数据集无关，但取决于用于回答查询的单元格数量。第二个来源是数据集本身的性质。当我们发出一个只与某个单元部分相交的查询时，我们必须估计相交单元中有多少数据点，假设数据点均匀分布。这种错误的大小既取决于数据集中点的分布，也取决于分区。我们的方法源于对这两种错误来源如何依赖于网格大小的仔细检查。

最近的几篇论文试图为二维数据集[2]，[3]开发这种差异私有的概要方法。这些论文采用空间索引方法，如四叉树和kd树，以提供数据分布的私有描述。这些方法都可以看作是将适用于一维数据集的二元层次结构方法应用于二维数据集。重点是如何执行分区，结果是一个深树。

//

本文的贡献有以下几点。1）我们发现地理空间数据集的差异化私有化提要的关键挑战是如何选择分区粒度来平衡两个来源造成的误差，并在分析误差如何取决于网格大小的基础上，提出了均匀网格法的网格大小选择方法。

2）我们提出了一种新颖、简单、有效的自适应网格方法，以及选择关键参数的方法。

3）我们使用4个不同大小的数据集进行了广泛的评估，其中包括之前没有被用于差异化私有数据发布文献的地理空间数据集。实验结果验证了我们的方法，并表明它们优于现有方法。

4）我们分析了为什么分层方法在二维情况下表现不佳，并预测它们在更高维度上的表现会更差。