差分隐私下多重一致性约束问题的逼近方法

蔡剑平，刘西蒙，熊金波，应作斌，吴英杰

（1.福州大学数学与计算机科学学院，福建 福州 350108；2.福建师范大学数学与信息学院，福建 福州 350117；3.新加坡南洋理工大学电气与电子工程学院，新加坡 639798）

1 引言

随着互联网和大数据技术的快速发展，人们普遍意识到数据发布、信息共享的重要性。为了达到信息公开、成果展示或者提升商业价值、履行社会责任等目的，包括医疗、餐饮、教育、金融等在内的多个行业都在尝试利用互联网和大数据技术向社会公开发布统计信息。然而，数据挖掘技术的飞速发展也使人们从公开发布的信息中挖掘潜在信息的能力不断增强。除了有价值的合法信息外，可被挖掘的信息中还潜藏着大量的个人敏感信息。利用公开发布的信息，攻击者可结合相关背景知识，利用关联分析等技术手段推断或窃取个人隐私，给人们的隐私安全带来了巨大威胁。为保护个人隐私，Dwork[1]提出了差分隐私保护技术。该技术通过对数据添加扰动的方式实现隐私保护，从理论上保证了具备任何知识的攻击者都无法从被保护的公开数据中挖掘个人隐私，是目前公认有效的隐私保护技术。

在某些数据发布问题中，数据间满足了某种语义上的一致性约束。由于差分隐私通过向数据添加噪声实现隐私保护，噪声的随机性会彻底破坏数据间一致性约束。为了获得满足一致性约束的发布效果，不少文献针对各类模型提出了有效的一致性发布算法[2-8]。然而，多数算法所适用的场景针对性较强，难以有效地应用于更广泛的差分隐私最优一致性发布问题。

随着差分隐私技术的日益普及，数据发布场景越来越复杂，同时数据间一致性约束问题的解决难度也越来越高。不少问题已超出了现有技术的关注范围，虽然采用基于极大似然估计的通用解法能够实现最优一致性发布，但通用解法效率极低，无法满足较大规模的数据发布需求。以餐饮行业的直方图统计发布为例，假设某餐馆记录了开业以来所有顾客的消费情况。记录内容如表1 所示，包含了顾客标识、食物种类、消费数量以及消费时间。假设餐馆提供的食物单品为可乐、汉堡、鸡翅、薯条、鸡块5种，则顾客所能购买的食物单品种类数c=5 。为了向公众展示销售情况，餐馆决定按天统计销量并采用直方图发布技术公开发布各单品销量，发布内容如表2 所示。同时，为保护顾客隐私，餐馆决定采用差分隐私技术并希望获得最优的一致性发布效果。本文称发布过程中涉及的问题为餐馆销量直方图发布问题。考虑餐馆长期以来只以套餐的形式销售食物，并不以单品形式销售，导致某些单品的销量组合无法满足该场景的语义特征。例如，餐馆销售以下3种套餐：1) 2 份可乐+汉堡+鸡翅+鸡块，2) 2 份汉堡+2 份鸡翅+薯条，3) 可乐+汉堡+薯条+鸡块。

表1 消费记录

表2 销量统计

在上述套餐组合下某些销量数据不可能出现。例如，不会出现5 种单品的销量均为3 份的情况。因此，除了直方图一致性约束问题，餐馆销量直方图发布问题还面临由套餐组合导致的一致性约束问题。本文称该问题为套餐一致性约束问题。餐馆销量直方图发布问题是由两者共同组成的全局一致性约束问题，超出了直方图发布问题的研究范畴，更加复杂。而一致性约束子问题的求解容易得多。直方图一致性约束问题的研究[3-5]已相当成熟，现有技术已具备实现大规模直方图最优一致性发布的能力；并且，由于餐馆提供的食物单品仅有5 种，每个套餐一致性约束子问题仅为数据规模为5 的小问题，采用通用解法[6]即可高效求解。数据规模小或存在高效算法等原因常常使子问题的求解难度比全局问题容易得多，但子问题之间并非简单的叠加关系，分别解决子问题的结果往往不能解决全局问题。研究表明，单独对某个子问题执行最优一致性发布算法会破坏另一个子问题发布的一致性。

