We extend a previous framework for designing differentially private (DP) mechanisms via randomized graph colorings that was restricted to binary functions, corresponding to colorings in a graph, to multi-valued functions. As before, datasets are nodes in the graph and any two neighboring datasets are connected by an edge. In our setting, we assume each dataset has a preferential ordering for the possible outputs of the mechanism, which we refer to as a rainbow. Different rainbows partition the graph of datasets into different regions. We show that when the DP mechanism is pre-specified at the boundary of such regions, at most one optimal mechanism can exist. Moreover, if the mechanism is to behave identically for all same-rainbow boundary datasets, the problem can be greatly simplified and solved by means of a morphism to a line graph. We then show closed form expressions for the line graph in the case of ternary functions. Treatment of ternary queries in this paper displays enough richness to be extended to higher-dimensional query spaces with preferential query ordering, but the optimality proof does not seem to follow directly from the ternary proof.
翻译:我们通过随机化图形色素设计不同私有(DP)机制的先前框架, 限于二进制功能, 与图表中的颜色相对应, 扩大到多值函数。 和以前一样, 数据集是图形中的节点, 任何两个相邻的数据集都是通过边缘连接的。 在我们的设置中, 我们假设每个数据集都对机制的可能输出有优先排序, 我们称之为彩虹。 不同的彩虹将数据集的图表分割到不同区域。 我们显示当DP机制在此类区域的边界上预先指定时, 最多可以存在一个最佳机制。 此外, 如果该机制对所有相同的彩虹边界数据集都采取相同的行为, 问题可以大大简化, 并通过线条图的形态化方式来解决 。 我们然后显示线条图的封闭形式表达方式 。 本文对长期查询的处理显示足够丰富, 足以扩展到具有优先查询顺序的更高维度的查询空间, 但是, 最佳性证明似乎并不直接追溯到 。