Semi-Streaming Algorithms for Annotated Graph Streams
Semi-Streaming Algorithms for Annotated Graph Streams
复制标题
带注释的图流的半流算法
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
J. Thaler
中科院分区：
文献类型：
--
作者：
J. Thaler
人们投入了大量的精力来开发用于分析海量图的流算法。不幸的是，许多结果都是负面的，这表明各种各样的问题需要 $\Omega(n^2)$ 空间来解决。少数亮点之一是针对少数图问题开发了半流算法——这些算法使用空间 $O(n\cdot\text{polylog}(n))$。
在 Chakrabarti 等人的带注释的数据流模型中，计算能力有限的客户端想要计算大量输入的某些属性，但缺乏存储输入的一小部分的资源，因此无法在本地执行所需的计算。因此，客户端访问一个强大但不受信任的服务提供商，该服务提供商不仅执行请求的计算，而且还证明答案是正确的。
我们提出了用于注释图流的半流算法的概念（简称半流注释方案）。在这些协议中，客户端的空间使用量和证明的长度都是 $O(n \cdot \text{polylog}(n))$。我们提供的证据表明，半流注释方案代表了比标准半流模型更强大的解决方案概念。从积极的一面来看，我们为标准模型中难以解决的两个动态图问题提供了半流式注释方案：（精确地）计算三角形和（精确地）计算最大匹配。前一种方案回答了Cormode 的问题。消极的一面是，我们首次确定了两个自然图问题（某个边缘更新模型中的连通性和二部性）可以在标准半流模型中解决，但不能通过“子半流”成本的注释方案来解决。也就是说，这些问题在注释模型中和在标准模型中一样困难。
Considerable effort has been devoted to the development of streaming algorithms for analyzing massive graphs. Unfortunately, many results have been negative, establishing that a wide variety of problems require $\Omega(n^2)$ space to solve. One of the few bright spots has been the development of semi-streaming algorithms for a handful of graph problems -- these algorithms use space $O(n\cdot\text{polylog}(n))$.
In the annotated data streaming model of Chakrabarti et al., a computationally limited client wants to compute some property of a massive input, but lacks the resources to store even a small fraction of the input, and hence cannot perform the desired computation locally. The client therefore accesses a powerful but untrusted service provider, who not only performs the requested computation, but also proves that the answer is correct.
We put forth the notion of semi-streaming algorithms for annotated graph streams (semi-streaming annotation schemes for short). These are protocols in which both the client's space usage and the length of the proof are $O(n \cdot \text{polylog}(n))$. We give evidence that semi-streaming annotation schemes represent a substantially more robust solution concept than does the standard semi-streaming model. On the positive side, we give semi-streaming annotation schemes for two dynamic graph problems that are intractable in the standard model: (exactly) counting triangles, and (exactly) computing maximum matchings. The former scheme answers a question of Cormode. On the negative side, we identify for the first time two natural graph problems (connectivity and bipartiteness in a certain edge update model) that can be solved in the standard semi-streaming model, but cannot be solved by annotation schemes of "sub-semi-streaming" cost. That is, these problems are just as hard in the annotations model as they are in the standard model.