为充分发挥一致性约束子问题高效求解的优势，提升全局最优一致性问题的求解效率，本文基于最优一致性发布问题的理论分析提出了差分隐私多重一致性约束最优发布问题。该问题主张将复杂的差分隐私的最优一致性约束问题拆分成多个可高效求解的子问题，然后通过独立求解子问题的最优一致性发布高效地实现原问题的最优一致性发布。经研究，本文提出了差分隐私下多重一致性约束问题的逼近方法，简称多重一致性约束逼近方法。该方法通过反复迭代求解一致性约束子问题使发布结果逼近原问题的最优一致性发布。严格理论论证表明，无论子问题被如何划分，该方法总能保证多重一致性约束问题实现最优一致性发布。此外，不少同类子问题所涉及的发布数据互不相交，数据的发布过程具有独立性，利用这种独立性设计的并行算法可进一步提升多重一致性约束逼近方法的求解效率。

本文主要的研究工作如下。

1) 求得差分隐私下最优一致性发布的解析表达式，并深入分析了解析表达式的数学性质。

2) 基于解析表达式的分析提出差分隐私多重一致性约束问题的逼近方法，并对该方法的收敛性进行充分论证。

3) 讨论多重一致性约束逼近方法的可并行性。以餐馆销量直方图发布问题为例设计了最优一致性发布算法并进行实验分析。

2 相关工作

自Dwork[1]提出差分隐私以来，不少国内外学者对数据发布的一致性约束问题做了深入研究，提出了许多有效的最优一致性发布算法。其中，以树为基础的发布模型是差分隐私一致性约束问题的典型代表。为解决直方图发布过程中的数据不一致问题，Boosting 算法[2]通过对完全k叉树的后置处理实现了最优一致性发布。基于Boosting 算法，Cormode 等[8]针对空间数据的划分发布问题建立了四分树发布模型，并提出了满足一致性约束的Quad-Post 算法。考虑Boosting 算法只能针对完全k叉树的不足，吴英杰等[3]提出了LBLUE（local best linear unbiased estimation）算法实现了面向任意区间树的最优一致性发布，贾俊杰等[5]则通过将查询区间映射为完全k叉树的方法改进最优一致性发布。与其他算法不同，LBLUE 算法将区间树中每对父子节点间的等式关系作为一个一致性约束子问题，然后采用迭代逼近的思想求解最优一致性发布。实际上，LBLUE 算法所解决的问题是多重一致性约束最优发布问题的一个特例，其有效性可以通过本文提出的理论得以充分解释。因此，该算法可以视为多重一致性约束逼近方法的一个具体应用。相比于Boosting 算法，LBLUE 算法不再局限于完全树模型，表明多重一致性约束逼近方法具备了处理更复杂模型的能力。

通过构造虚拟节点，张双越等[7]发现了差分隐私轨迹流量发布过程中潜在的一致性约束问题，通过实现最优一致性发布有效地提升了数据发布的精确性。该结果表明，除了以树为基础的发布模型，差分隐私一致性约束问题还具有其他更多的表现形式。多种不同的差分隐私一致性约束子问题可能存在于一个复杂的发布场景中。然而，目前关于差分隐私一致性约束问题的研究主要针对某个特定的应用场景。虽然大多数一致发布算法都是高效的，但仍无法解决复杂发布场景所涉及的一致性约束问题。采用极大似然估计的思想，Lee 等[6]将差分隐私一致性约束问题表述为抽象的优化方程，并实现了适用于任意最优一致性约束问题的通用解法。然而，通用解法实现最优一致性发布的效率普遍较低，只能有效解决局部的或规模较小的一致性约束问题。如何合理利用高效但针对性强的一致性发布算法以及低效但通用的一致性发布算法解决更复杂的差分隐私最优一致性约束问题具有较高的研究价值。此外，目前多数差分隐私一致性约束问题的研究工作集中在发布精度或效率的提升上。关于最优一致性发布性质的研究还十分有限，现有理论难以解释多重一致性约束之间的内在联系。因此，差分隐私多重一致性约束问题仍存在较大的研究空间。

3 预备知识

3.1 差分隐私

