Simulating Random Walks on Graphs in the Streaming Model
Simulating Random Walks on Graphs in the Streaming Model
复制标题
在流模型中模拟图上的随机游走
DOI：
10.4230/lipics.itcs.2019.46
复制
发表时间：
2018
影响因子：
4.4
通讯作者：
Ce Jin
中科院分区：
文献类型：
--
作者：
Ce Jin
我们研究了大约在图表中近似模拟T-步骤随机步行的问题，其中输入边缘来自单频道流。使用储层采样的直接算法需要内存的单词。我们表明，该空间复杂性对于有向图几乎是最佳的。对于无方向的图，我们证明了一个欧米茄（n sqrt {t}） - 位空间下限，并使用o（n sqrt {t}）单词给出了近距离的算法，带有2^{ - omega（sqrt {t sqrt {t） }）}模拟错误（定义为模拟算法的输出分布与完美随机的分布之间的L_1距离步行）。我们还讨论将算法扩展到旋转门模型，其中边缘插入和删除都可以出现在输入流中。
We study the problem of approximately simulating a t-step random walk on a graph where the input edges come from a single-pass stream. The straightforward algorithm using reservoir sampling needs O(nt) words of memory. We show that this space complexity is near-optimal for directed graphs. For undirected graphs, we prove an Omega(n sqrt{t})-bit space lower bound, and give a near-optimal algorithm using O(n sqrt{t}) words of space with 2^{-Omega(sqrt{t})} simulation error (defined as the l_1-distance between the output distribution of the simulation algorithm and the distribution of perfect random walks). We also discuss extending the algorithms to the turnstile model, where both insertion and deletion of edges can appear in the input stream.