2026-07-26T04:13:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14121 2024-03-06T10:53:31Z ddc:004 open_access

Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs Chen, Lijie Kol, Gillat Paramonov, Dmitry Saxena, Raghuvansh R. Song, Zhao Yu, Huacheng streaming algorithms random walk sampling For a directed graph G with n vertices and a start vertex u_start, we wish to (approximately) sample an L-step random walk over G starting from u_start with minimum space using an algorithm that only makes few passes over the edges of the graph. This problem found many applications, for instance, in approximating the PageRank of a webpage. If only a single pass is allowed, the space complexity of this problem was shown to be Θ̃(n ⋅ L). Prior to our work, a better space complexity was only known with Õ(√L) passes. We essentially settle the space complexity of this random walk simulation problem for two-pass streaming algorithms, showing that it is Θ̃(n ⋅ √L), by giving almost matching upper and lower bounds. Our lower bound argument extends to every constant number of passes p, and shows that any p-pass algorithm for this problem uses Ω̃(n ⋅ L^{1/p}) space. In addition, we show a similar Θ̃(n ⋅ √L) bound on the space complexity of any algorithm (with any number of passes) for the related problem of sampling an L-step random walk from every vertex in the graph. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lijie Chen and Gillat Kol and Dmitry Paramonov and Raghuvansh R. Saxena and Zhao Song and Huacheng Yu 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.52 urn:nbn:de:0030-drops-141218 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.52 eng https://creativecommons.org/licenses/by/4.0/legalcode