第3章异方差加噪下的差分隐私直方图发布 3.1引言 现有基于区间树的差分隐私直方图发布方法大多采用同方差的加噪方式。Hay［1］建立了差分隐私区间树并进行了同方差加噪与一致性调节。Xu［2］等人提出了StructureFirst，优化直方图划分策略，并在划分区间后的构造区间树中进行了同方差加噪。采用同方差加噪方式的发布方法有效提升了发布数据的可用性和算法效率。而实际上，通过研究可以发现，若采用异方差加噪方式，可进一步提高发布精度。文献［3］提出了通过迭代方式，在区间树中进行层次间隐私预算分配的方法，有效降低了查询误差，但其在相同层次的节点中仍使用了相同的隐私预算，因此仍具有进一步优化的空间。文献［4］提出了DPtree，通过异方差加噪，能够对多维数据进行发布并提高查询精度，但该方法采用了完全k叉树结构，限制了树结构调节的灵活性。 针对以上问题，本章提出一种异方差加噪下面向任意区间树结构的差分隐私直方图发布算法LUEDPTree，以期进一步降低区间计数查询误差，提高发布数据可用性。算法LUEDPTree首先根据区间计数查询的分布计算区间树中节点的覆盖概率，并据此分配各节点的隐私预算，从而实现异方差加噪；接着通过分析指出该异方差加噪策略适用于任意区间树结构下的差分隐私直方图发布，且从理论上进一步证明，对于任意区间树结构下基于异方差加噪的差分隐私直方图发布，仍然可在一致性约束下利用最优线性无偏估计进一步降低区间计数查询的误差;最后通过实验对算法LUEDPTree所发布直方图数据的区间计数查询精度及算法效率与同类算法进行了比较分析。 3.2基础知识与问题提出 在现有差分隐私直方图发布方法的研究中，主要通过重构直方图结构来回答区间计数查询，代表方法是基于差分隐私区间树的发布方法。它利用区间树结构重构原始直方图，可有效提高发布数据的精确度和算法运行效率。 定义3.1（差分隐私区间树［1］）对于给定计数直方图H={C1,C2,…,Cn}，对H建立的差分隐私区间树T满足以下特性: (1) 非叶节点的子节点数大于或等于2。 (2) 每个节点x对应于H中的一个区间范围，表示为［L(x),R(x)］，根节点所代表的区间为［1,n］。 (3) 每个节点x的真实计数值为hx=∑R(x)i=L(x)Ci，通过对每个节点添加噪声［57］(本章采用Laplace噪声［5］)，得到加噪计数值 x=hx+Lap(1/εx)，其中εx为节点x的隐私预算，使该节点满足εx差分隐私。 定义3.2（同/异方差加噪方式［1,4］）给定区间树T，通过噪声机制［1］使每个节点x满足εx差分隐私。若对任意节点x、y，均有εx=εy，则称作同方差加噪方式；若存在节点x、y，使得εx≠εy，则称作异方差加噪方式。 如图3.1所示，当ε=1.0时，在图3.1(a)的同方差加噪方式下，区间树的每个节点的隐私预算 εx均为0.5。而在图3.1(b)的异方差加噪方式下，节点1隐私预算为0.33，节点2、3、4的隐私预算均约为0.67。由于通常情况下区间树中的各个节点被查询区间覆盖的频率并不完全相同，例如在查询区间随机分布的情况下，节点2、3、4具有高于节点1的覆盖概率（计算过程将在后文给出），因此，在图3.1(b)中，能够对多数高频覆盖节点添加更少的噪声，对少数低频覆盖节点添加更多的噪声，从而降低整体区间计数查询误差。 图3.1同/异方差加噪下的隐私预算分配 定义3.3（查询一致性约束［1］）在发布后的差分隐私区间树T中，任意节点x的计数值应与其子节点的计数值总和相等，称为查询一致性约束: x=∑y∈Son(x)y其中,代表最终发布后节点的计数值，Son(x)为节点x的子节点集合。 本章的研究问题及目标是: 对于给定的原始直方图H，建立与其对应的差分隐私区间树T，并通过异方差方式进行加噪；接着说明该加噪方式适用于任意区间树结构，并利用查询一致性约束条件进一步优化区间计数查询精度；最后提出异方差加噪下面向任意区间树结构的差分隐私直方图发布算法LUEDPTree，同时保证算法满足 ε差分隐私。 3.3基于区间查询概率的差分隐私直方图发布〖*4/5〗3.3.1问题提出对于统计直方图，若所有可能的区间计数查询的概率相同，则称区间计数查询符合均匀分布。例如,直方图大小为2，则用户可能提出的区间计数查询有［1,1］、［1,2］、［2,2］ 3种，且每一个查询的概率均为1/3。 根据定义2.2中关于查询覆盖的说明，区间树节点被覆盖的概率可通过穷举覆盖区间树节点x的查询Q计算: Pro(x)=∑Q∈Cover(x)PQ（3.1）其中,Cover(x)表示覆盖节点x的区间查询集合，PQ表示某个查询Q的概率。若假设所有查询的概率相同，则有Pro(x)=|Cover(x)|/|Qall|，其中Qall表示所有可能的区间计数查询。覆盖节点x的查询数目越多，则节点被覆盖的概率越大。 对一个区间计数查询Q，令Node(Q)表示查询Q覆盖节点集合，则有Errs(Q)=∑x∈Node(Q)2Δ2ε2其中,Errs(Q)表示Q查询的方差，Δ表示差分隐私敏感度，即区间树的高度。在任意区间计数查询概率相等的背景下，其查询的方差的期望为E(Errs(Q))=∑Q∈Qall∑x∈Node(q)2Δ2ε2|Qall|通过进一步化简，可得E(Errs(Q))=∑x2Δ2|Cover(x)||Qall|ε2=∑x2Δ2Pro(x)ε2（3.2）例3.1对于大小为5的直方图，可构造出图3.2所示的2区间树。在区间计数查询满足均匀分布，即所有的区间查询等概率被提出的情况下，容易利用式（3.1）计算出每个节点被覆盖的概率，其概率分布如图3.2所示。 图3.2区间计数查询均匀分布下区间树节点被覆盖的概率 从图3.2可以看出，在区间计数查询均匀分布背景下，每个区间树节点最终被覆盖的概率不尽相同。节点5被覆盖的概率高达0.4，而节点0被返回的概率仅仅为0.066 667。这意味着对于一个随机的查询，节点5被覆盖的可能性远远大于节点0被覆盖的可能性，由此可以认为节点5在概率意义上更加重要。 对于大小为n的统计直方图，存在多种区间树结构与之对应。然而常使用均方的策略构建k区间树。其中k是一个事先指定的数字，一般取2。 例3.2考虑大小为3的直方图，图3.3展示了两种可能的区间树结构。 利用式（3.1），可得这两种区间树结构中各节点被覆盖的概率，如图3.4所示。 图3.3直方图大小为3的情况下两种 可能的区间树结构 图3.4直方图大小为3的情况下两种可能 的区间树结构节点被覆盖概率 根据式（3.2），图3.4中对应的两种可能的区间树结构在区间查询均匀分布前提下，其区间查询误差期望值分别为(令ε=1.0)E1(Errs(Q))=2×221.02×(0.167+0.333+0.500+0.333)≈10.664 E2(Errs(Q))=2×321.02×(0.167+0.167+0.333+0.167+0.333)≈21.006可见,在区间计数查询符合均匀分布前提下，图3.3(a)的区间树结构与图3.3(b)的区间树结构相比，其区间计数查询误差期望值更小，即查询的精度更高。由于图3.3(b)的区间树结构对应的敏感度大于图3.3(a)的区间树结构对应的敏感度，因此，即使图3.3(b)中节点被覆盖概率之和略小，图3.3(a)的区间树结构对应的区间计数查询误差期望值也将更小。 由上述例子可以看出，不同的区间树结构对应不同的节点被覆盖概率以及不同的区间查询方差期望。因此，如何根据区间计数查询的分布计算区间树节点的被覆盖概率，进行区间树结构的构建，以进一步减小区间计数查询方差的期望，提高区间计数查询的精度，是本节要解决的主要问题。 3.3.2基于区间计数查询概率的差分隐私直方图发布算法〖*2〗1. 相关定义与性质性质3.1在区间计数查询概率相等背景下，具有n个叶节点的区间树中节点x被覆盖概率为Pro(x)=1|Qall|,x为根节点 PL(x)+PR(x)-PC(x),否则其中（令y为x的父节点）PL(x)=(L(x)-L(y))(n-R(x)+1)/|Qall| PR(x)=L(x)(R(y)-R(x))/|Qall| PC(x)=(L(x)-L(y))(R(y)-R(x))/|Qall|证明: 对于根节点，易知有且仅有一个查询能覆盖它。对于非根节点x，令其父节点为y，则根据2.3.1节中关于k区间树的定义可知L(y)≤L(x)≤R(x)≤R(y)若某个查询Q=［L,R］覆盖x节点，则Q不能覆盖其父节点y，因此Q必须满足((L(y)+1≤L≤L(x))∧(R(x)≤R≤n))∨((1≤L≤L(x))∧(R(x)≤R≤R(y)-1))。其中,满足(L(y)+1≤L≤L(x))∧(R(x)≤R≤n)的可能的Q为(L(x)-L(y))(n-R(x)+1)个，而由于各区间被提出的概率相同，因此满足此条件的区间被提出的概率为PL(x)=(L(x)-L(y))(n-R(x)+1)/|Qall|同理，满足(1≤L≤L(x))∧(R(x)≤R≤R(y)-1)的可能Q为L(x)(R(y)-R(x))个，因此，满足此条件的区间被提出的概率为PR(x)=L(x)(R(y)-R(x))/|Qall|然而，某些区间将同时满足以上两个条件，因此在概率中将被重复计算。其中,被重复计算的区间个数为(L(x)-L(y))(R(y)-R(x))个，因此,被重复计算的概率值为PC(x)=(L(x)-L(y))(R(y)-R(x))/|Qall|，根据容斥原理，最终父节点为y的x节点被覆盖概率为PL(x)+PR(x)-PC(x)。证毕。 例3.3令n=6,k=3，则其3区间树结构如图3.5所示。 图3.5直方图大小为6时的3区间树 显然|Qall|=7 2=21。考虑树中x节点，其父节点为y，则 PL（x）=(3-1)(6-4+1)/21=2/7 PR(x)=3(6-4)/21=2/7 PC(x)=2×2/21=4/21 其中PL(x)为以下区间被提出的概率之和: ［2,4］,［2,5］,［2,6］ ［3,4］,［3,5］,［3,6］同理,PR(x)为以下区间被提出的概率之和: ［1,4］,［1,5］ ［2,4］,［2,5］ ［3,4］,［3,5］PC(x)为以下区间被提出的概率之和: ［2,4］,［2,5］ ［3,4］,［3,5］PC(x)即为PL(x)与PC(x)同时考虑的区间被提出的概率之和。因此，在这棵3区间树中, x节点被覆盖的概率为 PL(x)+PR(x)-PC(x)=8/21≈0.381 定义3.4(区间子树估价函数值)令H(L(x),R(x),ary)为节点x所代表区间［L(x),R(x)］按照ary区间树的划分方式进行划分得到的子树的估价函数值，若令其划分后得到的子树为T，则H(L(x),R(x),ary)=∑y∈TPro(y)例3.4在图3.2所示区间树结构中，选取节点2作为区间子树的根节点，令ary=2，如图3.6所示。 图3.6节点2按照ary=2划分后的区间树结构 根据定义3.1可得 H(3,5,2)=(0.13333+0.4+0.066667+0.266667+0.066667)≈0.933 若令ary=2,即节点2所代表区间按照3区间树的划分规则来划分，则划分后区间树结构将与图3.6中的区间树结构有细微不同，如图3.7所示。 图3.7节点2按照ary=3划分后的区间树结构 此时 H(3,5,3)=(0.13333+0.4+0.33333+0.13333)≈1.0 2. 算法描述 设直方图大小为n，且属性值离散化后的值从1开始。算法首先通过在适当规模内选取叉数(本节中选取2～20的数字)k=argmin2≤ary≤20E(Errs(Q))，使得其区间查询误差期望最小。在此情况下，递归地对区间树非根节点进行调整: 对于左端点不为1的区间树节点进行选择性划分，并按照区间子树估价函数值大小贪心选择最优划分叉数。在本算法中，规定在对区间树节点x进行划分时，若对于y0,y1∈Son(x)有L(y0)1，因此SC算法会对它们进行选择性划分，且划分参数大于或等于k。由于划分参数越大，区间树高度越小，因此yi对应的子树高度Height(yi)+1≤Height(root)。因此树高Height(root)=Height(y0)+1（3.3)将式（3.3）不断展开，易知区间树高度恰好为根节点至叶节点［1,1］的路径中的节点数，即Height(root)=|Path|。证毕。 根据结论3.2可知，该差分隐私区间树对应敏感度为|path|。化简式（3.2）可得E(Errs(Q))=2Δ2ε2∑xPro(x)=2|Path|2ε2∑xPro(x)在SC算法的选择性划分阶段，一次划分将会通过贪心选择将节点x按照划分参数w划分为w区间子树。图3.8给出了w为3的情况下对于x进行区间子树划分的例子。 图3.8ary=3划分区间子树后的区间树结构 由于w=3对应的H(L(x),R(x),w)最小，因此有∑x∈Tw=3Pro(x)≤∑x∈Tw<>3Pro(x)，其中Tw表示区间树节点x按照ary=w进行划分，故Ew=E(Errs(Q))≤Ew<>3(Erre(Q))因此,在每一次选择性划分中，区间计数查询误差的期望值非增。 结论3.3SC算法的时间复杂度为O(Unlog2n)。 证明: 由于划分参数不小于k，因此构建出的区间树高度为O(log2n)。根据区间树划分定义易得每一层的节点区间长度不超过n,即|Seg(yi)|≤n。 设区间树中某层节点如图3.9所示，若对于节点yi进行选择性划分，需要选择O(U)次划分参数，且每次需要通过构建完全w区间子树并遍历子树以计算H(L(yi),R(yi),w)，由于遍历的时间复杂度为O(|Seg(yi)|)，因此对于节点yi,其选择性划分时间复杂度为O(U|Seg(yi)|)。而对于某层的所有叶节点，其选择性划分的时间复杂度之和为OU∑|Seg(yi)|=O(Un)。由于区间树高度为O(log2n)，故选择性划分的总时间复杂度为O(Unlog2n)。而无论对于节点x是否进行选择性划分，最终均需要按照一个划分参数进行子节点的划分，因此划分步骤的时间复杂度为O(U)。由于区间树的节点数目为O(n)，因此划分步骤的总时间复杂度为O(Un)。故SC算法的总时间复杂度为O（Unlog2n+Un）=O(Unlog2n)。证毕。 图3.9区间树中某层节点 3.3.3实验结果与分析 本节将在区间计数查询符合均匀分布的背景下对直方图发布算法中区间查询的精度进行实验研究。其中，在同一数据集上，区间计数查询精度由随机区间查询结果与真实查询值之间的差异表示；在同一数据集上，比较并分析区间计数查询符合均匀分布前提下区间计数查询误差期望值的差异。SC算法的比对对象是传统二叉区间树(regular 2range tree)发布算法以及直接对直方图添加噪声的Dwork算法。对于现实数据集分别运行SC算法、传统二叉区间树发布算法以及Dwork算法，对各个算法运行前后的直方图随机区间查询精度进行衡量以及对比。 1. 实验数据与环境 实验数据分别来自Amazon(亚马逊)网站于2005年3月1日0时至2010年8月31日晚23时期间被访问的采样记录(称为Amazon数据集)以及从AOL 导出用户的点击网址为http: //www.ebay.com的数据(称为AOL数据集)。在本实验中区间查询长度为2i(i≥0)；对于每一个区间查询长度，随机生成500个查询区间；采样100次加噪声后的数据；误差通过区间查询的均方误差平均估值来衡量。 实验环境为: 1.8GHz Intel Core i5；4GB内存；Mac OS X 10.8.3操作系统；算法用C++语言实现。 表3.1是两个数据集的统计信息。其中,时间顺序划分表示将要进行发布的直方图中的属性按照日期（精确到天或分钟）递增顺序划分。表3.1数据集统计信息数据集数据规模划分单位划分后的数据规模Amazon716 064d2010AOL36 389 577min48 1302. 区间计数查询误差期望值 对AOL以及Amazon数据集运行SC算法与传统二叉区间树发布算法，并通过式（3.2）计算得到区间计数查询均匀分布下查询误差的期望值，如图3.10所示。 图3.10AOL/Amazon数据集下随机区间查询误差期望值 从实验结果可以看出，在AOL以及Amazon数据集中随机计数区间查询下，SC算法对应的区间查询误差期望值远小于传统二叉区间树发布算法。SC算法中参数k是通过式（3.2）选择的，因此其误差期望值应小于传统二叉区间树发布，而在SC算法的每一次选择性划分中，区间计数查询误差期望值非增，因此划分完后其误差期望值小于原先k区间树的误差期望值。实验结果符合理论预期。 3. 区间计数查询下的精度 分别对AOL以及Amazon数据集运行SC算法、传统二叉区间树发布算法以及Dwork算法，对于随机区间查询计算其均方差，并对此误差取对数。实验结果分别如图3.11和图3.12所示。 图3.11AOL数据集下随机区间查询误差 图3.12Amazon数据集下随机区间查询误差从实验结果可以看出，在AOL以及Amazon数据集中随机计数区间查询下，SC算法的误差曲线完全在传统二叉区间树发布算法下方。而在区间长度较小的情况下，Dwork算法的查询误差较小；在区间长度较大的情况下，Dwork算法的误差大于传统二叉区间树发布算法以及SC算法的误差。由于Dword算法中的误差为线性累加，因此其误差和查询区间大小呈线性关系；传统二叉区间树发布算法以及SC算法均通过区间树发布数据，因此其区间计数查询误差和区间大小呈类对数关系。本实验中，传统二叉区间树发布算法以及SC算法均运行于相同二叉区间树的树结构下，根据算法分析，SC算法优势明显，符合理论预期。 以上实验结果表明，在Amazon及AOL数据集下，SC算法在随机区间计数查询下误差较小，总体与理论预期相符，具有一定的实用性。 3.4异方差加噪下面向任意树结构的差分隐私直方图发布算法〖*4/5〗3.4.1节点覆盖概率计算当对区间树进行区间计数查询时，其计数值为查询区间［QL,QR］所覆盖的多个节点计数值之和［1］。查询区间所覆盖的节点互不相交，且并集等于查询区间。因此，被覆盖节点x需满足QL≤L(x)≤R(x)≤QR。同时，对任意一次查询，若其父节点fx能被查询区间覆盖，节点x将被忽略。因此，节点x被查询区间覆盖的条件为(QL≤L(x)≤R(x)≤QR)∧瘙綈(QL≤L(fx)≤R(fx)≤QR)（3.4)当x为根节点时，因其父节点fx不存在，令(QL≤L(fx)≤R(fx)≤QR)为假。 本节假定所有查询区间的出现概率相等。由式(3.1)可得出节点被覆盖概率px的计算公式: px=1n(n+1)/2,x为根节点 L(x)(n－R(x)+1)－L(fx)(n－R(fx)+1)n(n+1)/2,否则（3.5)根据式(3.5)，可由算法3.2计算节点被覆盖概率。算法3.2CNCP(Calculate Node Coverage Probability) 输入: 待计算节点x及其父节点fx 输出: 区间树中所有节点的被覆盖概率px 1. 若x为根节点: px←1n(n+1)/2 2. 若x为其他节点: px←L(x)(n－R(x)+1)－L(fx)(n－R(fx)+1)n(n+1)/2 3. 对所有y∈Son(x)，执行CNCP(y,x)实际上，当查询区间满足其他分布特性时，通过对式（3.5)的调整，其节点被覆盖概率也可通过本算法计算。由于算法3.2仅要求树结构满足区间树定义，因此适用于任意树结构的差分隐私区间树。 3.4.2节点系数计算及隐私预算分配 在计算出节点被覆盖概率后，即可据此调整隐私预算，通过异方差加噪方式降低整体的查询误差。而在此之前，需分析如何保证异方差加噪后的差分隐私区间树满足ε差分隐私。 结论3.4给定区间树T，Leaf(x)表示以x为根节点的子树的叶节点集合，Path(x,y)表示节点x到其子节点y路径上的节点集合。若通过添加Laplace噪声使每个节点x满足εx差分隐私，则整体发布过程满足maxx∈Leaf(root)∑y∈Path(root,x)εy差分隐私。 证明: 对任意节点x，设Sub(x)表示以节点x为根节点的子树，A(x)表示对子树Sub(x)进行发布的算法，则: (1) 对节点x的任意两个节点yi,yj∈Son(x)，由于Sub(yi)∩Sub(yj)=，根据差分隐私并行组合性［8］，算法A(y)y∈Son(x)组合后满足maxy∈Son(x)A(y)差分隐私。 (2) 对于节点y∈Son(x)，由于节点x的隐私预算为εx，且Sub(y)∩Sub(x)=Sub(y)，由差分隐私序列组合性［8］可得，A(x)满足(εx+maxy∈Son(x)A(y))差分隐私。 由(1)、(2)可得，A(root)满足maxx∈Leaf(root)∑y∈Path(root,x)εy差分隐私，证明完毕。 根据结论3.4，若要保证异方差加噪后的区间树满足ε差分隐私，需满足以下条件: maxx∈Leaf(root)∑y∈Path(root,x)εy=ε定义H(z)=∑y∈Path(root,z)εy，z为任意叶节点，为最小化区间计数查询误差期望，将以上条件转换为H(z)z∈Leaf(root)=∑y∈Path(root,z)εy=ε同时，令Node(Q)表示区间计数查询Q所覆盖的节点集合，由于Lap(1/εx)噪声引起的标准方差［9］为2/ε2x，因此，查询Q的误差方差为Err(Q)=∑x∈Node(Q)2ε2x则区间计数查询误差期望为E(Err(Q))=∑Q∈Qall∑x∈Node(Q)2ε2x|Qall|=px|Qall|∑x2ε2x|Qall|=2∑xpxε2x因此，在满足ε差分隐私的前提下，求解区间树上各节点的差分隐私预算，从而最小化区间计数查询误差期望的问题可转化为以下最优化问题: minf(ε)=12E(Err(Q))=∑xpxε2x s.t.H(z)z∈Leaf(root)=ε(3.6)其中，ε表示区间树中节点的差分隐私预算向量。 下面通过定义3.5与结论3.5进行求解。 定义3.5（路径隐私预算和） psum(x)=εx,x∈Leaf(root) psum(SonBound(x))+εx,否则 其中，SonBound(x)={y|y∈Son(x)∧L(y)=L(x)},由式(3.6)中的约束条件可得psum(root)=ε。 结论3.5为最小化区间计数查询误差期望（即求解式(3.6)），区间树中差分隐私预算分配方案需满足εx=axbxpsum(x)其中ax、bx称为节点x的节点系数，有ax=1,x∈Leaf(root) px∑y∈Son(x)pyb3ya3y13,否则 bx=1,x∈Leaf(root) ax+1,否则证明: (1) 若x为叶节点，则结论3.5显然成立。 (2) 若x为非叶节点，利用拉格朗日乘数法，可构造如下函数: F(ε,λ)=∑xpxε2x+∑λzz∈Leaf(root)(H(z)－ε)其中，λ为引入的未知标量。因目标函数f(ε)为凸函数，同时，求解式（3.5)与求解函数F(ε,λ)的全局最优解等价，因此，将F(ε,λ)对ε求导，得F(ε,λ)εx=－2pxε3x+∑z∈Leaf(x)λz=0（3.7)假设对于y∈Son(x)，结论均成立，则εy=aybypsum(y)（3.8)对于节点SonBound(x)和任意y∈Son(x)，由于式(3.6)的约束条件下，任意叶节点到根节点路径上的隐私预算和等于ε，因此: εpsum(y)=∑u∈Path(root,x)εu=εpsum(SonBound(x))（3.9)由式（3.8)和式（3.9)，得εy=aybypsum(SonBound(x))（3.10)为满足式（3.7)，必有2pyε3y=∑z∈Leaf(y)λz 2pxε3x=∑z∈Leaf(x)λz=∑y∈Leaf(x)∑z∈Leaf(y)λz=∑y∈Leaf(x)2pyε3y（3.11)将式（3.10)代入式（3.11)可得pxε3x=∑y∈Leaf(x)pyb3ya3ypsum(SonBound(x)3因此psum(SonBound(x))=εxpx∑y∈Leaf(x)pyb3ya3y13令ax=px∑y∈Leaf(x)pyb3ya3y13则psum(x)=psum(SonBound(x))+εx=1+axax εx=bxax εx综合(1)、(2)，结论得证。 至此，可通过算法3.3计算节点系数ax、bx。算法3.3CNP (Calculate Node Parameter) 输入: 待计算节点x 输出: 区间树中所有节点的节点系数ax、bx 1. 若x为叶节点: ax←1,bx←1 2. 若x为其他节点: ax←px∑y∈Son(x)pyb3ya3y13 bx←ax+13. 对于y∈Son(x),运行CNP(y)计算出节点系数ax、bx后，可通过算法3.4分配每个节点的差分隐私预算εx并进行异方差加噪。图3.13异方差加噪示例算法3.4NPBD(NonUniform Private Budget Distribute) 输入: 待加噪节点x、路径隐私预算和psum(x) 输出: 区间树所有节点的加噪计数值x 1. εx←axbxpsum(x)//分配隐私预算 2. x←hx+Lap(1/εx) //添加噪声 3. 对所有y∈Son(x)，执行NPBD(y,psum(x)-εx)下面以图3.1所示差分隐私区间树为例，分析异方差加噪对区间计数查询精度的影响。 将图3.1所示区间树通过算法3.2及算法3.3进行节点被覆盖概率和系数计算，结果如图3.13所示。再通过算法3.4进行隐私预算分配，得到各节点的隐私预算: ε1≈0.33,ε2≈0.67,ε3≈0.67,ε4≈0.67 该方案与图3.1(b)所示一致。分别对图3.1(a)、图3.1(b)中的隐私预算分配方案计算区间计数查询误差期望: Ea=21/60.52+1/30.52+1/20.52+1/30.52≈10.67 Eb=21/60.332+1/30.672+1/20.672+1/30.672≈8.25