This work concerns with proving space lower bounds for graph problems in the streaming model. It is known that computing the length of shortest path between two nodes in the streaming model requires $\Omega(n)$ space, where $n$ is the number of nodes in the graph. We study the problem of finding the depth of a given node in a rooted tree in the streaming model. For this problem we prove a tight single pass space lower bound and a multipass space lower bound. As this is a special case of computing shortest paths on graphs, the above lower bounds also apply to the shortest path problem in the streaming model. The results are obtained by using known communication complexity lower bounds or by constructing hard instances for the problem. Additionally, we apply the techniques used in proving the above lower bound results to prove space lower bounds (single and multipass) for other graph problems like finding min $s-t$ cut, detecting negative weight cycle and finding whether two nodes lie in the same strongly connected component.


翻译:这项工作涉及到证明流模式中图形问题的空间下线。 众所周知, 计算流模式中两个节点之间最短路径的长度需要 $\ Omega (n) 空间, 其中美元是图形中的节点数。 我们研究在流模式中根树中找到一个特定节点的深度的问题。 对于这个问题, 我们证明是一个紧凑的单一过关空间, 下拉多通道空间。 由于这是在图形中计算最短路径的一个特例, 以上较低界限也适用于流模式中最短路径的问题 。 其结果通过使用已知的通信复杂性较低界限或为问题构建硬实例获得 。 此外, 我们运用了用于证明上下线结果的技术来证明空间的较低界限( 单线和多通道 ) 。 对于其他图表问题, 如找到 mins- t$ 的切线, 检测负重循环, 并发现两个节点是否位于同一紧密相连的组件中 。

0
下载
关闭预览

相关内容

2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
已删除
将门创投
5+阅读 · 2018年1月24日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年1月7日
VIP会员
相关VIP内容
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
相关资讯
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
已删除
将门创投
5+阅读 · 2018年1月24日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员