为避免隐私泄露，差分隐私技术通过向待发布数据添加噪声的方式实现隐私保护。通过添加噪声，差分隐私有效地隐藏了隐私信息的存在性，确保攻击者即使掌握了所有背景知识也无法有效推断个人隐私。差分隐私的形式化定义如下。

定义1差分隐私[9]。若一个随机算法M 满足(ε,δ)−差分隐私，则对于2 个兄弟数据集D和D'满足所有M的输出O⊆Range(M) 都有以下不等式成立。

假设待发布数据由n个数据组成，分别记为x1,x2,…,xn，则数值型的发布函数为A:D→Rn。不妨将这些数据依次写为列向量x=[x1,x2,…,xn]T的形式，满足x=A(D)。随机算法M 通常采用特定的噪声机制向 A(D)添加噪声以实现差分隐私。常见的噪声机制主要包括拉普拉斯机制和高斯机制，其定义分别如下。

定义2拉普拉斯机制[10]。对于发布函数 A:D→Rn，拉普拉斯机制通过式(2)实现(ε,0)−差分隐私。

其中，ξ为随机向量且各元素均符合拉普拉斯分布，即，1Δ为A 的1L−敏感度[10]。

定义3高斯机制[9]。对于发布函数A:D→nRn，高斯机制通过式(3)实现(ε δ),−差分隐私。

根据上述定义可知，无论采用拉普拉斯机制还是高斯机制，M(D)中添加的噪声都具有独立同分布的性质。由于噪声随机性，M(D)无法仅靠噪声机制保证满足任何一致性约束。

3.2 数据发布的一致性约束问题

在数据发布过程中，一致性约束问题是由m个一致性约束条件组成的发布问题，其发布结果要求这m个一致性约束条件同时满足。其中，一致性约束条件的定义如下。

定义4一致性约束条件。对于由n个数据组成的待发布数据x1,x2,…,xn，一致性约束条件表示为一个关于xi的线性等式关系，如式(4)所示。

其中，mj和b是限定一致性约束条件的系数。根据上述定义，对于满足m个一致性约束条件差分隐私发布问题，在引入噪声机制之前，x满足了如式(5)所示的一致性约束方程。

由式(5)可知，一致性约束问题取决于矩阵M∈Rm×n和向量b∈Rm×1。由于添加噪声前的发布结果满足式(5)，因此式(5)为一致性方程，至少存在一个解。本文称满足式(5)的所有解均为一致性发布。记 M(D)的输出为向量～x=x+ξ，由上述分析可知，无法保证满足式(5)。为求得差分隐私下的最优一致性发布，文献[2,6,11-13]基于优化方程式(6)设计后置处理算法求得最优一致性发布。通常情况下，的总体误差小于，后置处理总是能有效地提升数据发布的精确性。

根据一致性发布的存在性，定理1 论证关于优化式(6)的最优一致性发布存在且唯一，同时最优一致性发布具有明确的解析表达式。

该优化方程是关于x' 的一致方程的最小范数解。由文献[14]可知

证毕。

作为最优一致性发布的解析表达式，式(7)可作为通用解法有效解决任意差分隐私下最优一致性约束问题。然而，式(7)所涉及的M†是关于矩阵M的Moore-Penrose 逆[14]运算。作为传统矩阵逆运算的拓展，Moore-Penrose 逆求解过程十分复杂，运算量极大。其求解难度不低于时间复杂度为O(n3)的传统求逆运算，无法高效地解决最优一致性约束发布问题。这导致通用解法难以有效解决数据规模较大的一致性约束问题。虽然通用解法的实用性有限，但作为小型最优一致性约束发布问题的解决方案仍然是合适的。

相较而言，针对具体发布问题设计的最优一致性发布算法的求解效率则高得多。Hay 等[2]设计的Boosting 只需对完全k叉树分别执行一次自底向上和自顶向下的后置处理，即可实现最优一致性发布，时间复杂度仅为O(n)；张双越等[7]设计的算法巧妙地利用轨迹流量发布问题的稀疏性实现多达数十万个节点的交通路网的最优一致性发布。然而，上述两项技术并不具备通用性，难以适用于其他发布场景，甚至无法直接应用于拓展模型。因此，适用范围相对有限。

4 多重一致性约束问题的逼近方法

根据差分隐私多重一致性约束最优发布问题的思想，复杂的差分隐私的最优一致性约束问题可划分为多个最优一致性发布子问题。相比于原问题，合理划分后的子问题往往更简单且容易解决，或者可利用现有技术得以高效求解。由于文献[2-7]已对诸多子问题提供了解决方案，因此本文将重点研究如何利用各部分子问题的最优一致性发布结果实现原问题的最优一致性发布。构建差分隐私多重一致性约束最优发布问题首先进行子问题划分。由于M和b的每行代表了一个一致性约束条件，因此划分子问题的过程即将一致性约束条件重新排列、分组的过程。形式上相当于对M和b按行进行矩阵分块的过程，且表述同一个一致性约束子问题的所有一致性约束条件将被划分到同一个子矩阵。设原问题划分为k重一致性约束发布问题，则分块过程为

其中，∗为函数的复合运算符，即fj∗f i(x)=f j(f i(x))；t表示函数的复合运算次数，即f2(x)=f(f(x))。根据极限表达式(8)，差分隐私下多重一致性约束问题的逼近方法的核心思想是通过依次反复求解一致性约束子问题，最终求解结果趋近于fM,b()，即原问题的最优一致性发布。这样只需求得子问题的最优一致性发布，即可解决原问题的最优一致性发布。

5 最优一致性发布的性质分析

确保差分隐私下多重一致性约束问题的逼近方法可行的关键在于论证式(8)能否准确地收敛于原问题的最优一致性发布。由于该问题十分复杂，论证过程需要大量理论基础，本节首先从最优一致性发布的性质入手开展研究工作，然后循序渐进地寻找该问题的答案。

作为式(7)的关键组成部分，Moore-Penrose 逆M†具有一些重要的数学性质。相关资料[15-17]表明，M†具有如下性质。

性质1[15]对于任意矩阵M∈Rm×n，都有M†=MT(MMT)†成立。

性质2[16]对于任意矩阵M∈Rm×n，都有MM†M=M成立。

性质3对于任意矩阵M∈Rm×n，都有M†M为幂等矩阵成立，且有谱范数[17]满足。

利用这些性质，本文通过进一步分析得出如下关于最优一致性发布的定理成立。

定理 2对于任意向量x∈Rn×1，设y=fM,b(x)，则有My=b。并且fM,b(x)的运算满足幂等律，即fM,b(x)=fM,b∗fM,b(x)。

证明由于y=fM,b(x)已为满足优化方程式(6)的最优一致性发布。将y代入式(6)中的，显然也是方程的一个可行解。此时，目标函数，根据fM,b(x)的定义可知y=fM,b(y)。

设y'=fM,b∗fM,b(x)=fM,b(y)=M†(b−My)+y，由于My=b⇒b−My=0，代入可得y'=y，因此幂等律得证。

根据定理2，本文有如下推论。

推论1设p∈Rn×1是任意满足Mp=b的一致性发布，至少能够找到一个向量x∈Rn×1使p=fM,b(x)成立。

证明根据定理2 可知，任意满足Mp=b的一致性发布p都有p=fM,b(p)。只需令x=p，即找到一个向量x使p=fM,b(x)成立。证毕。

虽然推论1 只论证了p本身能满足推论条件，但实际上满足p=fM,b(x)的向量往往无穷多，不过本文的分析过程只需关注其存在性，对具体有哪些x满足p=fM,b(x)将不再赘述。

接下来，定理3 将揭示最优一致性发布与其他一致性发布之间的关系。

定理3对于任意向量x及其最优一致性发布y=fM,b(x)，设p是满足Mp=b的一致性发布且，则p是关于x的最优一致性发布。

证明采用反证法证明，若p不是关于x的最优一致性发布，即p≠y，则。

由于p是满足Mp=b的一致性发布，根据推论1，可令向量q使p=fM,b(q)，有

x−p展开的结果为

y−p展开的结果为

综上可得

利用性质2 可得

利用性质1 可得

因此，有

与题设不符，假设不成立。因此，p=y，p是关于x最优一致性发布。证毕。

通常情况下，一致性发布的数量有无穷多个而最优一致性发布只有一个。定理3 给出了判断某个一致性发布是否为最优一致性发布的方法，对于检验算法是否实现了最优一致性发布具有重要意义。

此外，研究还发现最优一致性发布满足2 种不变性特征，分别是范数不变性以及内积不变性，具体内容如下。

定理4范数不变性。设p是满足Mp=b的一致性发布，则对于向量x及其最优一致性发布y=fM,b(x)，有

证明对展开，有

定理5内积不变性。设p1和p2是满足方程Mp=b的2 个一致性发布，对于向量x及其最优一致性发布y=fM,b(x)，则关于它们的内积满足

证明由于p1和p2是满足方程Mp=b的一致性发布，根据推论1，可找到向量q1和q2满足p1=fM,b(q1)和p2=fM,b(q2)。则

再次利用式(9)可知

同理，代入可得式(12)成立。证毕。

定理4 和定理5 分别体现了多重一致性约束问题的逼近方法迭代过程中内在的2 种不变性特征，对于其收敛性的分析过程具有重大意义。

6 收敛性分析

根据上述分析结果，本节将进一步分析差分隐私下多重一致性约束问题的逼近方法的收敛性，并以此论证逼近方法经过多次迭代后将实现原问题的最优一致性发布。为了确保分析收敛性的过程便于理解，本节将依次从差分隐私下多重一致性约束问题的逼近方法能否收敛、收敛结果是否满足一致性约束以及一致性发布结果是否满足最优发布这3个问题逐步深入地进行收敛性分析。

首先是关于多重一致性约束问题的逼近方法能否收敛的分析。根据式(8)所示的计算过程，记第s次执行复合运算所得结果为xs，x0表示执行一致性发布前的发布，即x0=。根据定义，式(8)的复合函数计算过程实际上是一种自右向左的操作过程，记第s次计算过程所执行的函数为f[s](x)，即对第[s]个子问题求最优一致性发布，则[s]=(s− 1)modk+1。设p为满足Mp=b的任意一致性发布。由根据定理4 所述的范数不变性，有

反复运用该定理，可得对于任意s有

但是，上述结果无法确定关于y是否满足一致性发布。接下来，本文将尝试论证y是否满足方程My=b的一致性发布。采用反证法论证，首先假设y不是满足My=b的一致性发布，即My≠b。根据多重一致性约束问题的定义，必然存在某个j使M jy≠bj。

令y'为原问题的一致性发布，即，由定理2 可知，y'为M jy=bj的解。由于y不是M jy≠bj的解，显然y'和y不同。令，有d>0 。

根据序列{xi}的收敛性可知，对于任意μ>0，均存在足够大的数l，可取任意s>l，均有。此时，取任意满足s>l且[s]=j的整数s，有。

最后，本文将进一步论证y不仅是满My=b的一致性发布，而且y是关于的最优一致性发布。

根据定理5 所述的内积不变性，对于满足Mp=b中的任意2 个一致性发布p1和p2，有

反复运用该定理，可得

根据上述论证过程，本文成功证明差分隐私下多重一致性约束问题的逼近方法将会收敛于原问题的最优一致性发布。并且，逼近方法的收敛性是无条件的。即无论最优一致性子问题如何划分，逼近方法总能够成功实现最优一致性发布，体现了其强大的稳健性。因此，实践中只需考虑所划分子问题的易解性，通过合理的子问题划分提升发布效率，而不必担心划分结果能否正确实现最优一致性发布。

7 多重一致性约束问题的并行计算

由于差分隐私下多重一致性约束问题的逼近方法在划分子问题时只需考虑划分的合理性，合理的划分可使同类子问题间所涉及的子数据集互不相交，使同类子问题过程满足独立性。利用这种独立性设计并行的计算过程能够进一步提升多重一致性约束问题的求解效率。

以餐馆销量直方图发布问题为例，5 个单品对应了5 个直方图一致性约束子问题，套餐一致约束子问题数量与发布天数T一致。该问题是T+5 重一致性约束问题。不难发现，5 个直方图一致性约束子问题各自关联了一个单品，所涉及数据之间互无交集，最优一致性发布的求解结果也互不影响。因此，这5 个直方图一致性约束子问题可并行计算。同理，套餐一致约束子问题关联的每日发布数据也互无交集，这些子问题的求解也具有可并行性。

