杭州余杭区网站建设,江宁网站建设多少钱,百度推广渠道代理,万表网手表官网文章目录AbstractIntroduction2 PRELIMINARIES2.12.2 Categorical Frequency Oracles4 GRID APPROACHES4.1概述Abstract
在本文中#xff0c;我们解决了在局部差异隐私下回答多维范围查询的问题。有三个关键的技术挑战#xff1a;捕捉属性之间的相关性#xff0c;避免维度的…
文章目录AbstractIntroduction2 PRELIMINARIES2.12.2 Categorical Frequency Oracles4 GRID APPROACHES4.1概述Abstract
在本文中我们解决了在局部差异隐私下回答多维范围查询的问题。有三个关键的技术挑战捕捉属性之间的相关性避免维度的诅咒以及处理大范围的属性。现有的方法都不能令人满意地应对这三个挑战。克服这三个挑战我们首先提出了一种称为二维网格TDG的方法。其主要思想是谨慎地使用装箱将所有属性对的二维2-D域划分为二维网格该二维网格可以回答所有2-D范围查询。然而为了减少噪声导致的误差二维网格中的每个属性都需要粗粒度从而丢失了各个属性的细粒度分布信息。为了纠正这一缺陷我们进一步提出了混合维网格HDG它还引入了一维网格来捕获关于每个属性分布的更细粒度信息并结合一维和二维网格的信息来回答范围查询。为了使HDG始终有效我们基于对不同误差源如何受到这些选择影响的分析为正确选择网格粒度提供了指导。在真实数据集和合成数据集上进行的大量实验表明HDG可以比现有方法提供显著的改进。
Introduction
如今用户的数据记录本质上包含许多顺序或数字属性例如收入、年龄、查看某个页面的时间、执行某个操作的次数等。这些属性的域由具有有意义的总顺序的值组成。对用户记录的一种典型的基本分析是多维范围查询它是对感兴趣属性的多个谓词的结合并询问其记录满足所有谓词的部分用户。特别是谓词是对属性值范围的限制。然而用户关于这些序数属性的记录是高度敏感的。如果没有强大的隐私保障对其进行多维度的查询将危及个人隐私。因此开发有效的方法来解决这些隐私问题成为迫切需要。
近年来本地差别隐私LDP已成为个人隐私保护的事实标准。在LDP下在将数据发送到中央服务器之前在客户端添加随机噪声。因此用户不需要依赖中央服务器的可信度。LDP的这一令人满意的特性已经导致了行业的广泛部署例如谷歌[16]、苹果[42]和微软[11]。然而现有的LDP解决方案[93148]大多限于对单个属性的一维1-D范围查询并且不能很好地扩展到处理多维范围查询。
在本文中我们解决了LDP下回答多维范围查询的问题。考虑到大量用户拥有包含多个序数属性的记录不可信聚合器的目标是在满足LDP的同时对用户的记录回答所有可能的多维范围查询。为了解决这个问题我们确定了三个关键的技术挑战1如何捕捉属性之间的相关性2如何避免维度的诅咒以及3如何应对属性的大范围。任何未能解决这三个挑战中任何一个的方法都将具有较差的实用性。正如我们在第3节中所展示的现有的方法或其扩展都不能同时应对所有三个挑战。
克服这三个挑战我们首先提出了一种称为二维网格TDG的方法。其主要思想是谨慎地使用装箱将所有属性对的二维2-D域划分为2-D网格该2-D网格可以回答所有可能的2-D范围查询。然而为了减少噪声导致的误差二维网格中的每个属性都需要粗粒度从而丢失了各个属性的细粒度分布信息。当通过部分包含在查询中的单元格计算二维范围查询的答案时需要假设这些单元格内的均匀分布这可能会导致较大的错误。为了纠正这一缺陷我们进一步提出了一种称为混合维网格HDG的升级方法其核心思想是结合混合维一维和二维信息以获得更好的估计。特别是HDG还引入了一维网格来捕获关于每个属性分布的更细粒度信息并结合一维和二维网格的信息来回答范围查询。在TDG和HDG中用户被分为多个组每个组报告一个网格的信息。在LDP下收集每个网格中单元的频率后聚合器使用技术来消除网格之间的负面性和不一致性并最终使用这些网格来回答范围查询。
然而使HDG始终有效仍然很重要因为一维和二维网格的粒度可以直接影响HDG的性能。因此有必要开发一种确定适当网格粒度的方法以便HDG能够保证理想的效用。特别是在HDG中有两个主要的误差来源LDP的随机性质产生的噪声和装箱引起的误差。当值的分布是固定的时由于均匀性假设由于装箱引起的误差不会改变并且可以被视为偏差而由于噪声引起的误差可以被看作方差。因此选择网格的粒度可以被视为一种偏差-方差权衡的形式。细粒度网格由于噪声而导致更大的误差而粗粒度网格由于偏差而导致更高的误差。每种选择的效果都取决于隐私预算ε、人口和分布属性。通过深入分析这两个误差源我们为在不同参数设置下正确选择网格粒度提供了指导。
通过通过二维网格捕获必要的成对属性相关性这两种方法都克服了前两个挑战。此外由于他们正确地使用了所提供的准则来减少由大域引起的错误所以第三个挑战被仔细地解决了。因此TDG通常比现有方法表现更好。通过引入一维网格来减少由于均匀性假设引起的误差HDG可以比现有方法有显著的改进。
总之本文做出了以下贡献 我们提出了TDG和HDG来回答LDP下的多维范围查询其中包括基于对不同来源的错误的分析来选择网格粒度的指南。 我们进行了大量实验以使用真实和合成数据集评估不同方法的性能。结果表明HDG优于现有方法一个数量级。
第2节提供了初步准备。第3节描述了问题陈述和四种基线方法。第4节详细介绍了网格方法。第5节显示了我们的实验结果。第6节审查相关工作。最后第7节总结了本文。
2 PRELIMINARIES
2.1
2.2 Categorical Frequency Oracles
在LDP中大多数问题可以归结为频率估计。
下面我们介绍了针对这些问题的两种最先进的分类频率OracleCFO协议。
4 GRID APPROACHES
在本节中我们首先在第4.1-4.4节中阐述了在LDP下回答多维范围查询的网格方法。然后我们在第4.5节中给出了他们的隐私和效用分析。最后我们将在第4.6节中描述如何选择适当的粒度。
4.1概述
如第3节所分析没有一种基线方法能够克服所有三个关键挑战。为了解决这个问题我们首先提出了一种称为二维网格TDG的方法。其主要思想是谨慎地使用装箱将所有属性对的2-D域划分为2-D网格该2-D网格可以回答所有2-D范围查询。
然而由于网格中同一单元格内的值是一起报告的因此聚合器无法告诉每个单元格内的分布只能假设均匀分布。当通过部分包含在查询中的单元格计算2-D范围查询的答案时由于一致性假设这可能会导致较大的错误。为了纠正这一缺陷我们进一步提出了一种称为混合维网格HDG的升级方法该方法还引入了更细粒度的一维网格并结合一维和二维网格的信息来回答范围查询。
请注意前两个挑战带来了一个困境捕获完全相关性如HIO将导致维度的诅咒而仅关注个体属性如MSW将完全丢失相关信息。在CALM[57]中通过使用二维边缘重建高维边缘解决了类似的困境这在处理这两个挑战时实现了很好的权衡。受此思想启发TDG和HDG都选择通过二维网格捕获必要的成对属性相关性这克服了前两个挑战。第三个挑战在TDG和HDG中也通过适当地使用与准则的合并来减少由大域引起的误差而被仔细地解决。
具体而言TDG和HDG由三个阶段组成
阶段1。构建网格。在TDG中根据给定的d个属性聚合器首先生成所有可能的mC2d个属性对。然后聚合器将用户随机分成m个组每组对应一对。接下来对于其中1≤jk≤d的每个属性对ajak聚合器通过将2-d域[c]×[c]划分为相等大小的д2×д2个2-d单元来分配相同的粒度д2以构建2-d网格Gjk。特别地每个2-D单元指定由cд2×cд2-D值组成的2-D子域。
最后为了获得每个网格中的小区的噪声频率聚合器指示与网格对应的组中的每个用户使用OLH报告他/她的私有值在哪个小区中。
在HDG中聚合器还分别为d个属性构造d个一维网格。因此HDG会有dC2d个网格而且用户被划分为mdC2d个组每个组对应于这些网格中的一个。除了建造C2dge粒度为g2的2D网格作为TDG在HDG中聚合器分配相同的粒度g1来构建一维网格Gj其中包含每个单个属性aj1≤j≤D的大小相等的g1一维单元。特别地每个一维单元指定由cд11-D值组成的一维子域。最后如在TDG中一样聚合器使用OLH来获得每个网格中小区的噪声频率。
阶段2。消除否定性和不一致性。由于使用OLH来确保隐私小区的噪声频率可能是负的这违反了真实频率为非负的先验知识。此外由于属性与多个网格相关不同网格中的属性上集成的噪声频率可能不同从而导致网格之间的不一致。在这个阶段为了提高效用聚合器对构建的网格进行后处理以消除负面性和不一致性。TDG和HDG的区别在于TDG只需要聚合器处理2-D网格而1-D和2-D网格需要在HDG中一起处理。我们在第4.2节中描述了后处理网格的细节。
阶段3。回答范围查询。在此阶段聚合器可以回答所有多维范围查询。我们首先描述如何回答二维范围查询。为了便于说明我们以对Aq0{a1a2}感兴趣的二维范围查询q0为例。在TDG中为了得到q0的答案fq0聚合器首先找到与Aq0对应的2-D网格G12然后以以下方式检查G1中的所有2-D单元。如果小区完全包括在q0中则聚合器将其噪声频率包括在fq0中如果小区被部分地包括则聚合器通过均匀猜测来估计小区和q0之间的公共2-D值的频率之和即假设小区内2-D值频率均匀分布然后将该和与fq0相加。
在HDG中聚合器使用响应矩阵而不是统一猜测来处理q0中部分包含的那些细胞这可以显著提高结果的准确性。具体而言对于每个属性对ajak聚合器首先使用三个网格{GjGkGk}在回答2-D范围查询之前构建响应矩阵Mjk。特别地矩阵Mjk由c×c个元素组成这些元素与ajak的2-D域[c]×[c]中2-D值的估计频率一一对应。第4.3节给出了响应矩阵生成的详细信息。当在HDG中计算2-D查询q0的答案fq0时聚合器还检查网格G12中对应于Aq0的所有2-D单元。对于完全包括在q0中的小区聚合器将其噪声频率包括在fq0中如在TDG中对于部分包含在查询q0中的单元格聚合器识别该单元格与q0之间的公共2-D值然后将M12中它们的对应元素的和与fq0相加。
对于λ2的λ-D范围查询其答案不能直接从构建的二维网格或响应矩阵中获得。为了回答这个λ-D查询我们建议将其分为λ 2 ? 关联的二维范围查询然后从这些答案中估计其答案λ 2 ? 二维查询。我们将在第4.4节中详细讨论。
