论文标题
部分可观测时空混沌系统的无模型预测
Distances Release with Differential Privacy in Tree and Grid Graph
论文作者
论文摘要
有关个人的数据可能包含私人和敏感信息。提出了差异隐私（DP），以解决保护每个人的隐私的问题，同时保留有关人口的有用信息。 Sealfon（2016）引入了一个私人图模型，其中假定将图形拓扑是公开的，而重量信息则被假定为私有。该模型可以在已知的运输系统中表达隐藏的拥塞模式。在本文中，我们重新审视了（Sealfon 2016）中所有顶点之间私下释放近似距离的问题。我们的目标是最大程度地减少加性错误，即释放的距离与私人设置下的实际距离之间的差异。我们在多种情况下提出了改进该问题的解决方案。 对于私人发布全对距离的问题，我们表明对于深度$ h $的树，我们可以释放带有加性错误$ o（\ log^{1.5} h \ cdot \ cdot \ cdot \ log^{1.5} v）$ foride privacy参数的$ o（\ log^{1.5} h \ cd {1.5} v）$的$ o（ $ h $可以小于$ o（\ log v）$。我们的结果意味着保存了$ \ log V $因子，并且树中的加性错误可能小于数组/路径上的错误。此外，对于具有任意边缘权重的网格图，我们还提出了一种使用加性误差$ \ tilde o（v^{3/4}）$释放全对距离的方法，用于固定的隐私参数。在应用方面，曼哈顿等许多城市都由水平街道和垂直途径组成，可以将其建模为网格图。
Data about individuals may contain private and sensitive information. The differential privacy (DP) was proposed to address the problem of protecting the privacy of each individual while keeping useful information about a population. Sealfon (2016) introduced a private graph model in which the graph topology is assumed to be public while the weight information is assumed to be private. That model can express hidden congestion patterns in a known transportation system. In this paper, we revisit the problem of privately releasing approximate distances between all pairs of vertices in (Sealfon 2016). Our goal is to minimize the additive error, namely the difference between the released distance and actual distance under private setting. We propose improved solutions to that problem for several cases. For the problem of privately releasing all-pairs distances, we show that for tree with depth $h$, we can release all-pairs distances with additive error $O(\log^{1.5} h \cdot \log^{1.5} V)$ for fixed privacy parameter where $V$ the number of vertices in the tree, which improves the previous error bound $O(\log^{2.5} V)$, since the size of $h$ can be as small as $O(\log V)$. Our result implies that a $\log V$ factor is saved, and the additive error in tree can be smaller than the error on array/path. Additionally, for the grid graph with arbitrary edge weights, we also propose a method to release all-pairs distances with additive error $\tilde O(V^{3/4}) $ for fixed privacy parameters. On the application side, many cities like Manhattan are composed of horizontal streets and vertical avenues, which can be modeled as a grid graph.