根据上述分析，结合多重一致性约束问题的逼近方法，餐馆销量直方图发布问题可划分为c（c=5）个直方图一致性约束子问题与T个套餐一致约束子问题两组。组内的各个子问题可并行地、独立地求解。

根据上述分析，本文将设计差分隐私下餐馆销量直方图发布问题的最优一致性发布并行求解算法。一方面，以顾客购买一次套餐作为事件提供事件级别差分隐私[18]保护，根据餐馆提供的套餐分析，顾客购买套餐最多可以拿到5 份食物（套餐1和套餐2），每日销售数据单独发布时数据敏感度为5。

另一方面，根据Boosting算法的理论，直方图发布的敏感度[2]取决于树高。因此，采用拉普拉斯作为噪声机制，餐馆销量直方图发布问题的全局敏感度[10]为Δ1=ch。分析套餐一致性约束问题，根据套餐内容，本文关于每日销量应满足一致性约束方程Bvt=0。vt∈R5×1表示第t天的销量，其第i个元素vt,i即为当天第i个单品的销量。经分析，B的内容如式(13)所示。

由于套餐一致性约束子问题仅为数据规模为5的一致性发布问题，本文直接采用通用解法求解最优一致性发布。根据上述分析，本文提出算法1 求解差分隐私下餐馆销量直方图发布问题的最优一致性发布。算法1 表明，本文提出的多重一致性约束问题逼近理论不仅能够将更复杂的差分隐私一致性约束问题拆分成简单的子问题，而且可以利用子问题将的独立性实现并行求解算法，极大提升了算法求解性能。

算法1餐馆销量直方图一致性并行发布算法

输入餐馆销量数据集D，隐私预算ε

输出差分隐私直方图一致性发布树

8 实验分析

为了验证本文所提多重一致性约束问题逼近方法解决实际问题的效果，本文以餐馆销量直方图发布问题为例进行实验分析。实验将算法1 与相应的通用解法对比，从算法求解效率、收敛性、稳定等方面对多重一致性约束问题的逼近方法进行综合分析。已有分析表明，Boosting 等差分隐私最优一致性发布问题的发布效果与加噪前数据内容无关[19]。为了实现更大规模的实验分析，在实验目的不受影响的前提下，本文采用虚拟数据进行实验。并且，为保持实验的准确与统一，实验均采用二叉树实现Boosting 子算法。研究表明[4]，差分隐私一致性约束问题的最优一致性发布效果在不同ε下是稳定的，为避免实验冗长，实验统一设ε=1 。实验硬件环境如下：Intel®CoreTM i5-9500H CPU@3.00 GHz，8 GB 内存，1 TB 存储空间。

8.1 收敛性分析

作为一种逼近方法，算法1 的收敛能力至关重要。因此，本节将通过跟踪算法运行过程来对算法的收敛性进行深入分析。收敛性分析包括2 个方面，分别是一致性检验和发布误差分析。虽然通用结果可由解析表达式(7)直接求解，无法直接对比两者的迭代过程，但通用解法已被证明发布结果即为最优一致性发布，实验对比可作为检验算法1 的一致性发布是否满足最优性的可靠标准。因此，在分析发布误差时，本文将其作为对比实验。由于通用解法需要消耗大量资源，常规的实验环境下通用解法难以有效满足发布天数远超1 000 天的发布需求。因此，本实验以T={32,64,128,256,512,1024}天进行分组对比，实验迭代次数固定为100 次，实验重复多次，记录平均结果。

作为多重一致性约束最优发布问题的基本目标，最终发布结果是否满足一致性约束是检验算法有效性的重要指标。为检验发布结果的一致性，本文提出了一致性偏差来衡量算法1 在迭代过程中满足一致性的情况。将s次迭代后的所有数据组织为向量形式，记为。然后，令。根据一致性约束问题的定义可知，当完全满足一致性时，ψ(s)应该等于0。不过，上述收敛性分析表明，逼近方法是在迭代过程中不断地令发布结果趋近于一致性。因而，本实验采用均方误差来衡量一致性偏差。记s次迭代后的一致性偏差为mses，则mses的计算过程如式(14)所示。

