Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs

Medientyp: E-Artikel; Elektronischer Konferenzbericht; Sonstige Veröffentlichung

Titel: Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs

Beteiligte: Chen, Lijie [VerfasserIn]; Kol, Gillat [VerfasserIn]; Paramonov, Dmitry [VerfasserIn]; Saxena, Raghuvansh R. [VerfasserIn]; Song, Zhao [VerfasserIn]; Yu, Huacheng [VerfasserIn]

Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021

Sprache: Englisch

DOI: https://doi.org/10.4230/LIPIcs.ICALP.2021.52

Schlagwörter: random walk sampling ; streaming algorithms

Entstehung:

Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.

Beschreibung: 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 Õ(√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.

Zugangsstatus: Freier Zugang

Nur in Feld suchen:

Zuletzt gesuchte Begriffe: