2026-08-10T23:54:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10139 2024-03-06T10:45:28Z ddc:004 open_access

Simulating Random Walks on Graphs in the Streaming Model Jin, Ce streaming models random walks sampling 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ce Jin 2019 Is Part Of LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2019.46 urn:nbn:de:0030-drops-101399 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.46 eng https://creativecommons.org/licenses/by/3.0/legalcode