如图1 所示，算法1 在迭代过程中出现的一致性偏差随着迭代次数的增加而快速减少。虽然随着T的增加，一致性偏差的收敛速度有所减少，但所有实验都能在迭代50 次左右使一致性偏差趋近于0。因此，在迭代50 次之后，算法就具备了较令人满意的一致性发布结果。并且随着迭代的增加，一致性偏差单调递减，表明算法1 的发布结果具有较强稳定性，不会在迭代过程中突然出现不一致性变大的发布结果。

图1 逼近方法的一致性偏差分析

除了发布结果的一致性，发布误差也是衡量发布结果优劣的重要指标。实验采用标准差衡量发布的误差。记s次迭代后发布结果相对于未加噪数据的标准差为errs，则errs可由式(15)求得

图2 中，虚线表示采用通用解法求得的最优一致性发布结果。由图2 可以看出，无论发布天数T为多少，算法都能相对稳定地收敛于最优一致性发布对应的误差。并且在迭代前后，算法减少误差的效果十分明显，对于提升数据发布的精度具有重要价值。此外，从收敛效果来看，迭代初期算法即可平稳快速地收敛，使误差能够迅速逼近于最优一致性发布。算法只需要较少的迭代就能达到令人满意在一致性发布效果。因此，本文所提多重一致性约束问题的逼近方法具有较高的收敛能力以及算法稳定性。

图2 逼近方法的发布数据误差

8.2 求解效率分析

为进一步验证逼近方法的实用性，本节将探讨算法1 求解最优一致性发布的效率。与8.1 节实验不同，本次实验要求算法1 达到足够的精度才停止。因此，实验设置算法终止条件为

将算法1 的逼近方法与通用解法对比，求得在不同的发布天数T下的算法运行时间如图3 所示。

图3 逼近方法与通用解法的运行时间对比

由图3 可知，算法1 的求解效率显著优于通用解法。从运行时间的增长幅度来看，算法1 的运行时间随着数据量的增大接近于线性增长，与理论的时间复杂度O(Ts)相符。而通用解法增长幅度则快很多，其时间复杂度为O(T3)。虽然当处理小规模数据时，算法1 由于多次迭代运行时间略大于通用解法，但当数据规模变大时，通用解法的效率却低很多，仅处理1 024天的数据发布就需耗时多达267 s，而算法1 仅需要0.667 s，差距高达400 倍。

实际上，算法1 所能处理的数据规模远不止1 024 天。为探究其数据处理潜力，本文采用更大规模数据对其进行实验并记录求解耗时。实验结果如图4 所示。图4 表明，算法1 已具备处理超大规模数据发布的能力，其所能处理的天数已高达百万。这表明算法1 具有强大的数据处理能力，能够满足大多数实际发布的需要。同时也证明了本文所提出的多重一致性约束问题的逼近方法不仅具有较强的理论价值，还具有较强的实际应用价值。

图4 逼近方法在大规模数据下的运行时间

9 结束语

通过差分隐私下多重一致性约束问题的深入研究，本文提出并论证了多重一致性约束问题的逼近方法的有效性，为利用一致性约束子问题解决复杂的差分隐私一致性约束问题的方法奠定了扎实的理论基础。并且，本文以餐馆销量直方图发布问题为例设计的餐馆销量直方图一致性并行发布算法不仅充分展示了逼近方法较高的收敛能力以及求解效率，还体现了该方法具备的并行计算优势。研究结果表明，多重一致性约束问题的逼近方法具有较高的应用价值。

后续的研究工作中将以本文的研究成果作为理论基础，尝试将已被研究的差分隐私一致性发布模型推广到交通、医疗等领域，结合这些领域原本涉及的一致性发布过程实现应用范围更广、复杂程度更高的差分隐私数据发布算法；同时，还将对多重一致性约束问题进行更加深入的理论研究，就如何更加合理地划分一致性约束子问题、如何提升逼近方法的收敛效率以及在不等式约束下如何实现多重一致性最优发布等问题开展研究工作，从而形成关于差分隐私最优一致性发布更加完善的理论体系。